Руководство по Java LinkedList

1. Введение

LinkedList — это двусвязный список, реализующий интерфейсы List и Deque . Он реализует все необязательные операции со списками и разрешает все элементы (включая null ).

2. Особенности

Ниже вы можете найти наиболее важные свойства LinkedList :

• Операции, индексирующие список, будут проходить по списку с начала или с конца, в зависимости от того, что ближе к указанному индексу.
• Это не синхронизировано
• Его итераторы Iterator и ListIterator являются отказоустойчивыми (это означает, что после создания итератора, если список будет изменен, будет выдано исключение ConcurrentModificationException )
• Каждый элемент представляет собой узел, который хранит ссылку на следующий и предыдущий элементы.
• Он поддерживает порядок вставки

Хотя LinkedList не синхронизирован, мы можем получить его синхронизированную версию, вызвав метод Collections.synchronizedList , например:

List list = Collections.synchronizedList(new LinkedList(...));

3. Сравнение с ArrayList

Хотя оба они реализуют интерфейс List , у них разная семантика, что определенно повлияет на решение, какой из них использовать.

3.1. Структура

ArrayList — это структура данных на основе индекса, поддерживаемая массивом . Он обеспечивает произвольный доступ к своим элементам с производительностью, равной O(1).

С другой стороны, LinkedList хранит свои данные в виде списка элементов, и каждый элемент связан со своим предыдущим и следующим элементом. В этом случае операция поиска элемента имеет время выполнения, равное O(n).

3.2. Операции

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

3.3. Использование памяти

LinkedList потребляет больше памяти, чем ArrayList , потому что каждый узел в LinkedList хранит две ссылки, одну для своего предыдущего элемента и одну для следующего элемента, тогда как ArrayList содержит только данные и свой индекс. ``

4. Использование

Вот несколько примеров кода, которые показывают, как вы можете использовать LinkedList :

4.1. Творчество

LinkedList<Object> linkedList = new LinkedList<>();

4.2. Добавление элемента

LinkedList реализует интерфейс List и Deque , кроме стандартных методов add() и addAll() есть addFirst() и addLast() , которые добавляют элемент в начало или конец соответственно.

4.3. Удаление элемента

Подобно добавлению элементов, эта реализация списка предлагает методы removeFirst() и removeLast().

Также есть удобные методы removeFirstOccurence() и removeLastOccurence() , которые возвращают логическое значение (true, если коллекция содержит указанный элемент).

4.4. Операции с очередью

Интерфейс Deque обеспечивает поведение, подобное очереди (фактически Deque расширяет интерфейс Queue ):

linkedList.poll();
linkedList.pop();

Эти методы извлекают первый элемент и удаляют его из списка.

Разница между poll() и pop() заключается в том, что pop выдает NoSuchElementException () для пустого списка, тогда как poll возвращает null. Также доступны API pollFirst() и pollLast() .

Вот, например, как работает push API:

linkedList.push(Object o);

Который вставляет элемент в качестве заголовка коллекции.

LinkedList имеет много других методов, большинство из которых должны быть знакомы пользователю, который уже использовал списки . Другие, предоставляемые Deque , могут быть удобной альтернативой «стандартным» методам.

Полную документацию можно найти здесь .

5. Вывод

ArrayList обычно является реализацией списка по умолчанию .

Однако существуют определенные варианты использования, в которых использование LinkedList будет более подходящим, например предпочтение постоянного времени вставки/удаления (например, частые вставки/удаления/обновления), а не постоянное время доступа и эффективное использование памяти.

Примеры кода можно найти на GitHub .