Зв’язаний список є частиною Рамка колекції присутній у пакеті java.util. Цей клас є реалізацією структури даних двозв'язаного списку.
Основна відмінність між звичайним зв’язаним списком і подвійно зв’язаним списком полягає в тому, що подвійно зв’язаний список містить додатковий вказівник, який зазвичай називається попереднім вказівником, разом із наступним вказівником і даними, які містяться в однозв’язаному списку.
Конструктори в LinkedList:
Щоб створити LinkedList, нам потрібно створити об’єкт класу LinkedList. Клас LinkedList складається з різних конструкторів, які дозволяють створювати список. У цьому класі доступні такі конструктори:
1. LinkedList(): Цей конструктор використовується для створення порожнього зв’язаного списку. Якщо ми хочемо створити порожній LinkedList з іменем ll, тоді його можна створити так:
LinkedList ll = новий LinkedList();
2. LinkedList (колекція C): Цей конструктор використовується для створення впорядкованого списку, який містить усі елементи вказаної колекції, що повертається ітератором колекції. Якщо ми хочемо створити LinkedList з іменем ll, тоді його можна створити так:
LinkedList ll = новий LinkedList(C);
Методи для Java LinkedList:
| метод | опис |
|---|---|
| add(int index, E element) | Цей метод вставляє вказаний елемент у вказану позицію в цьому списку. |
| додати (І і) | Цей метод додає вказаний елемент у кінець цього списку. |
| addAll(int index, Collection c) | Цей метод вставляє всі елементи вказаної колекції в цей список, починаючи з указаної позиції. |
| addAll(Collection c) | Цей метод додає всі елементи вказаної колекції в кінець цього списку в тому порядку, у якому їх повертає ітератор зазначеної колекції. |
| addFirst(E e) | Цей метод вставляє вказаний елемент на початку цього списку. |
| addLast(E e) | Цей метод додає вказаний елемент у кінець цього списку. |
| очистити() | Цей метод видаляє всі елементи зі списку. |
| клонувати() | Цей метод повертає поверхневу копію цього LinkedList. |
| містить (об'єкт o) | Цей метод повертає true, якщо цей список містить вказаний елемент. |
| descendingIterator() | Цей метод повертає ітератор для елементів у цій двоканальній послідовності у зворотному порядку. |
| елемент() | Цей метод отримує, але не видаляє заголовок (перший елемент) цього списку. |
| отримати (індекс індексу) | Цей метод повертає елемент у вказаній позиції в цьому списку. |
| getFirst() | Цей метод повертає перший елемент у цьому списку. |
| getLast() | Цей метод повертає останній елемент у цьому списку. |
| indexOf(Об'єкт o) | Цей метод повертає індекс першого входження зазначеного елемента в цьому списку або -1, якщо цей список не містить елемент. |
| lastIndexOf(Object o) | Цей метод повертає індекс останнього входження зазначеного елемента в цьому списку або -1, якщо цей список не містить елемент. |
| listIterator(індекс int) | Цей метод повертає список-ітератор елементів цього списку (у належній послідовності), починаючи з указаної позиції у списку. |
| пропозиція (E e) | Цей метод додає вказаний елемент як хвіст (останній елемент) цього списку. |
| offerFirst(E і) | Цей метод вставляє вказаний елемент на початку цього списку. |
| пропозиціяОстання(E e) | Цей метод вставляє вказаний елемент у кінець цього списку. |
| peek() | Цей метод отримує, але не видаляє заголовок (перший елемент) цього списку. |
| peekFirst() | Цей метод отримує, але не видаляє, перший елемент цього списку або повертає null, якщо цей список порожній. |
| peekLast() | Цей метод отримує, але не видаляє, останній елемент цього списку або повертає null, якщо цей список порожній. |
| опитування() | Цей метод отримує та видаляє заголовок (перший елемент) цього списку. |
| pollFirst() | Цей метод отримує та видаляє перший елемент цього списку або повертає null, якщо цей список порожній. |
| pollLast() | Цей метод отримує та видаляє останній елемент цього списку або повертає значення null, якщо цей список порожній. |
| поп() | Цей метод витягує елемент зі стеку, представленого цим списком. |
| push(E і) | Цей метод поміщає елемент у стек, представлений цим списком. |
| видалити() | Цей метод отримує та видаляє заголовок (перший елемент) цього списку. |
| видалити (індекс) | Цей метод видаляє елемент у вказаній позиції в цьому списку. |
| видалити (об'єкт o) | Цей метод видаляє перше входження зазначеного елемента зі списку, якщо він присутній. |
| removeFirst() | Цей метод видаляє та повертає перший елемент зі списку. |
| removeFirstOccurrence(Object o) | Цей метод видаляє перше входження зазначеного елемента в цьому списку (під час обходу списку від початку до кінця). |
| removeLast() | Цей метод видаляє та повертає останній елемент зі списку. |
| removeLastOccurrence(Object o) | Цей метод видаляє останнє входження зазначеного елемента в цьому списку (під час обходу списку від початку до кінця). |
| set(int index, E element) | Цей метод замінює елемент у вказаній позиції в цьому списку вказаним елементом. |
| розмір() | Цей метод повертає кількість елементів у цьому списку. |
| spliterator() | Цей метод створює над елементами в цьому списку сплітатор із пізнім прив’язуванням і швидким відмовою. |
| toArray() | Цей метод повертає масив, що містить усі елементи цього списку в належній послідовності (від першого до останнього елемента). |
| toArray(T[] a) | Цей метод повертає масив, що містить усі елементи цього списку в належній послідовності (від першого до останнього елемента); тип середовища виконання поверненого масиву – це тип зазначеного масиву. |
| toString() | Цей метод повертає рядок, що містить усі елементи цього списку в правильній послідовності (від першого до останнього елемента), кожен елемент розділений комами, а рядок укладено в квадратні дужки. |
Нижче наведено виконання вищевказаних операцій:
Java
// Java Program to Demonstrate> // Implementation of LinkedList> // class> > // Importing required classes> import> java.util.*;> > // Main class> public> class> GFG {> > >// Driver code> >public> static> void> main(String args[])> >{> >// Creating object of the> >// class linked list> >LinkedList ll =>new> LinkedList();> > >// Adding elements to the linked list> >ll.add(>'A'>);> >ll.add(>'B'>);> >ll.addLast(>'C'>);> >ll.addFirst(>'D'>);> >ll.add(>2>,>'E'>);> > >System.out.println(ll);> > >ll.remove(>'B'>);> >ll.remove(>3>);> >ll.removeFirst();> >ll.removeLast();> > >System.out.println(ll);> >}> }> |
>
>Вихід
[D, A, E, B, C] [A]>
На наведеній вище ілюстрації AbstractList, CopyOnWriteArrayList і AbstractSequentialList є класами, які реалізують інтерфейс списку. У кожному із зазначених класів реалізована окрема функціональність. Вони є:
- AbstractList: цей клас використовується для реалізації незмінюваного списку, для якого потрібно лише розширити цей клас AbstractList і реалізувати лише методи get() і size(). CopyOnWriteArrayList: цей клас реалізує інтерфейс списку. Це вдосконалена версія ArrayList, у якій усі зміни (додавання, встановлення, видалення тощо) реалізуються шляхом створення нової копії списку.
Виконання різних операцій над LinkedList:
- Додавання елементів
- Оновлення елементів
- Видалення елементів
- Ітерація елементів
- До масиву();
- Розмір();
- видалити First();
- видалити останній();
Операція 1: Додавання елементів
Щоб додати елемент до ArrayList, ми можемо використати метод add(). Цей метод перевантажений для виконання кількох операцій на основі різних параметрів. Вони є:
- add(Object): Цей метод використовується для додавання елемента в кінець LinkedList. add(int index, Object): цей метод використовується для додавання елемента за певним індексом у LinkedList.
Нижче наведено виконання описаної вище операції:
Java
// Java program to add elements> // to a LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll =>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'For'>);> > >System.out.println(ll);> >}> }> |
>
>Вихід
[Geeks, For, Geeks]>
Операція 2: Зміна елементів
Після додавання елементів, якщо ми хочемо змінити елемент, це можна зробити за допомогою методу set(). Оскільки LinkedList індексується, на елемент, який ми хочемо змінити, посилається індекс елемента. Таким чином, цей метод приймає індекс і оновлений елемент, який потрібно вставити в цей індекс.
Нижче наведено виконання описаної вище операції:
Java
// Java program to change elements> // in a LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll =>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'Geeks'>);> > >System.out.println(>'Initial LinkedList '> + ll);> > >ll.set(>1>,>'For'>);> > >System.out.println(>'Updated LinkedList '> + ll);> >}> }> |
формат рядка в java
>
>Вихід
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Операція 3: Видалення елементів
Щоб видалити елемент із LinkedList, ми можемо використати метод remove(). Цей метод перевантажений для виконання кількох операцій на основі різних параметрів. Вони є:
- remove(Object): цей метод використовується для простого видалення об’єкта зі списку LinkedList. Якщо таких об’єктів декілька, видаляється перший випадок об’єкта. remove(int index): Оскільки LinkedList індексується, цей метод приймає ціле число, яке просто видаляє елемент, присутній у цьому конкретному індексі LinkedList. Після видалення елемента й індекси елементів оновлюються, а також об’єкт LinkedList оновлюється, створюючи новий список після видалення елемента/ів.
Нижче наведено виконання описаної вище операції:
Java
// Java program to remove elements> // in a LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll =>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'For'>);> > >System.out.println(>'Initial LinkedList '> + ll);> > >// Function call> >ll.remove(>1>);> > >System.out.println(>'After the Index Removal '> + ll);> > >ll.remove(>'Geeks'>);> > >System.out.println(>'After the Object Removal '> >+ ll);> >}> }> |
>
>Вихід
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Операція 4: Ітерація LinkedList
Є кілька способів ітерації через LinkedList. Найвідомішими способами є використання базового циклу for у поєднанні з методом get() для отримання елемента за певним індексом і розширений цикл for.
Нижче наведено виконання описаної вище операції:
Java
функція прототипу c++
// Java program to iterate the elements> // in an LinkedList> > import> java.util.*;> > public> class> GFG {> > >public> static> void> main(String args[])> >{> >LinkedList ll> >=>new> LinkedList();> > >ll.add(>'Geeks'>);> >ll.add(>'Geeks'>);> >ll.add(>1>,>'For'>);> > >// Using the Get method and the> >// for loop> >for> (>int> i =>0>; i System.out.print(ll.get(i) + ' '); } System.out.println(); // Using the for each loop for (String str : ll) System.out.print(str + ' '); } }> |
>
>Вихід
Geeks For Geeks Geeks For Geeks>
Операція 4: Зв’язаний список із To Array за допомогою toArray();
Java
import> java.util.*;> public> class> GFG2 {> >public> static> void> main(String[] args)> >{> >LinkedList list=>new> LinkedList();> >list.add(>123>);> >list.add(>12>);> >list.add(>11>);> >list.add(>1134>);> >System.out.println(>'LinkedList: '>+ list);> >Object[] a = list.toArray();> >System.out.print(>'After converted LinkedList to Array: '>);> >for>(Object element : a)> >System.out.print(element+>' '>);> >}> }> |
>
>Вихід
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Операція 5-size();
Java
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> >public> static> void> main(String args[]) {> >LinkedList list =>new> LinkedList();> >list.add(>'Geeks for Geeks '>);> >list.add(>'is best '>);> >// Displaying the size of the list> >System.out.println(>'The size of the linked list is: '> + list.size());> >}> }> |
>
>Вихід
The size of the linked list is: 2>
Операція 7 – removeFirst();
Java
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> >public> static> void> main(String args[]) {> > >LinkedList list =>new> LinkedList();> >list.add(>10>);> >list.add(>20>);> >list.add(>30>);> >System.out.println(>'LinkedList:'> + list);> >System.out.println(>'The remove first element is: '> + list.removeFirst());> >// Displaying the final list> >System.out.println(>'Final LinkedList:'> + list);> >}> }> |
>
верхній індекс в ілюстраторі
>Вихід
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Операція 8- removelast();
Java
import> java.io.*;> import> java.util.LinkedList;> public> class> GFG2 {> >public> static> void> main(String args[])> >{> > >LinkedList list =>new> LinkedList();> >list.add(>10>);> >list.add(>20>);> >list.add(>30>);> >System.out.println(>'LinkedList:'> + list);> >// Remove the tail using removeLast()> >System.out.println(>'The last element is removed: '> + list.removeLast());> >// Displaying the final list> >System.out.println(>'Final LinkedList:'> + list);> >// Remove the tail using removeLast()> >System.out.println(>'The last element is removed: '> + list.removeLast());> >// Displaying the final list> >System.out.println(>'Final LinkedList:'> + list);> >}> }> |
>
>Вихід
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]>
Клас LinkedList у Java є частиною Java Collections Framework і забезпечує реалізацію пов’язаного списку інтерфейсу List. Це дозволяє зберігати та отримувати елементи в структурі даних подвійно зв’язаного списку, де кожен елемент пов’язаний зі своїми попередніми та наступними елементами.
Ось простий приклад, який демонструє, як використовувати LinkedList у Java:
Java
import> java.util.LinkedList;> > public> class> LinkedListExample {> >public> static> void> main(String[] args) {> >// Create a new linked list> >LinkedList linkedList =>new> LinkedList();> > >// Add elements to the linked list> >linkedList.add(>1>);> >linkedList.add(>2>);> >linkedList.add(>3>);> > >// Add an element to the beginning of the linked list> >linkedList.addFirst(>0>);> > >// Add an element to the end of the linked list> >linkedList.addLast(>4>);> > >// Print the elements of the linked list> >for> (>int> i : linkedList) {> >System.out.println(i);> >}> >}> }> |
>
>Вихід
0 1 2 3 4>
Переваги використання LinkedList у Java:
- Динамічний розмір: як і у випадку з вектором, розмір LinkedList може динамічно збільшуватися або зменшуватися, тому вам не доведеться турбуватися про встановлення початкового розміру.
- Ефективні вставки та видалення: LinkedList — це ефективна структура даних для вставки або видалення елементів у середині списку, оскільки вам потрібно лише змінити зв’язки між елементами, а не зміщувати всі елементи після точки вставки чи видалення.
- Гнучка ітерація: зі зв’язаним списком ви можете ефективно ітерувати список у будь-якому напрямку, оскільки кожен елемент має посилання як на попередні, так і на наступні елементи.
Недоліки використання LinkedList у Java:
- Продуктивність: LinkedList має нижчу продуктивність, ніж ArrayList, коли йдеться про доступ до окремих елементів. Це пояснюється тим, що вам потрібно пройти список, щоб дістатися до потрібного елемента, тоді як за допомогою ArrayList ви можете просто отримати доступ до потрібного елемента за допомогою індексу.
- Витрати пам’яті: LinkedList потребує більше пам’яті, ніж ArrayList, оскільки кожен елемент потребує додаткової пам’яті для посилань на його попередні та наступні елементи.
Довідник:
Хорошим довідником для вивчення Java Collections Framework і LinkedList є Java Collections від Naftalin і Wadler. У цій книзі представлено комплексний погляд на структуру колекцій Java, включаючи LinkedList, і містить багато прикладів і вправ, які допоможуть вам зрозуміти, як ефективно використовувати ці класи.