JavaRush /Java Курсы /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.

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

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

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

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

Dan Уровень 15

19 сентября 2023

У меня уже глаз дергается при слове linkedList

Afonya Уровень 6

17 сентября 2023

если не можете преподать материал как должно предоставте ссылки на сторонние компетентные ресурсы и задач по теме по больше, а так то материал предоставлен на отвяжись - вопрос, за что я плачу свои деньги? За то что вы льёте воду - тянете время за которое я плачу

bi lya Уровень 19

12 сентября 2023

Честно - первую задачу не осилил... Но разобрав ее по символам до костей, вторую сделал сам, через for. Условие по ограничению при отсутствующем индексе сделал через


if (мояПеременная.next == null) return null;

\_@_/

Айнур Хайбулов Уровень 18

2 сентября 2023

Понял что ничего не понял

Никита Бухарин Уровень 20

24 августа 2023


  Node newElement = new Node(); // Создание нового экземпляра класса Node
        newElement.value = value; // Присвоение значению нового элемента переданное значение

        if (last.prev == null) { // Если последний элемент в списке отсутствует
            first.next = newElement; // Устанавливается следующий элемент для начального маркера
            last.prev = newElement; // Устанавливается предыдущий элемент для конечного маркера
            newElement.prev = first; // Устанавливается начальный маркер как предыдущий элемент для нового элемента
        } else { // Если последний элемент в списке уже есть
            last.prev.next = newElement; // Устанавливается новый элемент как следующий для предыдущего последнего элемента
            newElement.prev = last.prev; // Устанавливается предыдущий элемент последнего элемента как предыдущий элемент для нового элемента
            last.prev = newElement; // Устанавливается новый элемент как последний элемент
        }

Валентин Уровень 14

21 августа 2023

Сегодня в 5 утра начался второй раунд Мой мозг vs LinkedList я в нокдауне! Как элементы хранятся в воздухе??? В ArrayList есть массив у массива есть индексы. А тут нет НИЧЕГО... пустота и в этой пустоте что-то к чему-то присваивается. Где оно хранится физически? Как? Задача про add... Правильный ответ из приложения вбил в IDE - Не работает!!! Cannot assign field "next" because "lastNode" is null парам-парам-пам ВСЕ! Node lastNode = last.prev; Как ЦЕЛЫЙ объект с ТРЕМЯ полями может быть равен одной переменной??? или вот... lastNode.next = node; Как переменная может быть равна целому объекту??? Помогите пожалуйста.

FeatHonnar Уровень 16

17 августа 2023

Тот редкий случай, когда свое решение нравится больше, чем авторское (сначала мое, потом авторское)


    public String get(int index) {
        //напишите тут ваш код
        Node lastNode = first;
        for (int i = 0; i <= index; i++) {
            if (lastNode.next == null) {
                return null;
            }
            lastNode = lastNode.next;
        }
        return lastNode.value;
    }


    public String get(int index) {
        int currentIndex = 0;
        Node currentElement = first.next;
        while ((currentElement) != null) {
            if (currentIndex == index) {
                return currentElement.value;
            }
            currentElement = currentElement.next;
            currentIndex++;
        }
        return null;
    }

Dmitry Vidonov Уровень 26 Expert

13 августа 2023

Если кому-то не понятно или сложно - рисуйте в тетради как выглядят Node, с чем они связаны и как происходит процесс вставки прописывайте прям по шагам. Осознать все в уме человеку, который с такими штуками раньше не работал - нереально практически. Здесь дан некий упрощенный вариант списка, в котором у нас first и last узлы ни на что не ссылаются изначально, просто как два буйка в море болтаются, ни с чем не связаны. Если вы попробуете вывести значения полей next, prev и value у first или last узла еще до добавления чего-либо, то окажется, что они все равны null. Следовательно, для того, чтобы программа поняла, что вы еще ничего в список не добавляли, вам достаточно будет условия:


if(first.next == null)

По-хорошему, как по мне, у нас при добавлении нового узла есть 2 ситуации, которые надо рассмотреть отдельно: 1) либо мы вообще ничего еще не добавляли 2) либо добавили хотя бы один узел в этот список В первом случае представьте, что у вас болтаются вот эти два first и last и добавляемым узлом вы связываете три узла воедино. То есть помещаете свой узел между first и last. Какие здесь должны быть связи? У first указатель next будет принимать значение того узла, который вы добавили. Не value, а сам узел. Т.е. first.next = node; Далее - у добавляемого узла указатель next будет смотреть на last узел. Указатель prev добавляемого узла смотрит на first. Указатель prev узла last смотрит на наш добавляемый узел. Последним шагом заносим значение в наш node новоиспеченный. Вторая ситуация: в списке уже были узлы. И вместо first у нас будет фигурировать узел, который идет прямо перед last. То есть новый узел вы будете впихивать между ним и last. Все шаги по установлению связей будут точно такие же, но вместо first вам надо дать указатель на узел last.prev, т.е. тот, что стоял перед last. Надеюсь что это как-то кому-то поможет.

maestro Уровень 23 Expert

2 августа 2023

то есть linkedlist не юзается 99.9% разработчиков, а в уровень добавляют задачи с пометкой Hard, мне кажется это немного странным.........

Ulukay Уровень 19

1 августа 2023

фуф!

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

1. История LinkedList

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

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

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

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

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

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

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