Bazaprogram.ru

Новости из мира ПК
3 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Linkedlist java методы

Связанный массив LinkedList

LinkedList — реализует интерфейсы List, Dequeue, Queue и является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. LinkedList реализует методы получения, удаления и вставки в начало, середину и конец списка, а также позволяет добавлять любые элементы, в том числе и null.

Конструкторы LinkedList

Класс LinkedList имеет следующие два конструктора :

  • LinkedList(): создает пустой список;
  • LinkedList(Collection collection): создает список, в который добавляет все элементы коллекции collection.

Создание LinkedList объекта

Для создания нового LinkedList объекта можно использовать один из конструкторов, например:

В графическом виде объект можно представить в следующем виде:

Созданный объект list, содержит свойства header и size. header — это псевдоэлемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как список вновь созданного объекта пустой, свойства next и prev указывают сами на себя (т.е. на элемент header). Следовательно, выполняется следующее тождество.

Добавление элемента в связанный массив LinkedList

Для добавления элемента в массив LinkedList можно использовать методы

  • add(value), addLast(value) — добавление в конец списка
  • addFirst(value) — добавление в начало списка

Класс LinkedList включает статический внутренний класс Entry, с помощью которого создаются новые элементы.

Для добавления нового элемента в LinkedList необходимо выполнить две итерации:

  • создать экземпляр класса Entry;
  • переопределить указатели на предыдущий и следующий элемент.

В результате графически объект можно представить в следующем виде:

Методы 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

ArrayList — это реализованный на основе массива список объектов. LinkedList — это связный список объектов.

LinkedList выполняет вставку и удаление элементов в списке за постоянное время (определение позиции для вставки или удаления не рассматривается). В большинстве случаев LinkedList проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.

Если в алгоритме предусмотрена активная работа (вставка/удаление) в середине списка или в случаях, когда необходимо гарантированное время добавления элемента в список, то целесообразно использовать LinkedList.

Структуры данных в картинках. 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. Это справедливо для всех методов где в параметрах фигурирует индекс.

Читать еще:  Java security krb5 conf

Удаление элементов

Удалять элементы из списка можно несколькими способами:
— из начала или конца списка с помощью 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).

Редакторский дайджест

Присылаем лучшие статьи раз в месяц

Скоро на этот адрес придет письмо. Подтвердите подписку, если всё в силе.

  • Скопировать ссылку
  • Facebook
  • Twitter
  • ВКонтакте
  • Telegram
  • Pocket

Похожие публикации

  • 4 октября 2019 в 07:23

Структуры данных для программистов игр: bulk data

Экзотические структуры данных: Modified Merkle Patricia Trie

Потоки Redis как чистая структура данных

Вакансии

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

Спасибо — очень просто написано и легко для понимания.

В связи со статьей возник вопрос: кто-нибудь в реальном проекте когда-либо использовал LinkedList?

Из своего опыта скажу, что даже в тех случаях, когда он по идее должен был дать прирост в производительности — т.е. большой список с частым удалением и добавлением элементов в середину и начало списка — ArrayList все равно оказывался быстрее.

Объяснение простое: ArrayList внутри себя использует System.arrayCopy — нативную функцию, которая отрабатывает на удивление шустро. В то же время для LinkedList’а приходится переопределять несколько указателей, но это не самое главное. Все эти указатели на предыдущего и следующего обходятся сборщиком мусора. Из-за этого растет время, необходимое для стадии маркинга, а с учетом того, что в одном списке оказываются элементы из разных поколений, вся процедура затягивается еще больше.

В единственный раз, когда LinkedList почти догнал ArrayList по производительности, я решил попробовать PersistentVector из Clojure, и тот оказался в полтора раза быстрее обоих. PersistentVector внутри представляет из себя дерево массивов, поэтому операции вставки приводят к изменению только одного или нескольких сегментов дерева, т.е. одной или нескольким операциям arrayCopy, которая для небольших массивов остается непревзойденной по скорости.

Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.

Да, это ясно, но ведь список будет какое-то время жить в рантайме, по нему нужно будет итерироваться, и с учетом того, что мы добавляем туда элементы, итерироваться придется неоднократно. А это довольно дорогая операция по сравнению с ArrayList’ом.

Если нам так уж нужно, чтобы элементы находились в определенном порядке, не лучше ли формализовать этот порядок в виде компаратора и использовать SortedSet?

А если порядок не нужен, почему бы не добавлять элементы в конец списка?

А если ожидаемое количество элементов известно, не проще ли создать ArrayList с заданным первоначальным размером?

А если все-таки, несмотря на все вышеперечисленные предложения, больше подходит LinkedList, не стоит ли посмотреть в сторону B-деревьев?

Есть только один сценарий, при котором LinkedList уместен — когда он стоит в основе реализации очереди, используемой несколькими потоками.

LinkedList в Java

Связанный список — это линейные структуры данных, в которых элементы не хранятся в смежных местоположениях, а каждый элемент представляет собой отдельный объект с частью данных и частью адреса. Элементы связаны с помощью указателей и адресов. Каждый элемент известен как узел. Из-за динамичности и простоты вставок и удалений они предпочтительнее массивов. У него также есть несколько недостатков, таких как невозможность прямого доступа к узлам, вместо этого нам нужно начинать с головы и следовать по ссылке, чтобы добраться до узла, к которому мы хотим получить доступ.
Для хранения элементов в связанном списке мы используем двусвязный список, который обеспечивает линейную структуру данных, а также используется для наследования абстрактного класса и реализации интерфейсов списка и deque.

Читать еще:  Java lang linkageerror

В Java класс LinkedList реализует интерфейс списка . Класс LinkedList также состоит из различных конструкторов и методов, как и другие коллекции Java.

Конструкторы для Java LinkedList:

  1. LinkedList (): используется для создания пустого связанного списка.
  2. LinkedList (Коллекция C): используется для создания упорядоченного списка, который содержит все элементы указанной коллекции, возвращаемые итератором коллекции.

// Java-код для реализации связанного списка

public class Test

public static void main(String args[])

// Создание объекта связанного списка классов

LinkedList object = new LinkedList ();

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

System.out.println( «Linked list : » + object);

// Удаление элементов из связанного списка

System.out.println( «Linked list after deletion: » + object);

// Поиск элементов в связанном списке

boolean status = object.contains( «E» );

System.out.println( «List contains the element ‘E’ » );

System.out.println( «List doesn’t contain the element ‘E'» );

// Количество элементов в связанном списке

int size = object.size();

System.out.println( «Size of linked list = » + size);

// Получить и установить элементы из связанного списка

Object element = object.get( 2 );

System.out.println( «Element returned by get() : » + element);

System.out.println( «Linked list after change : » + object);

Методы для Java LinkedList:

  1. add (int index, E element): Этот метод вставляет указанный элемент в указанную позицию в этом списке.
  2. add (E e): этот метод добавляет указанный элемент в конец этого списка.
  3. addAll (int index, Collection c): этот метод вставляет все элементы в указанной коллекции в этот список, начиная с указанной позиции.
  4. addAll (Коллекция c): этот метод Добавляет все элементы в указанной коллекции в конец этого списка в том порядке, в котором они возвращаются итератором указанной коллекции.
  5. addFirst (E e): этот метод вставляет указанный элемент в начало этого списка.
  6. addLast (E e): этот метод добавляет указанный элемент в конец этого списка.
  7. clear (): этот метод удаляет все элементы из этого списка.
  8. clone (): этот метод возвращает поверхностную копию этого LinkedList.
  9. contains (Object o): этот метод возвращает true, если этот список содержит указанный элемент.
  10. downndingIterator (): Этот метод возвращает итератор для элементов в этой деке в обратном последовательном порядке.
  11. element (): Этот метод извлекает, но не удаляет заголовок (первый элемент) этого списка.
  12. get (int index) : Этот метод возвращает элемент в указанной позиции в этом списке.
  13. getFirst (): этот метод возвращает первый элемент в этом списке.
  14. getLast (): этот метод возвращает последний элемент в этом списке.
  15. indexOf (Object o): этот метод возвращает индекс первого вхождения указанного элемента в этом списке или -1, если этот список не содержит элемент.
  16. lastIndexOf (Object o): этот метод возвращает индекс последнего вхождения указанного элемента в этом списке или -1, если этот список не содержит элемент.
  17. listIterator (int index): этот метод возвращает список-итератор элементов в этом списке (в правильной последовательности), начиная с указанной позиции в списке.
  18. offer (E e): этот метод добавляет указанный элемент как хвост (последний элемент) этого списка.
  19. offerFirst (E e): этот метод вставляет указанный элемент в начало этого списка.
  20. offerLast (E e): этот метод вставляет указанный элемент в конец этого списка.
  21. peek (): этот метод извлекает, но не удаляет заголовок (первый элемент) этого списка.
  22. peekFirst (): этот метод извлекает, но не удаляет первый элемент этого списка, или возвращает ноль, если этот список пуст.
  23. peekLast (): этот метод извлекает, но не удаляет последний элемент этого списка, или возвращает ноль, если этот список пуст.
  24. poll (): этот метод извлекает и удаляет заголовок (первый элемент) этого списка.
  25. pollFirst (): этот метод извлекает и удаляет первый элемент этого списка или возвращает ноль, если этот список пуст.
  26. pollLast (): этот метод извлекает и удаляет последний элемент этого списка или возвращает ноль, если этот список пуст.
  27. pop (): этот метод извлекает элемент из стека, представленного этим списком.
  28. push (E e): этот метод помещает элемент в стек, представленный этим списком.
  29. remove (): Этот метод извлекает и удаляет заголовок (первый элемент) этого списка.
  30. remove (int index): Этот метод удаляет элемент в указанной позиции в этом списке.
  31. remove (Object o): Этот метод удаляет первое вхождение указанного элемента из этого списка, если он присутствует.
  32. removeFirst (): этот метод удаляет и возвращает первый элемент из этого списка.
  33. removeFirstOccurrence (Object o): Этот метод удаляет первое вхождение указанного элемента в этом списке (при обходе списка от головы до хвоста).
  34. removeLast (): Этот метод удаляет и возвращает последний элемент из этого списка.
  35. removeLastOccurrence (Object o): Этот метод удаляет последнее вхождение указанного элемента в этом списке (при обходе списка от головы до хвоста).
  36. set (int index, E element) : Этот метод заменяет элемент в указанной позиции в этом списке указанным элементом.
  37. size (): этот метод возвращает количество элементов в этом списке.
  38. spliterator (): этот метод создает позднюю привязку и отказоустойчивый Spliterator для элементов в этом списке.
  39. toArray (): этот метод возвращает массив, содержащий все элементы в этом списке в правильной последовательности (от первого до последнего элемента).
  40. toArray (T [] a): этот метод возвращает массив, содержащий все элементы в этом списке в правильной последовательности (от первого до последнего элемента); тип времени выполнения возвращаемого массива является типом указанного массива.
Читать еще:  Arithmetic exception java

Эта статья предоставлена ​​Мехаком Нарангом.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Интерфейс Queue и классы

1. Интерфейс Queue

Интерфейс Queue расширяет Collection и объявляет поведение очередей, которые представляют собой список с дисциплиной «первый вошел первый вышел“ (FIFO). Существуют разные типы очередей, в которых порядок основан на некотором критерии. Очереди не могут хранить значения null.

Методы интерфейса Queue:

  1. Е element()— возвращает элемент из головы очереди. Элемент нe удаляется. Если очередь пуста, инициируется исключение NoSuchElementException.
  2. Е remove() — удаляет элемент из головы очереди, возвращая его. Инициирует исключение NoSuchElementException, если очередь пуста.
  3. Е peek() — возвращает элемент из головы очереди. Возвращает null, если очередь пуста. Элемент не удаляется.
  4. Е роll()— возвращает элемент из головы очереди и удаляет его. Возвращает null, если очередь пуста.
  5. boolean offer(Е оbj) — пытается добавить оbj в очередь. Возвращает true, если оbj добавлен, и false в противном случае.

Пример 1. Методы offer(), peek(), poll() интерфейса Queue

2. Интерфейс Deque

Интерфейс Deque появился в Java 6. Он расширяет Queue и описывает поведение двунаправленной очереди. Двунаправленная очередь может функционировать как стандартная очередь FIFO либо как стек LIFO.

Методы интерфейса Deque:

  1. void addFirst(Е obj)— добавляет obj в голову двунаправленной очереди. Возбуждает исключение IllegalStateException, если в очереди ограниченной емкости нет места.
  2. void addLast(Е obj)— добавляет obj в хвост двунаправленной очереди. Возбуждает исключение IllegalStateException, если в очереди ограниченной емкости нет места.
  3. Е getFirst()— возвращает первый элемент двунаправленной очереди. Объект из очереди не удаляется. В случае пустой двунаправленной очереди возбуждает исключение NoSuchElementException.
  4. Е getLast() — возвращает последний элемент двунаправленной очереди. Объект из очереди не удаляется. В случае пустой двунаправленной очереди возбуждает исключения NoSuchElementException.
  5. boolean offerFirst(Е obj) — пытается добавить obj в голову двунаправленной очереди. Возвращает true, если obj добавлен, и false в противном случае. Таким образом, этот метод возвращает false при попытке добавить obj в полную двунаправленную очередь ограниченной емкости.
  6. boolean offerLast(E obj) — пытается добавить obj в хвост двунаправленной очереди. Возвращает true, если obj добавлен, и false в против ном случае.
  7. Е рор() — возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возбуждает исключение NoSuchElementException, если очередь пуста.
  8. void push(Е obj) — добавляет элемент в голову двунаправленной очереди. Если в очереди фиксированного объема нет места, возбуждает исключение IllegalStateException.
  9. Е peekFirst() — возвращает элемент, находящийся в голове двунаправленной очереди. Возвращает null, если очередь пуста. Объект из очереди не удаляется.
  10. Е peekLast() — возвращает элемент, находящийся в хвосте двунаправленной очереди. Возвращает null, если очередь пуста. Объект из очереди не удаляется.
  11. Е pollFirst()— возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возвращает null, если очередь пуста.
  12. Е pollLast()— возвращает элемент, находящийся в хвосте двунаправленной очереди, одновременно удаляя его из очереди. Возвращает null, если очередь пуста.
  13. Е removeLast()— возвращает элемент, находящийся в конце двунаправленной очереди, удаляя его в процессе. Возбуждает исключение NoSuchElementException, если очередь пуста.
  14. Е removeFirst()— возвращает элемент, находящийся в голове двунаправленной очереди, одновременно удаляя его из очереди. Возбуждает исключение NoSuchElementException, если очередь пуста.
  15. boolean removeLastOccurrence(Object obj) — удаляет последнее вхождение obj из двунаправленной очереди. Возвращает true в случае успеха и false если очередь не содержала obj.
  16. boolean removeFirstOccurrence(Object obj) — удаляет первое вхождение obj из двунаправленной очереди. Возвращает true в случае успеха и false, если очередь не содержала obj.

3. Класс ArrayDeque

ArrayDeque создает двунаправленную очередь.

Конструкторы класса ArrayDeque:

  • ArrayDeque() — создает пустую двунаправленную очередь с вместимостью 16 элементов.
  • ArrayDeque(Collection c) — создает двунаправленную очередь из элементов коллекции c в том порядке, в котором они возвращаются итератором коллекции c.
  • ArrayDeque(int numElements) — создает пустую двунаправленную очередь с вместимостью numElements.

Пример 2. Использование класса ArrayDeque

4. Класс LinkedList

Класс LinkedList реализует интерфейсы List, Deque. LinkedList – это двухсвязный список.

Конструкторы класса LinkedList:

Внутри класса LinkedList существует static inner класс Entry, с помощью которого создаются новые элементы:

Ссылка на основную публикацию
Adblock
detector