Структуры данных в картинках. 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).
Связанный массив 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
Класс 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
Вступление:
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
1. История LinkedList
Так зачем же нужен еще один класс-список?
Но за счет другого внутреннего устройства у класса LinkedList — самая быстрая операция вставки элементов в середину списка.
В интернете часто можно найти такое сравнение классов ArrayList и LinkedList :
| Операция | Метод | ArrayList | LinkedList |
|---|---|---|---|
| Добавление элемента | Быстро | Очень быстро | |
| Вставка элемента | Медленно | Очень быстро | |
| Получение элемента | Очень быстро | Медленно | |
| Изменение элемента | Очень быстро | Медленно | |
| Удаление элемента | Медленно | Очень быстро |
2. Никто не использует LinkedList
Во-первых, класс ArrayList стал вставлять элементы в середину списка очень быстро. При добавлении элемента в середину списка нужно сдвинуть все элементы после нужного на 1 в сторону конца списка. Раньше это занимало время.
К тому же, сейчас у процессоров большой кэш, и обычно весь массив попадает в такой кэш, поэтому элементы массива сдвигаются даже не в памяти, а в кэше процессора. Миллион элементов легко сдвигается за одну миллисекунду.
Во-вторых, класс LinkedList быстро вставляет элементы, если вы вставляете их с помощью итератора. Если вы с помощью итератора проходитесь по списку LinkedList и постоянно вставляете новые элементы (или удаляете существующие), это действительно супербыстрая операция.
Реальность гораздо ближе к такой ситуации:
| Операция | Метод | ArrayList | LinkedList |
|---|---|---|---|
| Добавление элемента | Быстро | Очень быстро | |
| Вставка элемента | Медленно | Очень медленно | |
| Получение элемента | Очень быстро | Очень медленно | |
| Изменение элемента | Очень быстро | Очень медленно | |
| Удаление элемента | Медленно | Очень медленно | |
| Вставка через итератор | Медленно | Очень быстро | |
| Удаление через итератор | Медленно | Очень быстро |
Почему же операция получения элемента в LinkedList такая медленная?
Ответ на этот вопрос вы узнаете, если немного ознакомитесь с устройством LinkedList
3. Устройство LinkedList
Каждый элемент двусвязного списка хранит ссылки на предыдущий и следующий элемент. Это чем-то напоминает очередь, где каждый человек запоминает того, кто стоит перед ним, и того, кто стоит после него.
Вот как выглядит такой список в памяти:
Второй объект (адрес == F24) является следующим ( next ) для первого и предыдущим ( prev ) для третьего. Желтое поле третьего объекта содержит ссылку F24 и синее поле первого объекта содержит ссылку F24.
Стрелки с первого и третьего объектов указывают на один и тот же второй объект. Поэтому более правильно было бы нарисовать стрелки так.