Что «под капотом» у LinkedList?

Добрый день, хабрачитатели!

Как работает ArrayList, вполне понятно. Есть много статей по этому поводу, часть из них иллюстрированы замечательными картинками, так что даже новичкам становится сразу все ясно. К лучшим статьям на эту тему я отношу «Структуры данных в картинках. ArrayList», написанную tarzan82.

Этот же автор описывает принципы работы LinkedList, однако часть данных устарела еще с выходом Java 7, поэтому попытка детально разобраться, что происходит внутри этой коллекции, по рисункам tarzan82 уже сложно. Да и в других источниках я не встретила понятных картинок, потому и возникла идея написать эту статью.

Итак, LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа.

Разберемся, что же происходит, когда мы пишем уже простые и привычные строки кода.

1. Создание связанного списка


LinkedList<Integer> numbers = new LinkedList<>();

Данный код создает объект класса LinkedList и сохраняет его в ссылке numbers. Созданный объект предназначен для хранения целых чисел (Integer). Пока этот объект пуст.

Класс LinkedList содержит три поля:

// модификатор transient указывает на то, что данное свойство класса нельзя
// сериализировать 
transient int size = 0;
transient Node<E> first;
transient Node<E> last;



2. Добавление объекта в конец связанного списка


numbers.add(8);

Данный код добавляет число 8 в конец ранее созданного списка. Под «капотом» этот метод вызывает ряд других методов, обеспечивающих создание объекта типа Integer, создание нового узла, установку объекта класса Integer в поле item этого узла, добавление узла в конец списка и установку ссылок на соседние узлы.

Для установки ссылок на предыдущий и следующий элементы LinkedList использует объекты своего вложенного класса Node:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

При каждом добавлении объекта в список создается один новый узел, а также изменяются значения полей связанного списка (size, first, last).

В случае с добавлением первого элемента создается узел, у которого предыдущий и следующий элементы отсутствуют, т.е. являются null, размер коллекции увеличивается на 1, а созданный узел устанавливается как первый и последний элемент коллекции.

Добавим еще один элемент в нашу коллекцию:

numbers.add(5);

Сначала создается узел для нового элемента (число 5) и устанавливается ссылка на существующий элемент (узел с числом 8) коллекции как на предыдущий, а следующим элементом у созданного узла остается null. Также этот новый узел сохраняется в переменную связанного списка last:

Как можно увидеть на рис. 4, первый элемент коллекции (под индексом 0) пока ссылается на null как на следующий элемент. Теперь эта ссылка заменяется и первый элемент начинает ссылаться на второй элемент коллекции (под индексом 1), а также увеличивается размер коллекции:

3. Добавление объекта в середину связанного списка


numbers.add(1, 13);

LinkedList позволяет добавить элемент в середину списка. Для этого используется метод add(index, element), где index — это место в списке, куда будет вставлен элемент element.

Как и метод add(element), данный метод вызывает несколько других методов. Сначала осуществляется проверка значения index, которое должно быть положительным числом, меньшим или равным размеру списка. Если index не удовлетворит этим условиям, то будет сгенирировано исключение IndexOutOfBoundsException.

Затем, если index равен размеру коллеции, то осуществляются действия, описанные в п. 2, так как фактически необходимо вставить элемент в конец существующего списка.

Если же index не равен size списка, то осуществляется вставка перед элементом, который до этой вставки имеет заданный индекс, т.е. в данном случае перед узлом со значением 5.

Для начала с помощью метода node(index) определяется узел, находящийся в данный момент под индексом, под который нам необходимо вставить новый узел. Поиск данного узла осуществляется с помощью простого цикла for по половине списка (в зависимости от значения индекса — либо с начала до элемента, либо с конца до элемента). Далее создается узел для нового элемента (число 13), ссылка на предыдущий элемент устанавливается на узел, в котором элементом является число 8, а ссылка на следующий элемент устанавливается на узел, в котором элементом является число 5. Ссылки ранее существующих узлов пока не изменены:

Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент (теперь она указывает на узел со значением 13), для предшествующего новому элементу заменяется ссылка на следующий элемент (теперь она указывает на узел со значением 5). И в последнюю очередь увеличивается размер списка:

4. Удаление объекта из списка


Для удаления одного элемента из списка класс LinkedList предлагает нам аж 10 методов, различающихся по типу возвращаемого значения, наличию или отсутствию выбрасываемых исключений, а также способу указания, какой именно элемент следует удалить:

Рассмотрим удаление элемента из связанного списка по его значению. Удалим элемент со значением 5 из нижепредставленного списка:

numbers.remove(Integer.valueOf(5));

Обратите внимание, что принимаемым значением в методе remove(object) является именно объект, если же мы попытаемся удалить элемент со значением 5 следующей строкой
numbers.remove(5);

то получим IndexOutOfBoundsException, т.к. компиллятор воспримет число 5 как индекс и вызовет метод remove(index).

Итак, что же происходит при вызове метода remove(object)? Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла. Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной. Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга:

Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции:

Теперь вернемся к тому моменту, что элемент из удаляемого узла мы сохраняли в памяти. Зачем мы это делали, спросите вы, если эти данные мы нигде дальше не использовали. Дело в том, что рассматриваемый нами метод в результате своей работу не возвращает удаленный элемент, потому данные, возврещенные вызванным в рамках работы метода unlink(node), вызванного методом remove(object), просто не понадобились. А вот когда мы используем метод remove(index), также вызывающий метод unlink(node), то значение данного элемента последовательно возвращается сначала методом unlink(node), а затем и методом remove(index). Похожая ситуация наблюдается и в остальных методах, возвращающих значение удаленного элемента, только внутри вызываются другие методы, отсоединяющие ссылку: в методах poll(), pollFirst(), remove() и removeFirst() это метод unlinkFirst(node), а в методах pollLast() и removeLast() — метод unlinkLast(node).

Итак, что следует помнить о LinkedList, решая, использовать ли данную коллекцию:

  • не синхронизирована;
  • позволяет хранить любые объекты, в том числе null и повторяющиеся;
  • за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции элемента, который осуществляется за линейное время);
  • за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.

Ссылки


Исходный код LinkedList (JDK 8)
Документация LinkedList

Средняя зарплата в IT

110 450 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 7 043 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 45

    +13
    за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции вставки элемента);

    Как раз сложность поиска элемента в двусвязном списке как раз O(N), и это надо прямо указывать. А то у меня от этой вставки и удаления из середины за О(1) глаза на лоб вылезли.


    Из приятного — наглядность картинок порадовала. Продолжайте пробовать писать, но что-то более существенное и интересное, ибо то, что написано здесь — прям для совсем начинающих.

      0
      Ну, справделивости ради — через итераторы сложность удаления будет как-раз O(1). А вот если удалять по индексу/элементу — тут всё печально, да…
        0
        Но нужно до элемента доитерироватся, а это печально. Если стоять на месте и вставлять элементв временный лист и addAll часто оптимальнее.
          0
          Prototik а вы можете дать ссылку на какой-нибудь авторитетный ресурс, который подтвердит, что перебор элементов списка с помощью итератора осуществляется за О(1)?
            +2
            перебор элементов списка с помощью итератора осуществляется за О(1)?

            Перебор, очевидным образом осуществляется за O(n). Предыдущий комментарий был о том, что, если у нас есть итератор, который уже стоит на каком-то конкретном узле, скорость удаления этого узла никак не будет зависеть от количества элементов в LinkedList.

        +11
        Объяснение хорошее, хотел бы добавить, что часто ArrayList даст фору LinkedList, даже там где, где вычислительная сложность у последнего лучше. Связано это с тем, при расчете вычислительной сложности, не учитывается особенности работы кеша. Когда в кеш загружается массив ArrayList, он делает это максимально быстро, все элементы находятся последовательно в одной области памяти. Объекты же связанного листа могут быть разбросаны в памяти и их придется загружать в кеш поштучно, что относительно дорого.
          0

          Да, и кроме того — иногда забывают, что ArrayList (по сути массив) занимает непрерывную область памяти и если попытаться создать такой список очень большого размера, то вполне реально упасть с ошибкой выделения памяти.

            +1
            Процесс упадет, если попытаетесь выделить память превышающую лимит, а непрерывность, следствие фрагментации, это проблема языков с неуправляемой памятью. GC, когда занимается сбором мусора, именно для того останавливает все потоки исполнения, чтобы сдвинуть все оставшиеся в живых объекты в начало памяти, по сути он делает дефрагментацию. Просто пометить память как свободную от удаленных объектов, он мог бы на фоне, без остановки всего и вся. И именно поэтому в Java нет указателей, а есть ссылки, которые не дают доступ к физическому адресу в памяти, потому что этот адрес может меняться.
            Далее, если мы имеем дело с большим объемом данных, то LinkedList тем более не подойдет, расходы памяти на него выше, чем у ArrayList. Каждый элемент оборачивается, небольшим, но все таки объектом Node. Когда ваша программа работает на пределе возможностей, универсального рецепта нет, но вероятно и от ArrayList придется отказаться тоже и работать с простыми массивами, как с наиболее низкоуровневыми объектами.
              0
              занимает непрерывную область памяти и если попытаться создать такой список очень большого размера, то вполне реально упасть с ошибкой выделения памяти.

              Обычно JVM будет перемещать объекты пока не сможет выделить такую область памяти. То есть ошибка out of memory будет если банально кончится вся или почти вся свободная память. Но LinkedList занимает (по моим подсчетам) примерно в 4 раза больше места чем ArrayList, то есть он упадет с out of memory намного раньше, не говоря уже о бешеной нагрузке на сборщик мусора от миллионов объектов типа Node.

              P.S. Есть разумеется фундаментальное ограничение на ArrayList и LinkedList в виде использования int в качестве их счетчика (а это 2 с небольшим миллиарда). Поэтому List не может быть больше 2 млд. с хвостиков значений, но это несколько гигабайт, а учитывая что в List хранятся только ссылки, то с объектами это десятки гигабайт на одну структуру. Как правило, для большинства даже серверных задач это с головой хватает (если вам нужно в памяти одного процесса держать десятки гигабайт данных в одном List — у вас что не так со архитектурой приложения).
            +3

            Зря вы не упомянули add/remove в итераторе, это существенная часть внутреннего устройства (единственная реализация за O(1))

              +8
              Как давно признался Шипилёву автор LinkedList,



              Рекомендую прочитать весь тред.

              twitter.com/joshbloch/status/583813919019573248
                0

                Надеюсь, автор знает, кто такой Шипилев :)

                  +1
                  Ради одного только этого коммента стоило зайти в статью :).
                    0
                    Ну мы все знаем что он используется в LinkedHasMap/Set :)
                    +4
                    Поавила использования LinkedList:
                    1. Не существует задач когда стоит использовать LinkedList,
                    2. Если у вас такая задача см. пункт 1,

                    Надо часто удалять из середины? Используйте ArrayList заменяя элементы на null, а потом их игнорируяя. При слишком большом кол-ве null — можно создать новый лист без null.
                    Надо всавлять в начало — переверните ArrayList и вставляйте в конец, С двух сторон — просто используйте 2 листа,
                    Надо вставлять в середину много элементом — используйте временный лист и addAll,

                    В конце концов, самое лучшее используйте TreeList из Apache коллекций. Не хотите /не можете тянуть зависимость? Просто скопируйте ее код.

                    Это осуждалось уже в моей статье
                      0
                      Его удобно использовать в качестве Dequeue. Каждый раз когда мне нужно решать какую-то задачу со стеком — использую его.
                        0
                        Так-то ArrayList тоже может использоватся для этого, добавление и удаление из конца вообще очень быстрое, разве что интерфейса он не реализует и писать чуть дольше, но можно увереным что он не станет узким местом в производительности.
                          0
                          А как работает удаление из начала?
                            0
                            Если все равно на производительность — то точно так же, если нет см. мой пост выше.
                              0
                              Это был риторический вопрос. Понятно что удаление из начала линкдлиста очень быстро, так же как и получение знаечния оттуда. Поэтому если нам надо Dequeue — LinkedList хорошая структура данных.
                                0
                                Когда говорят «очевидно/понятно/несомненно» темную сторону силы вижу я. Нет, не понятно и не очевидно, что будет быстрее (вы, видимо, совсем не смотрели мой комментарий и комментарии выше, в том числе от того кто написал LinkedList и те кто занимается производительностью JVM).

                                Придумайте любую задачу и тест производительности, а перепишу с использованием ArrayList (на крайний случай двух ArrayList) реализацию быстрее. Я уже не говорю о TreeList от апача, которые быстрее будет практически всегда.

                                И это не говоря о диких расходах памяти (намного больших чем ArrayList) и мусора для сборщика
                                  0
                                  Лист, обёмом в полтора миллиарда long. Удаляем элемент по 0 индексу. Замеряем время до конца операции. Сравниваем ArrayList и LinkedList.
                                    0
                                    Не вопрос, заменяем элемент ArrayList на null и меняем внутренний индекс первого элемента. И замеряем скорость.

                                    public class MyList  {
                                        private List<Long> list = new ArrayList<Long>(1500000000);
                                        private int firstIndex;
                                    
                                        public Long remove(int index) {
                                            Long old = list.set(index + firstIndex, null);
                                            if(index == 0) {
                                                firstIndex++;
                                            }
                                            return old;
                                        }
                                        
                                        ...
                                    }
                                    


                                    При вставке в первый элемент проводим обратную операцию (на случай вставки до удаления можно изначально начинать с firstIndex равным 10-30% от ожидаемого размера коллекции).
                                      0
                                      Не, я прошу удалить первый элемент с помощью remove(0). Чтобы работало как popFirst(). А вы предлагает саблисты использовать. Что ошибкоопасно. Да и итератор если получить — нас итератор от основного листа вернётся.

                                      И раз уж мы тут говорим про сравнение листов — то ArrayList на 3 миллиарда элементов тоже не сделаешь.
                                        0
                                        А вы предлагает саблисты использовать. Что ошибкоопасно.

                                        Не хотите писать руками используйте (или скопируйте) TreeList от апача.

                                        Да и итератор если получить — нас итератор от основного листа вернётся.

                                        Кто сказал? Сложно написать свой итератор?

                                        И раз уж мы тут говорим про сравнение листов — то ArrayList на 3 миллиарда элементов тоже не сделаешь.

                                        С такими запросами вам классы BigList нужны
                                          0
                                          Вы сказали что ArrayList всегда лучше. Нет. С остальным я и не спорил. Писать свой итератор — плохо потому что можно наошибаться. И вообще свой код писать опасно.
                                        0
                                        Учитывая что линкедлист занимает в 6 раз больше памяти (не говоря уже о 3 миллиардах объектов для сборщика), мы можем выделять в обе стороны по 100% запасу и все равно выиграем линкедлист в 2 раза по памяти.
                                          0
                                          Я скорость предлагаю мерить, а не память. Вы сказали вам подобрать пример когда ArrayList эффективнее чем LinkedList. Я подобрал и сказал что именно мы выигрываем. Почему вы мне говорите про то что мы на линдлисте проигрываем по памяти мне абсолютно непонятно. А ещё мы по скорости случайного доступа!
                                            0
                                            Я сказал, что нет задач для которых использование LinkedList имело бы смысл даже чисто по производительности, так как есть возможность либо написать свой код, либо использовать намного лучшие аналоги из сторонних коллекций (проверенные и оттестированные), если так уж не хочется свой код.
                                            О чем вы спорите я тоже не знаю.
                            0
                            А разве в Java нет чего-нибудь вроде std::deque из c++ STL? Если нет, возможно, эффективнее будет реализовать руками, чем использовать LinkedList.

                            Он работает примерно следующим образом: храним массив (одним куском) + его размер, и два указателя на него: на первый элемент дека и на следующий после последнего.
                            При добавлении в конец или начало: смотрим, есть ли у нас свободное место в массиве. Если нет — выделяем новый массив в X (от 1 до 2) раз больше текущего и все элементы перемещаем в него. Дальше добавляем новый элемент по указателю на конец или начало, сдвигая его в нужную сторону. Сложность получается O(N) в случае увеличения размера, но, учитывая экспоненциальность выделения памяти, в среднем O(1).
                            В итоге у нас добавление и удаление элементов как в начало, так и в конец за O(1), а еще за O(1) поиск элемента по индексу и вообще все cache friendly.
                              0
                              ArrayDeque.
                                0
                                Тогда почему бы не использовать его вместо LinkedList в качестве дека?
                                  0
                                  Допустим у меня в стеке должно лежить 3 миллиарда элементов…
                                    0
                                    Допустим. И?
                                    Например, я вижу такое существенное отличие в данном случае, как экономия 6 млрд указателей (48 Гб памяти) по сравнению с LinkedList. Да и скорость итерирования за счет лучшего использования кеша будет лучше.
                                      0
                                      PS: Сорри, возможно, я что-то как-то не так понимаю, ибо с C# сто лет как не работал, а когда работал, это было несерьезно. Но концепция дека на массиве от этого хуже не становится. В c++ нет ну вообще никаких проблем с тем, чтобы сделать std::deque (или std::vector, если такой класс пишется самостоятельно) на 3 млрд элементов.
                                        0
                                        В массиве не помещается 3 миллиарда элементов. Но вообще-то да, экономим мы либо память, либо процессор.
                                          0
                                          Это какое-то ограничение C#? Ну, тогда можно написать свой массив, который будет лишен этого недостатка.
                                          Для хранения, скажем, 3 млрд 32-битных чисел в массиве нам нужно 3*4=12 Гб памяти, а для хранения их же в списке нам уже потребуется 3*(4 + 2*8)=60 Гб памяти. Как может такое быть, что первое не умещается в память, а второе умещается?
                                            0
                                            Про шарп ничего ен знаю, тольк опро джаву, которую тут вроде бы и обсуждали. В массив в джаве в принципе не умещается больше чем Integer.MAX_VALUE элементов. А вот в линкдлисте таких ограничений нет.
                                              0
                                              Да, действительно, Java — опечатка.
                                                0
                                                А вот в линкдлисте таких ограничений нет.

                                                Правда нет? То есть то что все методы интерфейса List принимают только int в качестве индекса вас не смущает?

                                                А то что внутренне поле size у LinkedList тоже int — тоже не наводит на смутные сомнения, что больше Integer.MAX_VALUE элементов в LinkedList никак не влезет?
                                                  0
                                                  Ладно, вот тут неправ, признаю. А там проверки или overflow сработает и мы сможем нафигачить столько элементов сколько захотим?
                                0
                                Поавила использования LinkedList:
                                1. Не существует задач когда стоит использовать LinkedList,
                                2. Если у вас такая задача см. пункт 1,

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

                                  +2
                                  Тогда заранее можно выделить память с запасом, LinkedList в разы больше памяти ест. Ну и стабильно плохая производительность вряд ли лучше очень хорошей производительностью с ростом до чуть менее хорошей. Выделение массива не так сильно влияет на производительность, так как там используется системная функция выделения куска памяти и копирования, в большинстве случаев по сравнению с запуском сборщика (а LinkedList куда больше объектов создает) расширения массива нечто почти незаметное.
                                  0
                                  Правила именования листов:
                                  1. Если перед вами лист дерева (структура данных или растение) — называйте его листом.
                                  2. Если перед вами лист бумаги — называйте его листом.
                                  2. Если перед вами ArrrayList или LinkedList — называйте их списками (точнее, списочным массивом и связанным списком). Вы, конечно, можете называть их и листами, но это так же неправильно, как называть их деревьями, массивами, графами, кошками или космическими кораблями.
                                    0
                                    LinkedList может быть полезен в качестве источника «сырых» данных (например, запроса из таблицы, который заранее условиями WHERE разбивать на части не удобно или не эффективно), которые приходится в цикле обрабатывать несколько раз, разделяя данные на части по какому-то условию. При каждом проходе из списка удаляются записи, соответствующими критерию из данного цикла, так что в следующем цикле приходится обходить гораздо меньше записей (null оставляет количество записей первоначальным, создание новой копии списка на каждом проходе снижает эффективность).

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

                                  Самое читаемое