Структура объявления двусвязного списка:
Функциональность Очереди соответствует действиям с двусвязным списком:"голова" показывает на последний добавленный элемент, а "хвост" – на элемент, который должен быть удален первым. (В очереди с течением времени элементы перемещаются от "головы" к «хвосту»).
Типовые операции для односвязных списков:
Список - упорядоченная совокупность, состоящая из элементов.
Список называется упорядоченным, если имеется отношение предыдущего элемента к следующему. Список с таким отношением порядка называется односвязным. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла невозможно. Длина списка – это число элементов, содержащихся в списке. Список нулевой длины называется пустым списком. К списку применимы операции: включения, исключения. Списки являются простейшими динамическими типами данных.
Односвязный список:
Основные операции (методы) для списков:
добавить элемент (новый элемент становится первым в списке)
удалить элемент (удаляется первый элемент списка, второй станет первым)
Дополнительные методы:
удалить все элементы, копировать список, проверить равенство списков, добавить элемент в конец списка, удалить элемент из конца списка, добавить или удалить элемент, получить элемент по его номеру, изменить порядок элементов на обратный, упорядочить элементы, найти позицию данного элемента в упорядоченном списке.
Кольцевой и двусвязный списки: отличия от односвязного списка:
Двусвязный список:
В отличие от односвязного списка, в двусвязном списке ссылки в каждом узле указывают на предыдущий и на последующий узел в списке. По двусвязному списку можно передвигаться в любом направлении — как к началу, так и к концу. В этом списке проще производить удаление и перестановку элементов, так как всегда известны адреса тех элементов списка, указатели которых направлены на изменяемый элемент.
Кольцевой список:
Разновидностью связных списков является кольцевой (циклический, замкнутый) список. Он тоже может быть односвязным или двусвязным. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний. Реализация такой структуры происходит на базе линейного списка. В каждом кольцевом списке есть указатель на первый элемент. В этом списке константы NULL не существует.
Так же существуют циклические списки с выделенным головным элементом, облегчающие полный проход через список.
Все операции и методы для односвязного списка применимы и к двусвязным спискам и кольцевым спискам!!!
Порядок добавления элемента в односвязный список:
1. Создается новый элемент, задается ссылка на него, и заполняется информационная часть. Поле связи (next) пустое, т.е. = null
2. Ссылка из головы копируется в поле next нового элемента (стрелка 3). /Теперь на первый элемент списка указывают два элемента: голова списка и новый элемент (стрелки 1 и 3)/
3. Ссылка на новый элемент копируется в поле next головы / так что next начинает "указывать" на новый элемент (появляется стрелка 2, стрелка 1 исчезает)/ После этого новый элемент становится первым элементом списка: голова указывает на новый элемент, новый элемент – на старый первый, далее – как было в исходном списке.
При удалении элемента действия проводятся в обратном порядке.
public class ListEl { //ListElement – элемент списка
Object inf; //информационная часть
ListEl next; //ссылка на следующий элемент
ListEl( ) { next = null; inf = null; } //конструктор
ListEl (Object ob) { inf = ob; next = null; } //конструктор
public static void addToList (ListEl hd, Object ob) {
ListEl e=new ListEl (ob );
if(hd.next!= null) { // если список не пуст,
ListEl old= hd.next; // сохранить ссылку
hd.next =e; // голову связать с новым
e.next =old;
}
else hd.next =e; // или сделать элемент первым
}
public static void printMyList ( ListEl a ) { //печать списка
ListEl c= a.next; //с – текущий элемент списка
while( c != null ) { // пока есть элементы,
System.out.print( c.inf+ " "); // напечатать инфо-часть с
c= c.next; // и перейти к следующему
}; System.out.println( ); // когда все элементы
public static void main(String[ ] args){
ListEl list=new ListEl(); //создали «голову» списка
for (int i=0; i<10; i++)
addToList (list, Integer.toString(i *i ) ) ; //помещая в inf-часть
printMyList ( list ); //печатаем созданный список
}
}
Результат в терминале:
81 64 49 36 25 16 9 4 1 0