1. История LinkedList

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

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

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

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

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

В интернете часто можно найти такое сравнение классов ArrayList и 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, к каждой быстрой операции вставки добавляется медленная операция «получение элемента».

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

Операция Метод ArrayList LinkedList
Добавление элемента
add(value)
Быстро Очень быстро
Вставка элемента
add(index, value)
Медленно Очень медленно
Получение элемента
get(index)
Очень быстро Очень медленно
Изменение элемента
set(index, value)
Очень быстро Очень медленно
Удаление элемента
remove(index)
Медленно Очень медленно
Вставка через итератор
it.add(value)
Медленно Очень быстро
Удаление через итератор
it.remove()
Медленно Очень быстро

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

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


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

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

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

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

Устройство LinkedList

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

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

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

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

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

Устройство LinkedList 1



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

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

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

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

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

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

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


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

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

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

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

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

Такие дела.

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

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