Материал: 8

Узел содержит поля данных и одну или несколько ссылок. Ссылка является ссылкой на следующий узел. Узел обычно определяется внутри другого класса, что делает его внутренним классом (inner) для контейнера.

Схема односвязного списка на рисунке 8.6 – 8.7.

Рисунок 8.6 – Single-Linked Lists

Рисунок 8.7 – Single-Linked Lists

DoubleLinkedList (двусвязный список)

Ограничения одно-связанный список включают в себя:

-вставка в начало списка O (1);

-вставка на другие позиции O(n) где n размер списка.

Можно вставить узел только после ссылочного узла. Можно удалить узел, только если у нас есть ссылка на его узел-предшественник. Может проходить по списку только в прямом направлении. Эти ограничения удаляются путем добавления ссылки в каждом узле к предыдущему узлу (двусвязный список, рисунок 7.8).

Рисунок 8.8 – Double-Linked Lists

Циклические списки

Циклический связанный список (рисунок 8.9): связать последний узел двусвязного списка с первым узлом и первый с последним.

Преимущество: может двигаться в прямом или обратном направлении по списку, даже после того, как вы прошли последний или первый узел. Можно посетить все элементы списка из любой начальной точки. Никогда нельзя выйти за пределы списка (за последний элемент). Неудобство: бесконечный цикл.

Рисунок 8.9 – Циклический список

Класс LinkedList<E>:

-часть Java API;

-реализует интерфейс List<E> с использованием двусвязного списка (double-linked list).

Методы данного класса указаны на рисунке 8.10.

Рисунок 8.10 – Методы класса LinkedList<E>

Интерфейс Iterator<E> Interface

Интерфейс итератора Iterator составляет часть пакета API java.util. В интерфейсе List объявлен метод итератора, который возвращает объект итератора, который будет выполнять итерацию по элементам этого списка. Iterator (рисунок 7.11) не относится к какому-либо элементу и не указывает на конкретный узел в данный момент времени, но точки между узлами.

Рисунок 8.11 – Методы интерфейса Iterator<E>

Интерфейс ListIterator<E>

Ограничения Iterator:

-можно только пройти списка в прямом направлении;

-обеспечивает только метод удаления.

Необходимо заранее реализовывать итератор, используя свой собственный цикл, если исходное положение не в начале списка. ListIterator<E> (рисунок 8.12) является расширением Iterator<E>

для преодоления ограничений. Можно представить Итератор как закладку, которая позиционируется между элементами связанного списка.

Рисунок 8.12 – Методы интерфейса ListIterator<E>

Сравнение Iterator и ListIterator

ListIterator является подинтерфейсом интерфейса Iterator; классы, которые реализуют ListIterator обеспечивают все возможности и кроме того интерфейс итератора требует меньшего количества методов и может использоваться для итерации по более общим структурам данных, но только в одном направлении.

Для Iterator требуется интерфейс Collection, в то время как для

ListIterator требуется только интерфейс List.

Различия между ListIterator и индексом

У ListIterator есть методы nextIndex и previousIndex, которые возвращают значения индексов, связанные с объектами, которые будут возвращаться при вызове методов next или previous. У класса

LinkedList есть метод ListIterator (int индекс). Возвращает

ListIterator, чей вызов next возвращает элемент на следующей позиции индекса.

Производительность ArrayList и LinkedList

LinkedList обеспечивает лучшую производительность в следующих

случаях:

-при операциях добавления/удаления элементов в начале списка по

индексу;

-при операциях добавления/удаления элементов внутри списка по итератору (при условии, что этот итератор был каким-то образом получен заранее);

-при доступе к первому/последнему элементу списка (getFirst() / getLast() / removeFirst() / removeLast() и

т.д.). Во многих остальных случаях ArrayList показывает более высокую производительность.

LinkedList надо что-то вставить в середину в какую-то позицию Х, то он будет прямо с начала по ссылкам искать эту позицию. С LinkedList

надо использовать, к примеру, ListIterator, который умеет вставлять в середину списка по индексу (поэтому в LinkedList вставка на самом деле будет за мизерное постоянное время).

Пример:

ListIterator<Integer> iter = list.listIterator(inputIndex);

iter.add(new Integer(123));