Lista połączona jest częścią Ramy kolekcji obecny w pakiecie java.util . Ta klasa jest implementacją podwójnie połączonej struktury danych listowych.
Główna różnica między zwykłą listą połączoną a podwójnie połączoną listą polega na tym, że lista podwójnie połączona zawiera dodatkowy wskaźnik, zwykle nazywany poprzednim wskaźnikiem, wraz z następnym wskaźnikiem i danymi znajdującymi się na pojedynczo połączonej liście.
Konstruktorzy w LinkedList:
Aby stworzyć LinkedList musimy stworzyć obiekt klasy LinkedList. Klasa LinkedList składa się z różnych konstruktorów, które umożliwiają ewentualne utworzenie listy. Poniżej znajdują się konstruktory dostępne w tej klasie:
1. Połączona lista(): Ten konstruktor służy do tworzenia pustej listy połączonej. Jeśli chcemy utworzyć pustą listę LinkedList o nazwie ll, można ją utworzyć jako:
LinkedList ll = nowa LinkedList();
2. Połączona lista (kolekcja C): Ten konstruktor służy do tworzenia uporządkowanej listy zawierającej wszystkie elementy określonej kolekcji zwrócone przez iterator kolekcji. Jeśli chcemy utworzyć LinkedList o nazwie ll, można ją utworzyć jako:
LinkedList ll = nowa LinkedList(C);
Metody dla Java LinkedList:
| metoda | Opis |
|---|---|
| add(int indeks, element E) | Ta metoda wstawia określony element w określonej pozycji na tej liście. |
| dodaj (i i) | Ta metoda dołącza określony element na końcu tej listy. |
| addAll(int indeks, kolekcja c) | Ta metoda wstawia do tej listy wszystkie elementy z określonej kolekcji, zaczynając od określonej pozycji. |
| addAll(kolekcja c) | Ta metoda dołącza wszystkie elementy określonej kolekcji na koniec tej listy, w kolejności, w jakiej są zwracane przez iterator określonej kolekcji. |
| addFirst(E e) | Ta metoda wstawia określony element na początku tej listy. |
| dodajOstatni(E e) | Ta metoda dołącza określony element na końcu tej listy. |
| jasne() | Ta metoda usuwa wszystkie elementy z tej listy. |
| klon() | Ta metoda zwraca płytką kopię tej listy LinkedList. |
| zawiera (obiekt o) | Ta metoda zwraca wartość true, jeśli ta lista zawiera określony element. |
| malejącyIterator() | Ta metoda zwraca iterator po elementach w tym deque w odwrotnej kolejności. |
| element() | Ta metoda pobiera, ale nie usuwa, głowę (pierwszy element) tej listy. |
| pobierz (indeks int) | Ta metoda zwraca element na określonej pozycji na tej liście. |
| getFirst() | Ta metoda zwraca pierwszy element na tej liście. |
| pobierzOstatni() | Ta metoda zwraca ostatni element na tej liście. |
| indeksOf(Obiekt o) | Ta metoda zwraca indeks pierwszego wystąpienia określonego elementu na tej liście lub -1, jeśli ta lista nie zawiera tego elementu. |
| lastIndexOf(obiekt o) | Ta metoda zwraca indeks ostatniego wystąpienia określonego elementu na tej liście lub -1, jeśli ta lista nie zawiera tego elementu. |
| listIterator(int indeks) | Ta metoda zwraca iterator listy elementów na tej liście (w odpowiedniej kolejności), zaczynając od określonej pozycji na liście. |
| oferta(E e) | Ta metoda dodaje określony element jako koniec (ostatni element) tej listy. |
| ofertaPierwsza(E i) | Ta metoda wstawia określony element na początku tej listy. |
| ofertaOstatnia(E e) | Ta metoda wstawia określony element na końcu tej listy. |
| zerkać() | Ta metoda pobiera, ale nie usuwa, głowę (pierwszy element) tej listy. |
| spójrz najpierw() | Ta metoda pobiera, ale nie usuwa, pierwszy element tej listy lub zwraca wartość null, jeśli ta lista jest pusta. |
| zajrzyj do ostatniego() | Ta metoda pobiera, ale nie usuwa, ostatni element tej listy lub zwraca wartość null, jeśli ta lista jest pusta. |
| głosowanie() | Ta metoda pobiera i usuwa nagłówek (pierwszy element) tej listy. |
| pierwsza ankieta() | Ta metoda pobiera i usuwa pierwszy element tej listy lub zwraca wartość null, jeśli ta lista jest pusta. |
| ankietaOstatnia() | Ta metoda pobiera i usuwa ostatni element tej listy lub zwraca wartość null, jeśli ta lista jest pusta. |
| Muzyka pop() | Ta metoda Wyskakuje element ze stosu reprezentowanego przez tę listę. |
| naciśnij(E i) | Ta metoda wypycha element na stos reprezentowany przez tę listę. |
| usunąć() | Ta metoda pobiera i usuwa nagłówek (pierwszy element) tej listy. |
| usuń(indeks int) | Ta metoda usuwa element z określonej pozycji na tej liście. |
| usuń(obiekt o) | Ta metoda usuwa pierwsze wystąpienie określonego elementu z tej listy, jeśli jest obecne. |
| usuńFirst() | Ta metoda usuwa i zwraca pierwszy element z tej listy. |
| usuńFirstOccurrence(Obiekt o) | Ta metoda usuwa pierwsze wystąpienie określonego elementu na tej liście (podczas przechodzenia po liście od początku do końca). |
| usuńOstatnie() | Ta metoda usuwa i zwraca ostatni element z tej listy. |
| usuńLastOccurrence(Obiekt o) | Ta metoda usuwa ostatnie wystąpienie określonego elementu na tej liście (podczas przechodzenia po liście od początku do końca). |
| set(indeks int, element E) | Ta metoda zastępuje element znajdujący się na określonej pozycji na liście określonym elementem. |
| rozmiar() | Ta metoda zwraca liczbę elementów na tej liście. |
| rozdzielacz() | Ta metoda tworzy późno wiążący i niezawodny Spliterator dla elementów na tej liście. |
| do tablicy() | Metoda ta zwraca tablicę zawierającą wszystkie elementy tej listy w odpowiedniej kolejności (od pierwszego do ostatniego elementu). |
| doArray(T[]a) | Metoda ta zwraca tablicę zawierającą wszystkie elementy tej listy w odpowiedniej kolejności (od pierwszego do ostatniego elementu); typem środowiska wykonawczego zwróconej tablicy jest typ określonej tablicy. |
| doString() | Metoda ta zwraca ciąg zawierający wszystkie elementy z tej listy w odpowiedniej kolejności (od pierwszego do ostatniego elementu), każdy element oddzielamy przecinkami, a ciąg znaków ujęliśmy w nawiasy kwadratowe. |
Poniżej realizacja powyższych operacji:
Jawa
// 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);> >}> }> |
>
>Wyjście
[D, A, E, B, C] [A]>
Na powyższej ilustracji AbstractList, CopyOnWriteArrayList i AbstractSequentialList to klasy implementujące interfejs list. W każdej z wymienionych klas zaimplementowana jest osobna funkcjonalność. Oni są:
- AbstractList: Ta klasa służy do implementacji niemodyfikowalnej listy, dla której wystarczy rozszerzyć tę klasę AbstractList i zaimplementować tylko metody get() i size(). CopyOnWriteArrayList: Ta klasa implementuje interfejs listy. Jest to ulepszona wersja ArrayList, w której wszystkie modyfikacje (dodawanie, ustawianie, usuwanie itp.) są implementowane poprzez utworzenie nowej kopii listy.
Wykonywanie różnych operacji na LinkedList:
- Dodawanie elementów
- Aktualizacja elementów
- Usuwanie elementów
- Iterowanie po elementach
- Do tablicy();
- Rozmiar();
- usuń Najpierw();
- usuń ostatni();
Operacja 1: Dodawanie elementów
Aby dodać element do listy ArrayList, możemy skorzystać z metody add(). Ta metoda jest przeciążona, aby wykonać wiele operacji w oparciu o różne parametry. Oni są:
- add(Object): Ta metoda służy do dodawania elementu na końcu listy LinkedList. add(int indeks, obiekt): Ta metoda służy do dodawania elementu o określonym indeksie na liście LinkedList.
Poniżej implementacja powyższej operacji:
Jawa
// 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);> >}> }> |
>
>Wyjście
[Geeks, For, Geeks]>
Operacja 2: Zmiana elementów
Jeśli po dodaniu elementów będziemy chcieli zmienić element, można to zrobić za pomocą metody set(). Ponieważ lista LinkedList jest indeksowana, do elementu, który chcemy zmienić, odwołuje się indeks elementu. Dlatego ta metoda pobiera indeks i zaktualizowany element, który należy wstawić do tego indeksu.
Poniżej implementacja powyższej operacji:
Jawa
// 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);> >}> }> |
przeanalizuj ciąg znaków na int
>
>Wyjście
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Operacja 3: Usuwanie elementów
Aby usunąć element z listy LinkedList, możemy skorzystać z metody usuwania(). Ta metoda jest przeciążona, aby wykonać wiele operacji w oparciu o różne parametry. Oni są:
zajebisty język
- Remove(Object): Ta metoda służy do prostego usunięcia obiektu z LinkedList. Jeżeli takich obiektów jest wiele, to pierwsze wystąpienie obiektu jest usuwane. usuń(int indeks): Ponieważ lista LinkedList jest indeksowana, ta metoda przyjmuje wartość całkowitą, która po prostu usuwa element znajdujący się pod tym konkretnym indeksem na liście LinkedList. Po usunięciu elementu i indeksów elementów następuje aktualizacja, obiekt LinkedList jest aktualizowany dając nową Listę po usunięciu elementu/ów.
Poniżej implementacja powyższej operacji:
Jawa
// 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);> >}> }> |
>
>Wyjście
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Operacja 4: Iteracja listy połączonej
Istnieje wiele sposobów iteracji po LinkedList. Najbardziej znane sposoby to użycie podstawowej pętli for w połączeniu z metodą get() w celu uzyskania elementu o określonym indeksie oraz zaawansowana pętla for.
Poniżej implementacja powyższej operacji:
Jawa
// 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 + ' '); } }> |
>
>Wyjście
Geeks For Geeks Geeks For Geeks>
Operacja 4: Połączona lista z To Array za pomocą toArray();
Jawa
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+>' '>);> >}> }> |
>
>Wyjście
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Operacja 5-size();
Jawa
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());> >}> }> |
>
>Wyjście
The size of the linked list is: 2>
Operacja 7 – usuńFirst();
Jawa
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);> >}> }> |
>
>Wyjście
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Operacja 8- usuńostatnie();
Jawa
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);> >}> }> |
>
>Wyjście
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]>
Klasa LinkedList w Javie jest częścią Java Collections Framework i zapewnia implementację listy połączonej interfejsu List. Umożliwia przechowywanie i odzyskiwanie elementów w podwójnie połączonej strukturze danych listowych, gdzie każdy element jest powiązany ze swoim poprzednikiem i następcą.
Oto prosty przykład pokazujący, jak używać listy LinkedList w Javie:
Jawa
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);> >}> >}> }> |
>
>
lista niezmienna JavaWyjście
0 1 2 3 4>
Zalety korzystania z LinkedList w Javie:
- Rozmiar dynamiczny: Podobnie jak w przypadku wektora, rozmiar listy LinkedList może dynamicznie rosnąć lub zmniejszać się, więc nie musisz się martwić o ustawienie rozmiaru początkowego.
- Efektywne wstawianie i usuwanie: LinkedList to wydajna struktura danych do wstawiania lub usuwania elementów na środku listy, ponieważ wystarczy zmienić tylko połączenia między elementami, a nie przesuwać wszystkie elementy po punkcie wstawiania lub usuwania.
- Elastyczna iteracja: dzięki połączonej liście możesz efektywnie iterować po liście w dowolnym kierunku, ponieważ każdy element ma odniesienie zarówno do swojego poprzednika, jak i następcy.
Wady korzystania z LinkedList w Javie:
- Wydajność: LinkedList ma mniejszą wydajność niż ArrayList, jeśli chodzi o dostęp do poszczególnych elementów. Dzieje się tak dlatego, że musisz przejść przez listę, aby dotrzeć do żądanego elementu, podczas gdy w przypadku ArrayList możesz po prostu uzyskać dostęp do żądanego elementu za pomocą indeksu.
- Obciążenie pamięci: LinkedList wymaga więcej pamięci niż ArrayList, ponieważ każdy element wymaga dodatkowej pamięci dla łączy do swoich poprzedników i następników.
Książka referencyjna:
Dobrym podręcznikiem do nauki o Java Collections Framework i LinkedList jest Java Collections autorstwa Naftalina i Wadlera. Książka ta zapewnia kompleksowe spojrzenie na framework kolekcji Java, w tym LinkedList, oraz zawiera wiele przykładów i ćwiczeń, które pomogą Ci zrozumieć, jak efektywnie korzystać z tych klas.