Знакомство с коллекцией LinkedList

1. История LinkedList

В Java есть еще один класс-коллекция, который достался Java в наследство от языка C++. Это класс LinkedList, что переводится как «Связный Список».

Внешне LinkedList — это такой же список, как и ArrayList. У класса LinkedList есть все те же методы, что и у класса ArrayList. И в принципе вы всегда можете использовать LinkedList вместо ArrayList, и все будет работать.

Так зачем же нужен еще один класс-список?

Все дело во внутреннем устройстве класса LinkedList. Вместо массива там используется двусвязный список. Что это такое, расскажем немного позже.

Но за счет другого внутреннего устройства у класса LinkedList — самая быстрая операция вставки элементов в середину списка.

В интернете часто можно найти такое сравнение классов ArrayList и LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Вроде бы все понятно: если нужно вставлять элементы в список часто, используйте LinkedList, если редко, то ArrayList. Однако реальность немного другая.

2. Никто не использует LinkedList

Никто не использует LinkedList.

Недавно даже сам автор кода класса LinkedList в твиттере написал пост: «Ребята, кто-нибудь вообще использует LinkedList? За 20 лет я не использовал его ни разу!».

Так в чем же дело?

Во-первых, класс ArrayList стал вставлять элементы в середину списка очень быстро. При добавлении элемента в середину списка нужно сдвинуть все элементы после нужного на 1 в сторону конца списка. Раньше это занимало время.

Но сейчас все поменялось. Все элементы массива находятся рядом в одном блоке памяти, поэтому операция по сдвигу элементов массива выполняется очень быстрой низкоуровневой командой System.arraycopy().

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

Во-вторых, класс LinkedList быстро вставляет элементы, если вы вставляете их с помощью итератора. Если вы с помощью итератора проходитесь по списку LinkedList и постоянно вставляете новые элементы (или удаляете существующие), это действительно супербыстрая операция.

Если же вы просто в цикле добавляете элементы внутрь класса LinkedList, к каждой быстрой операции вставки добавляется медленная операция «получение элемента».

Реальность гораздо ближе к такой ситуации:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Почему же операция получения элемента в LinkedList такая медленная?

Ответ на этот вопрос вы узнаете, если немного ознакомитесь с устройством LinkedList

3. Устройство LinkedList

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

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

Вот как выглядит такой список в памяти:

По бокам (серый фон) переменные first и last, которые хранят ссылки на объекты типа Node.

В середине вы видите цепочку объектов (именно объектов, не переменных) типа Node. Каждый из них состоит их трех полей:

• prev — хранит ссылку на предыдущий объект типа Node (желтый фон).
• value — хранит значение – элемент списка (зеленый фон).
• next — хранит ссылку на следующий объект типа Node (синий фон)

Второй объект (адрес == F24) является следующим (next) для первого и предыдущим (prev) для третьего. Желтое поле третьего объекта содержит ссылку F24 и синее поле первого объекта содержит ссылку F24.

Стрелки с первого и третьего объектов указывают на один и тот же второй объект. Поэтому более правильно было бы нарисовать стрелки так.

4. Вставка элемента в связный список

Чтобы добавить человека в такую очередь, нужно просто согласие двух соседних людей. Первый из них запоминает новичка как нового: «этот человек за мной», а второй — как нового «этот человек передо мной».

Всего-то и нужно изменить ссылки двух соседних объектов:

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

Удаление еще проще. Если мы хотим удалить, допустим 100-й объект из списка, нужно просто у 99-го объекта поменять next, чтобы он указывал на 101-й объект, а у 101-го объекта поменять prev, чтобы он указывал на 99. И все.

Вот только получить 100-й объект не так просто.

5. Получение элемента списка

Чтобы получить 100-й элемент связного списка, нужно:

Получить 1-й объект: на него ссылается переменная first у объекта LinkedList. У 1-го объекта есть ссылка (поле next) на 2-й объект. С ее помощью получаем второй объект. У 2-го объекта есть ссылка на третий, и т.д.

Если нам нужно получить ссылку на 100-й объект, нам нужно последовательно пройтись по всем объектам с 1-го до 100-го. А если нам нужен миллионный элемент списка, нужно последовательно перебрать миллион объектов!

А ведь если эти объекты добавлялись в список в разное время, они находятся в разных частях памяти и вряд ли одновременно попадают в кэш процессора. А это значит, что последовательный перебор элементов связного списка — вещь не просто медленная, а очень медленная.

Такие дела.

Так зачем мы тут учим, как устроен этот медленный LinkedList?

Все дело в том, что на собеседовании вас обязательно спросят, чем LinkedList отличается от ArrayList. Обязательно.