Связанный список (LinkedList) — Java: Списки

ArrayList — это одна из нескольких готовых реализаций интерфейса List. Для хранения данных ArrayList, использует массив, что с одной стороны позволяет работать быстро в случае необходимости обращаться к произвольным элементам по индексу, с другой, работает медленно, в том случае, если нам нужно добавить или удалить элемент списка. Связано это с тем, что массивы имеют фиксированную длину и для изменения размера списка придется создавать новый массив и копировать в него данные из старого.

Если произвольный доступ к списку нас не волнует, а мы больше выполняем вставку и удаление новых элементов в список, то тогда эффективнее использовать LinkedList. Эта реализация списка основана на структуре данных называемой двунаправленный список.

import java.util.LinkedList;

var items = new LinkedList<String>();

items.add("Sun");
items.add("Mars");
items.add("Jupiter");
items.add("Saturn");

Внутри это выглядит примерно так:

Head -> Sun -> Mars -> Jupiter -> Saturn -> Null

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

• Произвольный доступ к элементу выполняется относительно долго, так как, в отличие от массивов, в двунаправленном списке придется перебирать элементы по одному до тех пор, пока мы не придем к нужному. Например, если мы обращаемся к элементу под индексом 5, то внутри LinkedList будет выполнено пять операций по извлечению следующего элемента.
• Добавление новых элементов работает быстро и эффективно. Нам не нужно ничего заново создавать, как в случае с массивами. Достаточно поменять указатель на следующий и предыдущий элемент, так чтобы они ссылались на вновь добавленный.

items.remove(1); // удаляет Mars
items.add("Mars"); // добавляет в конец
items.addFirst("Uranus"); // добавляет в начало
System.out.println(items); // [Uranus, Sun, Jupiter, Saturn, Mars]

Но здесь есть нюанс. remove() и add() методы интерфейса List, поэтому они одинаково работают для всех реализаций List. Метод addFirst() реализован только в LinkedList, но его нет в интерфейсе List. Это значит, что если нам нужна возможность добавлять элементы в начало, то придется указывать тип LinkedList, а не List.

Дополнительные материалы

1. Класс LinkedList

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты