LinkedList

LinkedList — связанный двунаправленный список. Как и в ArrayList, порядок хранения элементов в LinkedList соответствует последовательности их добавления.

Поскольку LinkedList представляет из себя связанный список, каждый его элемент ссылается на 2 соседних - предыдущий и следующий. Также Класс LinkedList содержит ссылки на первый и последний элементы списка (поля first, last). Итератор LinkedList поддерживает обход в обе стороны.

LinkedList позволяет добавлять любые элементы, в том числе и null.

Новый объект класса LinkedList создаётся с размером size = 0, first = null, last = null.

Класс LinkedList содержит внутренний статический класс Node, с помощью которого создаются новые элементы для хранения в нём информации о себе. Он содержит поля item, next (ссылка на следующий элемент), prev (ссылка на предыдущий элемент).
При добавлении первого элемента (назовем его Item) создается узел, у которого предыдущий и следующий элементы отсутствуют, т.е. являются null, размер коллекции увеличивается на 1, а созданный узел устанавливается как первый и последний элемент коллекции (first = last = Item).

Добавление нового элемента:
1. Создаётся новый экземпляр класса Node. Также этот новый узел сохраняется в переменную связанного списка last.
2. Переопределяются указатели на предыдущий и следующий элемент, увеличивается размер коллекции.

Добавление элементов в «середину» списка:
add(index, value).
1. Для этого нужно пробежаться по списку в поисках элемента с указанным индексом. Обход осуществляется циклом for от начала или от конца списка. Поэтому в худшем случае приходится обойти только половину списка.
2. Создаётся новый новый экземпляр класса Node.
3. Для него назначаются ссылки next, prev.
4. Перестраиваются все ссылки для элементов, следующих за ним.

Удаление элементов:
Удаление первого или последнего элемента: removeFirst(), removeLast()
При удалении по индексу или значению происходит одинаково.
1. Находится требуемый узел.
2. Перестраиваются ссылки для следующего и предыдущего узла.
3. Обнуляется ссылка на удаляемый элемент.

LinkedList не синхронизирован. Чтобы его синхронизировать, нужно воспользоваться методом Collections.synchronizedList(new LinkedList()).

Полная статья о LinkedList.