Bazaprogram.ru

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

Java linkedlist пример

LinkedList в Java

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

В 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): этот метод возвращает массив, содержащий все элементы в этом списке в правильной последовательности (от первого до последнего элемента); тип времени выполнения возвращаемого массива является типом указанного массива.

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

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

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

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

Читать еще:  Javascript return function

Конструкторы 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 in Java with Example

By Chaitanya Singh | Filed Under: Java Collections

Similar to arrays in Java, LinkedList is a linear data structure. However LinkedList elements are not stored in contiguous locations like arrays, they are linked with each other using pointers. Each element of the LinkedList has the reference(address/pointer) to the next element of the LinkedList.

Table of Contents

LinkedList representation

Each element in the LinkedList is called the Node. Each Node of the LinkedList contains two items: 1) Content of the element 2) Pointer/Address/Reference to the Next Node in the LinkedList.

This is how a LinkedList looks:

Note:
1. Head of the LinkedList only contains the Address of the First element of the List.
2. The Last element of the LinkedList contains null in the pointer part of the node because it is the end of the List so it doesn’t point to anything as shown in the above diagram.
3. The diagram which is shown above represents a singly linked list. There is another complex type variation of LinkedList which is called doubly linked list, node of a doubly linked list contains three parts: 1) Pointer to the previous node of the linked list 2) content of the element 3) pointer to the next node of the linked list.

Why do we need a Linked List?

You must be aware of the arrays which is also a linear data structure but arrays have certain limitations such as:
1) Size of the array is fixed which is decided when we create an array so it is hard to predict the number of elements in advance, if the declared size fall short then we cannot increase the size of an array and if we declare a large size array and do not need to store that many elements then it is a waste of memory.

2) Array elements need contiguous memory locations to store their values.

3) Inserting an element in an array is performance wise expensive as we have to shift several elements to make a space for the new element. For example:
Let’s say we have an array that has following elements: 10, 12, 15, 20, 4, 5, 100, now if we want to insert a new element 99 after the element that has value 12 then we have to shift all the elements after 12 to their right to make space for new element.

Similarly deleting an element from the array is also a performance wise expensive operation because all the elements after the deleted element have to be shifted left.

These limitations are handled in the Linked List by providing following features:
1. Linked list allows dynamic memory allocation, which means memory allocation is done at the run time by the compiler and we do not need to mention the size of the list during linked list declaration.

2. Linked list elements don’t need contiguous memory locations because elements are linked with each other using the reference part of the node that contains the address of the next node of the list.

3. Insert and delete operations in the Linked list are not performance wise expensive because adding and deleting an element from the linked list does’t require element shifting, only the pointer of the previous and the next node requires change.

Читать еще:  Класс scanner java

Hierarchy of LinkedList class in Java

Java Linked List example of adding elements

In the following example we are using add() , addFirst() and addLast() methods to add the elements at the desired locations in the LinkedList, there are several such useful methods in the LinkedList class which I have mentioned at the end of this article.

Output:

Java example of removing elements from the LinkedList

In the following example we are checking out the few popular remove methods in the LinkedList that are used to remove elements from certain positions in the LinkedList. Detailed explanation of these methods along with examples are covered in the separate tutorials, links are provided at the end of this article.

Output:

Example of LinkedList in Java

Methods of LinkedList class:

Here I have mentioned the brief description of the LinkedList methods, I have covered each one of these methods in separate tutorials, links are provided at the end of this article.

For all the examples in the below methods, consider llistobj as a reference for LinkedList .

LinkedList llistobj = new LinkedList ();

1) boolean add(Object item): It adds the item at the end of the list.

It would add the string “Hello” at the end of the linked list.

2) void add(int index, Object item): It adds an item at the given index of the the list.

This will add the string “bye” at the 3rd position( 2 index is 3rd position as index starts with 0).

3) boolean addAll(Collection c): It adds all the elements of the specified collection c to the list. It throws NullPointerException if the specified collection is null. Consider the below example –

This piece of code would add all the elements of ArrayList to the LinkedList.

4) boolean addAll(int index, Collection c): It adds all the elements of collection c to the list starting from a give index in the list. It throws NullPointerException if the collection c is null and IndexOutOfBoundsException when the specified index is out of the range.

It would add all the elements of the ArrayList to the LinkedList starting from position 6 (index 5).

5) void addFirst(Object item): It adds the item (or element) at the first position in the list.

It would add the string “text” at the beginning of the list.

6) void addLast(Object item): It inserts the specified item at the end of the list.

This statement will add a string “Chaitanya” at the end position of the linked list.

7) void clear(): It removes all the elements of a list.

8) Object clone(): It returns the copy of the list.

For e.g. My linkedList has four items: text1, text2, text3 and text4.

Output: The output of above code would be:

[text1, text2, text3, text4]

9) boolean contains(Object item): It checks whether the given item is present in the list or not. If the item is present then it returns true else false.

It will check whether the string “TestString” exist in the list or not.

10) Object get(int index): It returns the item of the specified index from the list.

It will fetch the 3rd item from the list.

11) Object getFirst(): It fetches the first item from the list.

12) Object getLast(): It fetches the last item from the list.

13) int indexOf(Object item): It returns the index of the specified item.

14) int lastIndexOf(Object item): It returns the index of last occurrence of the specified element.

integer variable pos will be having the index of last occurrence of string “hello”.

15) Object poll(): It returns and removes the first item of the list.

16) Object pollFirst(): same as poll() method. Removes the first item of the list.

17) Object pollLast(): It returns and removes the last element of the list.

18) Object remove(): It removes the first element of the list.

19) Object remove(int index): It removes the item from the list which is present at the specified index.

It will remove the 5th element from the list.

20) Object remove(Object obj): It removes the specified object from the list.

21) Object removeFirst(): It removes the first item from the list.

22) Object removeLast(): It removes the last item of the list.

23) Object removeFirstOccurrence(Object item): It removes the first occurrence of the specified item.

It will remove the first occurrence of the string “text” from the list.

24) Object removeLastOccurrence(Object item): It removes the last occurrence of the given element.

It will remove the last occurrence of string “String1”.

25) Object set(int index, Object item): It updates the item of specified index with the give value.

It will update the 3rd element with the string “Test”.

26) int size(): It returns the number of elements of the list.

LinkedList Tutorials

Here are the tutorials that I have shared on 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.

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

Добавление элементов

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).

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

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

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

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

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

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

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

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

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

Вопросы и ответы

Где можно попрактиковать Java Stream API?

Выбор среды и движка?

Каким образом лучше реализовать фронтэнд онлайн сервиса с бэкэндом на Java?

Как правильно располагать виджеты на экране в Andro > Java Простой 1 ответ

Как выбрать между C# и Java?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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