JavaRush /Курсы /Java Syntax Pro /Знакомство с коллекцией LinkedList

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

Java Syntax Pro

14 уровень , 5 лекция

Открыта

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. Обязательно.

Решая эту задачу, ты научишься извлекать элемент из двусвязного списка. Мы реализовали метод add, который добавляет элементы в конец списка. Тебе нужно реализовать метод get(int), который вернет строку под индексом, переданным в метод. Если строки с таким индексом нет, нужно вернуть null.

Предыдущая Предыдущая лекция

Следующая Следующая лекция

Комментарии (582)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Сергей Тыщенко Уровень 14

13 июля 2025

Какая то здесь странная реализация двусвязного списка. Зачем хранить адреса терминальных узлов в поле узлов, зачем два лишних узла создавать?. Классическая реализация - в полях списка хранятся узловые ссылки на голову и хвост. Надеюсь в библиотечном типе реализовано по классике...

Anonymous #3585174 Уровень 16

6 июля 2025

Виктор Уровень 16

15 июня 2025

Вот вроде читаешь и понимаешь логику, а как начинаешь делать вообще непонятно что происходит.

Eternal Fire Уровень 28

28 мая 2025

Поменял бы value нодов в последней задаче. Получилось решить вот так public String get(int index) { Node current = first.next; while (current.value != null && Integer.parseInt(current.value) != index + 1) { current = current.next; } return current.value; } В целом компилятор принял решение, но всё-таки это не совсем то, что требовалось в задаче )

VadChet Уровень 28

15 мая 2025

Блин, в лекции перед первым заданием явно не хватает примеров, пошагового объяснения. Действительно, без записи в Excel (или на бумажке, как хотите) сложно понять что вообще происходит. Признаюсь, я почти сразу открыл ответ и начал думать над ним. Без готового решения у меня бы ушло очень много времени и сил, чтобы придумать всё это самостоятельно.

Leano Уровень 16

24 мая 2025

Полностью согласен, хорошо, что сейчас есть разные инструменты ИИ, которые помогают разобраться более детально. Я первое задание подсмотрел ответ также, т.к очень долго не понимал как это работает. Затем разобрал сам ответ и как под капотом работает LinkedList и попросил ИИ разжеванно мне объяснить как он работает. После этого 2-е задание решалось чуть легче, чем первое. Нужно просто терпения и усидчивости :) В таком списке было интересно разобраться на самом деле, это очень важно для дальнейшего понимания алгоритмов. Для тех кто пишет, что проще скипнуть, чем проходить никому ненужный список: да, ребят, он сложный для понимания без разжевывания, но самостоятельно разобраться почему именно так, а не иначе - очень круто. Нужно лишь погуглить или спросить у ИИ и попытаться хотя бы готовый ответ разобрать. Не сдавайтесь сразу не попытавшись даже инфу найти! :) Если хочется быть крутым тех.специалистом по Java - нужно перетерпеть и постараться понять, в реальности такие ситуации очень часто будут случаться, когда нефига непонятно "как правильно" сделать. После того как получилось понять эту темку: + Дофамин + Мотивация + Знание для ответов на вопросах собеса Оно того стоит :)

LisoEdoEd Уровень 16 Student

31 мая 2025

спасибо за совет использовать ИИ. Эта самая сложная тема для меня за все время

Anonymous #3537180 Уровень 23

2 мая 2025

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

Alpha Уровень 19

31 марта 2025

По первой задаче, логика (может кому поможет разобраться): 1) Если last.prev равно null (то есть ни на что не ссылался раньше, а значит объектов в списке не было и это первое добавление), то соответственно и в first.next автоматически должен быть null (можно конечно проверять условие сразу на last.prev == null && first.next == null). В данном случае при первом добавлении, просто указываем last.prev и first.next ссылки на первый наш добавленный объект. В самом объекте поля next и prev при первод добавлении использовать не надо, т.к. других объектов, на которые он мог бы ссылаться нет. 2) При добавлении второго и следующих объектов, мы должны указать нашему новому объекту в поле prev ссылку на уже существующий в конце списка, а это тот, на который уже ссылается last.prev, тут просто копируем ссылку в наш новозданный объект в поле prev из last.prev (node.prev = last.prev). Ок, далее нам надо, чтобы уже last.prev ссылался на новосозданный объект (last.prev = node). Ну и осталось, чтобы объект который был перед нашим новосозданным объектом ссылался на этот новый объект (node.prev.next (обращаемся к объекту до новосозданному к полу 'next') = node). //напишите тут ваш код Node node = new Node(); node.value = value; if(last.prev == null) { last.prev = node; first.next = node; } else { node.prev = last.prev; last.prev = node; node.prev.next = node; }

Хэйли Эванс Уровень 19

28 марта 2025

мда последняя задача то еще дно, через for не пропускает хотя он работает имеет все проверки и выводит все как и ожидается , а в праильном решении используют while, я битый час пыталась понять что ж не так , но и даже gpt и копилот не поняли что не так и мы вместе пришли к выводу что тестирование ожидает while железобетонно...

Илья Уровень 30

1 апреля 2025

Решил через for и прошел проверку. Больше сидел и не понимал почему не проходит условие проверки на null, пока не зашел на обсуждение данной задачи, где сказали сделать проверку на index < 0


    public String get(int index) {
        if (index < 0) {
            return null;
        }

        Node current = first.next;
        for (int i = 0; i < index; i++) {
            if (current == last) {
                return null;
            }
            current = current.next;
        }
        return current == last ? null : current.value;
    }

lusya 1 Уровень 32

2 апреля 2025

А у меня наоборот😀 Node node = first следовательно нужно было "<= index", а я по привычке поставила "<" и тупила, что же тут не так

Nagnetatel Уровень 26

23 марта 2025

Первую задачу решил через создание нового объекта prevNode, в котором хранилась ссылка на предыдущий созданный объект, prevNode присваиваю ссылку на первый созданный объект, дальше просто обновляю ее. Валидатор принял, но решение в ответе более изящное)

Riga Уровень 23

4 марта 2025

коллекции которые используют все, мы вам дадим изи задачи. Коллекция которую никто не использует, держите Хард)

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

1. История LinkedList

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

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

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

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

1. История `LinkedList`

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

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