Связанный массив LinkedList
LinkedList — реализует интерфейсы List, Dequeue, Queue и является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. LinkedList реализует методы получения, удаления и вставки в начало, середину и конец списка, а также позволяет добавлять любые элементы, в том числе и null.
Конструкторы LinkedList
Класс LinkedList имеет следующие два конструктора :
Создание LinkedList объекта
Для создания нового LinkedList объекта можно использовать один из конструкторов, например:
В графическом виде объект можно представить в следующем виде:
Созданный объект list, содержит свойства header и size. header — это псевдоэлемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как список вновь созданного объекта пустой, свойства next и prev указывают сами на себя (т.е. на элемент header). Следовательно, выполняется следующее тождество.
Добавление элемента в связанный массив LinkedList
Для добавления элемента в массив LinkedList можно использовать методы
Класс LinkedList включает статический внутренний класс Entry, с помощью которого создаются новые элементы.
Для добавления нового элемента в LinkedList необходимо выполнить две итерации:
В результате графически объект можно представить в следующем виде:
Методы LinkedList
Класс LinkedList содержит ряд методов для управления элементами, среди которых можно выделить следующие:
| Метод | Описание |
|---|---|
| addFirst() / offerFirst() | добавляет элемент в начало списка |
| addLast() / offerLast() | добавляет элемент в конец списка |
| removeFirst() / pollFirst() | удаляет первый элемент из начала списка |
| removeLast() / pollLast() | удаляет последний элемент из конца списка |
| getFirst() / peekFirst() | получает первый элемент |
| getLast() / peekLast() | получает последний элемент |
Пример связанного списка LinkedList :
В примере LinkedList создаются и используются два списка: для строк и для объектов класса Person. При этом в дополнение к методам addFirst/removeLast и т.д., доступны стандартные методы, определенные интерфейсом Collection: add(), remove, contains, size и другие. Поэтому можно использовать разные методы для одного и того же действия. Например, добавление в самое начало списка можно сделать так :
Отличие LinkedList от ArrayList
LinkedList выполняет вставку и удаление элементов в списке за постоянное время (определение позиции для вставки или удаления не рассматривается). В большинстве случаев LinkedList проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.
Если в алгоритме предусмотрена активная работа (вставка/удаление) в середине списка или в случаях, когда необходимо гарантированное время добавления элемента в список, то целесообразно использовать LinkedList.
Что «под капотом» у LinkedList?
Добрый день, хабрачитатели!
Как работает ArrayList, вполне понятно. Есть много статей по этому поводу, часть из них иллюстрированы замечательными картинками, так что даже новичкам становится сразу все ясно. К лучшим статьям на эту тему я отношу «Структуры данных в картинках. ArrayList», написанную tarzan82.
Этот же автор описывает принципы работы LinkedList, однако часть данных устарела еще с выходом Java 7, поэтому попытка детально разобраться, что происходит внутри этой коллекции, по рисункам tarzan82 уже сложно. Да и в других источниках я не встретила понятных картинок, потому и возникла идея написать эту статью.
Итак, LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа. 
Разберемся, что же происходит, когда мы пишем уже простые и привычные строки кода.
1. Создание связанного списка
Данный код создает объект класса LinkedList и сохраняет его в ссылке numbers. Созданный объект предназначен для хранения целых чисел (Integer). Пока этот объект пуст.
Класс LinkedList содержит три поля:
2. Добавление объекта в конец связанного списка
Данный код добавляет число 8 в конец ранее созданного списка. Под «капотом» этот метод вызывает ряд других методов, обеспечивающих создание объекта типа Integer, создание нового узла, установку объекта класса Integer в поле item этого узла, добавление узла в конец списка и установку ссылок на соседние узлы.
Для установки ссылок на предыдущий и следующий элементы LinkedList использует объекты своего вложенного класса Node:
При каждом добавлении объекта в список создается один новый узел, а также изменяются значения полей связанного списка (size, first, last). 
В случае с добавлением первого элемента создается узел, у которого предыдущий и следующий элементы отсутствуют, т.е. являются null, размер коллекции увеличивается на 1, а созданный узел устанавливается как первый и последний элемент коллекции.
Добавим еще один элемент в нашу коллекцию:
Сначала создается узел для нового элемента (число 5) и устанавливается ссылка на существующий элемент (узел с числом 8) коллекции как на предыдущий, а следующим элементом у созданного узла остается null. Также этот новый узел сохраняется в переменную связанного списка last: 
Как можно увидеть на рис. 4, первый элемент коллекции (под индексом 0) пока ссылается на null как на следующий элемент. Теперь эта ссылка заменяется и первый элемент начинает ссылаться на второй элемент коллекции (под индексом 1), а также увеличивается размер коллекции: 
3. Добавление объекта в середину связанного списка
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 из нижепредставленного списка: 
Обратите внимание, что принимаемым значением в методе remove(object) является именно объект, если же мы попытаемся удалить элемент со значением 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, решая, использовать ли данную коллекцию:
LinkedList в Java
Вступление:
LinkedList — это линейная структура данных, состоящая из узлов. В односвязном списке каждый узел содержит данные и ссылку. Здесь эталонная часть ссылается на следующий узел в связанном списке.
Создайте LinkedList :
Мы можем создать связанный список в Java одним из следующих способов:
т.е. этот класс предоставляет два конструктора:
Добавление элементов:
Удаление элементов:
Эти методы как удаляют, так и возвращают удаленное значение.
Класс Java LinkedList также предоставляет методы removeFirstOccurrence (Object obj) и removeLastOccurrence (Object obj) для удаления первого и последнего вхождения данного значения соответственно. Эти методы возвращают false, если в нашем списке такого значения нет.
Запрашиваемые элементы:
У нас есть методы getFirst () и getLast () в классе LinkedList для запроса первого или последнего элемента нашего связанного списка:
Поскольку это реализация двусвязного списка, getFirst () и getLast () являются операциями постоянного времени.
Если нам известен индекс извлекаемого элемента, мы также можем использовать метод get (int index) интерфейса List :
Итерация по LinkedList :
Мы будем перебирать связанный список, как и любую другую форму списка:
LinkedList против ArrayList:
Давайте наметим различия между классами Java LinkedList и ArrayList :
| LinkedList | ArrayList |
|---|---|
| Использует двусвязное представление списка | Использует концепцию динамических массивов |
| Реализует оба списка | Только реализует список |
| Не подходит для произвольного доступа | Отлично подходит для произвольного доступа. Если мы знаем индекс, это займет всего O (1) времени для поиска |
| O (1) вставки / удаления в начале и конце связанного списка Java | Вставка элементов в ArrayList может привести к изменению размера резервного массива, поэтому амортизированная стоимость O (n). Кроме того, вставка в начале ArrayList потребует от нас смещения всех элементов вправо на одну позицию. |
| Затраты памяти на хранение ссылок на предыдущий и следующий узел | Нет необходимости хранить дополнительную информацию |
Вывод:
Оставьте первый комментарий.
Мнения, высказанные участниками Java Code Geeks, являются их собственными.
LinkedList
Класс LinkedList имеет больше операций, чем ArrayList, а значит более сложный и требующий больше памяти. Класс представляет структуру данных связного списка и реализует интерфейсы List, Dequeue, Queue.
LinkedList позволяет хранить любые объекты, в том числе null и повторяющиеся.
Для добавления элемента в конец списка используется метод add(), для удаления используется метод remove().
Используемый в примере итератор имеет ограниченные возможности, например, его метод add() добавляет новый элемент в конец списка. Чтобы иметь возможность вставлять в середину, используйте интерфейс ListIterator. Кроме того, в ListIterator имеются методы previous() и hasPrevious() для прохода по списку в обратном направлении.
Метод add() итератора вводит новый элемент до текущей позиции итератора. Например, в следующем примере пропускается первый элемент связного списка и вводится элемент «Пушок» перед вторым элементом.
Также есть удобные методы addFirst(), addLast(), addAll().
Получить объект можно через get(), getFirst(), getLast().
Для изменения элемента используется метод set().
Метод contains() проверяет наличие конкретного элемента.
Метод element() идентичен getFirst() и присутствует из-за принадлежности к интерфейсу Queue, который используется в LinkedList. А также есть метод peek(), который идентичен getFirst(), но не вызовет ошибку, если объект будет несуществующим, а просто вернёт null. А ещё есть методы peekFist() и peekLast(), которые аналогичны peek(), но более понятны по названию.
Для удаления отдельного элемента кроме метода remove() можно вызвать методы poll(), pollFirst(), pollLast().
На самом деле методов гораздо больше, изучайте документацию.
Структуры данных в картинках. LinkedList
Приветствую вас, хабражители!
Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.
В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.
LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null.
Создание объекта
Footprint
Object size: 48 bytes
Только что созданный объект list, содержит свойства header и size.
header — псевдо-элемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как на данный момент список еще пуст, свойства next и prev указывают сами на себя (т.е. на элемент header). Размер списка size равен 0.
Добавление элементов
Footprint
Object size: 112 bytes
Добавление элемента в конец списка с помощью методом add(value), addLast(value)
и добавление в начало списка с помощью addFirst(value) выполняется за время O(1).
Внутри класса LinkedList существует static inner класс Entry, с помощью которого создаются новые элементы.
Каждый раз при добавлении нового элемента, по сути выполняется два шага:
1) создается новый новый экземпляр класса Entry
2) переопределяются указатели на предыдущий и следующий элемент
Добавим еще один элемент
Добавление элементов в «середину» списка
Для того чтобы добавить элемент на определенную позицию в списке, необходимо вызвать метод add(index, value). Отличие от add(value) состоит в определении элемента перед которым будет производиться вставка
Метод entry(index) пробегает по всему списку в поисках элемента с указанным индексом. Направление обхода определяется условием (index > 1)). По факту получается что для нахождения нужного элемента перебирается не больше половины списка, но с точки зрения асимптотического анализа время на поиск растет линейно — O(n).
Как видно, разработчик может словить IndexOutOfBoundsException, если указанный индекс окажется отрицательным или большим текущего значения size. Это справедливо для всех методов где в параметрах фигурирует индекс.
Удаление элементов
Удалять элементы из списка можно несколькими способами:
— из начала или конца списка с помощью removeFirst(), removeLast() за время O(1);
— по индексу remove(index) и по значению remove(value) за время O(n).
Рассмотрим удаление по значению
Footprint
Object size: 176 bytes
Внутри метода remove(value) просматриваются все элементы списка в поисках нужного. Удален будет лишь первый найденный элемент.
В общем, удаление из списка можно условно разбить на 3 шага:
1) поиск первого элемента с соответствующим значением
2) переопределяются указатели на предыдущий и следующий элемент
3) удаление указателей на другие элементы и предание забвению самого элемента
Итераторы
Для собственноручного перебора элементов можно воспользоваться «встроенным» итератором. Сильно углубляться не буду, процессы протекающие внутри, очень похожи на то что описано выше.
Приведенный выше код поместит указатель в начало списка. Так же можно начать перебор элементов с определенного места, для этого нужно передать индекс в метод listIterator(index). В случае, если необходимо начать обход с конца списка, можно воспользоваться методом descendingIterator().
Стоит помнить, что ListIterator свалится с ConcurrentModificationException, если после создания итератора, список был изменен не через собственные методы итератора.
Ну и на всякий случай примитивный пример перебора элементов:
Итоги
— Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1);
— На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1);
— Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки;
— Не синхронизирован.
Ссылки
Объем занимаемой памяти измерялся с помощью инструмента memory-measurer. Для его использования также понадобится Guava (Google Core Libraries).
