Теория: Связанный список (LinkedList)

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");

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

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

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

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

Для более глубокого понимания темы мы рекомендуем просмотреть видео лекцию, которая является дополнительным материалом к данному курсу.