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


14
Задача
Java Syntax Pro, 14 уровень, 5 лекция
Недоступна
StringLinkedList
Пришло время познакомиться с двусвязным списком. Решая эту задачу ты поймешь, как работает двусвязный список и сможешь добавлять в него элементы. У тебя есть класс StringsLinkedList, в котором есть поля first и last, указывающие на первый и последний элемент соответственно.

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

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

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

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

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

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

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


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

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

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

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

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

Такие дела.

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

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


14
Задача
Java Syntax Pro, 14 уровень, 5 лекция
Недоступна
StringLinkedList, часть 2
Решая эту задачу, ты научишься извлекать элемент из двусвязного списка. Мы реализовали метод add, который добавляет элементы в конец списка. Тебе нужно реализовать метод get(int), который вернет строку под индексом, переданным в метод. Если строки с таким индексом нет, нужно вернуть null.
Комментарии (582)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Сергей Тыщенко Уровень 14
13 июля 2025
Какая то здесь странная реализация двусвязного списка. Зачем хранить адреса терминальных узлов в поле узлов, зачем два лишних узла создавать?. Классическая реализация - в полях списка хранятся узловые ссылки на голову и хвост. Надеюсь в библиотечном типе реализовано по классике...
Anonymous #3585174 Уровень 16
6 июля 2025
Like
Виктор Уровень 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
коллекции которые используют все, мы вам дадим изи задачи. Коллекция которую никто не использует, держите Хард)