Linked List je součástí Kolektivní rámec přítomný v balíčku java.util . Tato třída je implementací dvojitě propojené datové struktury seznamu.
Hlavní rozdíl mezi normálním propojeným seznamem a dvojitě propojeným seznamem je ten, že dvojitě propojený seznam obsahuje další ukazatel, který se obvykle nazývá předchozí ukazatel, spolu s dalším ukazatelem a daty, která jsou v jednoduše propojeném seznamu.
Konstruktoři v LinkedList:
Abychom mohli vytvořit LinkedList, musíme vytvořit objekt třídy LinkedList. Třída LinkedList se skládá z různých konstruktorů, které umožňují případné vytvoření seznamu. V této třídě jsou k dispozici následující konstruktory:
1. Spojový seznam(): Tento konstruktor se používá k vytvoření prázdného propojeného seznamu. Pokud chceme vytvořit prázdný LinkedList s názvem ll, lze jej vytvořit jako:
LinkedList ll = new LinkedList();
2. LinkedList (kolekce C): Tento konstruktor se používá k vytvoření uspořádaného seznamu, který obsahuje všechny prvky zadané kolekce, jak je vrací iterátor kolekce. Pokud chceme vytvořit LinkedList s názvem ll, pak může být vytvořen jako:
LinkedList ll = new LinkedList(C);
Metody pro Java LinkedList:
| Metoda | Popis |
|---|---|
| add(int index, prvek E) | Tato metoda Vloží zadaný prvek na zadané místo v tomto seznamu. |
| přidat (a a) | Tato metoda Připojí zadaný prvek na konec tohoto seznamu. |
| addAll(int index, kolekce c) | Tato metoda Vloží všechny prvky v zadané kolekci do tohoto seznamu počínaje zadanou pozicí. |
| addAll(kolekce c) | Tato metoda připojí všechny prvky v zadané kolekci na konec tohoto seznamu v pořadí, v jakém jsou vráceny iterátorem zadané kolekce. |
| addFirst (E e) | Tato metoda Vloží zadaný prvek na začátek tohoto seznamu. |
| addLast(E e) | Tato metoda Připojí zadaný prvek na konec tohoto seznamu. |
| Průhledná() | Tato metoda odstraní všechny prvky z tohoto seznamu. |
| klon() | Tato metoda vrací mělkou kopii tohoto LinkedList. |
| obsahuje (Objekt o) | Tato metoda vrátí hodnotu true, pokud tento seznam obsahuje zadaný prvek. |
| descendingIterator() | Tato metoda vrací iterátor nad prvky v tomto deque v obráceném pořadí. |
| živel() | Tato metoda načte, ale neodstraní hlavičku (první prvek) tohoto seznamu. |
| get(int index) | Tato metoda vrátí prvek na zadanou pozici v tomto seznamu. |
| getFirst() | Tato metoda vrátí první prvek v tomto seznamu. |
| getLast() | Tato metoda vrací poslední prvek v tomto seznamu. |
| indexOf(Objekt o) | Tato metoda vrátí index prvního výskytu zadaného prvku v tomto seznamu nebo -1, pokud tento seznam prvek neobsahuje. |
| lastIndexOf(Objekt o) | Tato metoda vrací index posledního výskytu zadaného prvku v tomto seznamu nebo -1, pokud tento seznam prvek neobsahuje. |
| listIterator(int index) | Tato metoda vrací iterátor seznamu prvků v tomto seznamu (ve správném pořadí), počínaje od zadané pozice v seznamu. |
| nabídka (E e) | Tato metoda Přidá zadaný prvek jako konec (poslední prvek) tohoto seznamu. |
| nabídka první (E a) | Tato metoda Vloží určený prvek na začátek tohoto seznamu. |
| poslední nabídka (E e) | Tato metoda Vloží zadaný prvek na konec tohoto seznamu. |
| nahlédnout () | Tato metoda načte, ale neodstraní hlavičku (první prvek) tohoto seznamu. |
| peekFirst() | Tato metoda načte, ale neodstraní první prvek tohoto seznamu, nebo vrátí hodnotu null, pokud je tento seznam prázdný. |
| peekLast() | Tato metoda načte, ale neodstraní poslední prvek tohoto seznamu, nebo vrátí hodnotu null, pokud je tento seznam prázdný. |
| hlasování() | Tato metoda načte a odstraní hlavičku (první prvek) tohoto seznamu. |
| pollFirst() | Tato metoda načte a odstraní první prvek tohoto seznamu nebo vrátí hodnotu null, pokud je tento seznam prázdný. |
| pollLast() | Tato metoda načte a odstraní poslední prvek tohoto seznamu nebo vrátí hodnotu null, pokud je tento seznam prázdný. |
| pop() | Tato metoda Vybere prvek ze zásobníku reprezentovaného tímto seznamem. |
| tlačit (E a) | Tato metoda vloží prvek do zásobníku reprezentovaného tímto seznamem. |
| odstranit() | Tato metoda načte a odstraní hlavičku (první prvek) tohoto seznamu. |
| odstranit (int index) | Tato metoda odstraní prvek na zadané pozici v tomto seznamu. |
| odstranit (objekt o) | Tato metoda odstraní první výskyt zadaného prvku z tohoto seznamu, pokud je přítomen. |
| removeFirst() | Tato metoda odstraní a vrátí první prvek z tohoto seznamu. |
| removeFirstOccurrence(Object o) | Tato metoda odstraní první výskyt zadaného prvku v tomto seznamu (při procházení seznamu od hlavy k patě). |
| removeLast() | Tato metoda odstraní a vrátí poslední prvek z tohoto seznamu. |
| removeLastOccurrence(Object o) | Tato metoda odstraní poslední výskyt zadaného prvku v tomto seznamu (při procházení seznamu od hlavy k patě). |
| set(int index, prvek E) | Tato metoda nahradí prvek na zadané pozici v tomto seznamu zadaným prvkem. |
| velikost() | Tato metoda vrací počet prvků v tomto seznamu. |
| rozdělovač() | Tato metoda vytvoří nad prvky v tomto seznamu spliterator s pozdní vazbou a rychlým selháním. |
| toArray() | Tato metoda vrací pole obsahující všechny prvky v tomto seznamu ve správném pořadí (od prvního po poslední prvek). |
| toArray(T[] a) | Tato metoda vrací pole obsahující všechny prvky v tomto seznamu ve správném pořadí (od prvního po poslední prvek); typ runtime vráceného pole je typ zadaného pole. |
| toString() | Tato metoda vrací řetězec obsahující všechny prvky v tomto seznamu ve správném pořadí (od prvního po poslední prvek), každý prvek je oddělen čárkami a řetězec je uzavřen v hranatých závorkách. |
Níže je uvedena implementace výše uvedených operací:
Jáva
// 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);> >}> }> |
>
>Výstup
[D, A, E, B, C] [A]>
Na obrázku výše jsou AbstractList , CopyOnWriteArrayList a AbstractSequentialList třídy, které implementují rozhraní seznamu. V každé ze zmíněných tříd je implementována samostatná funkcionalita. Oni jsou:
- AbstractList: Tato třída se používá k implementaci nemodifikovatelného seznamu, pro který je potřeba pouze rozšířit tuto třídu AbstractList a implementovat pouze metody get() a size(). CopyOnWriteArrayList: Tato třída implementuje rozhraní seznamu. Je to vylepšená verze ArrayList, ve které jsou všechny úpravy (přidat, nastavit, odebrat atd.) implementovány vytvořením nové kopie seznamu.
Provádění různých operací na LinkedList:
- Přidávání prvků
- Aktualizace prvků
- Odstraňování prvků
- Iterování přes prvky
- To Array();
- Velikost();
- remove First();
- remove last();
Operace 1: Přidávání prvků
Abychom přidali prvek do ArrayList, můžeme použít metodu add() . Tato metoda je přetížena prováděním více operací na základě různých parametrů. Oni jsou:
- add(Object): Tato metoda se používá k přidání prvku na konec LinkedList. add(int index, Object): Tato metoda se používá k přidání prvku do určitého indexu v LinkedList.
Níže je uvedena implementace výše uvedené operace:
Jáva
// 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);> >}> }> |
>
>Výstup
[Geeks, For, Geeks]>
Operace 2: Změna prvků
Po přidání prvků, pokud chceme prvek změnit, lze to provést pomocí metody set() . Protože LinkedList je indexován, na prvek, který chceme změnit, se odkazuje index prvku. Proto tato metoda bere index a aktualizovaný prvek, který je třeba vložit do tohoto indexu.
Níže je uvedena implementace výše uvedené operace:
Jáva
// 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);> >}> }> |
hašování v datové struktuře
>
>Výstup
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Operace 3: Odebírání prvků
Abychom odstranili prvek z LinkedList, můžeme použít metodu remove() . Tato metoda je přetížena prováděním více operací na základě různých parametrů. Oni jsou:
- remove(Object): Tato metoda se používá k jednoduchému odstranění objektu z LinkedList. Pokud existuje více takových objektů, pak se první výskyt objektu odstraní. remove(int index): Protože je LinkedList indexován, tato metoda přebírá celočíselnou hodnotu, která jednoduše odstraní prvek přítomný na tomto konkrétním indexu v LinkedList. Po odstranění prvku a indexů prvků se aktualizuje, stejně jako se aktualizuje objekt LinkedList a po smazání prvku/ů se získá nový seznam.
Níže je uvedena implementace výše uvedené operace:
Jáva
// 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);> >}> }> |
>
>Výstup
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Operace 4: Iterace LinkedList
Existuje několik způsobů, jak iterovat přes LinkedList. Nejznámějšími způsoby je použití základní smyčky for v kombinaci s metodou get() k získání prvku na konkrétním indexu a pokročilé smyčky for.
Níže je uvedena implementace výše uvedené operace:
Jáva
// 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 + ' '); } }> |
>
>Výstup
Geeks For Geeks Geeks For Geeks>
Operace 4: Propojený seznam s To Array pomocí toArray();
Jáva
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+>);> >}> }> |
>
porovnání řetězců v Javě
>Výstup
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Operace 5-size();
Jáva
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());> >}> }> |
>
>Výstup
The size of the linked list is: 2>
Operace 7 – removeFirst();
Jáva
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);> >}> }> |
>
>Výstup
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Operace 8- removelast();
Jáva
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);> >}> }> |
>
>Výstup
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]>
Třída LinkedList v Javě je součástí Java Collections Framework a poskytuje implementaci propojeného seznamu rozhraní List. Umožňuje ukládání a načítání prvků ve dvojitě propojené datové struktuře seznamu, kde je každý prvek propojen se svými předchůdci a následovníky.
Zde je jednoduchý příklad, který ukazuje, jak používat LinkedList v Javě:
Jáva
runas v powershell
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);> >}> >}> }> |
>
>Výstup
0 1 2 3 4>
Výhody použití LinkedList v Javě:
- Dynamická velikost: Stejně jako u Vector může velikost LinkedList dynamicky růst nebo zmenšovat, takže se nemusíte starat o nastavení počáteční velikosti.
- Efektivní vkládání a mazání: LinkedList je efektivní datová struktura pro vkládání nebo mazání prvků uprostřed seznamu, protože potřebujete pouze změnit vazby mezi prvky, nikoli posouvat všechny prvky za bod vložení nebo odstranění.
- Flexibilní iterace: S propojeným seznamem můžete efektivně iterovat seznamem v obou směrech, protože každý prvek má odkaz na své předchůdce i následovníky.
Nevýhody používání LinkedList v Javě:
- Výkon: LinkedList má pomalejší výkon než ArrayList, pokud jde o přístup k jednotlivým prvkům. Je to proto, že musíte procházet seznamem, abyste dosáhli požadovaného prvku, zatímco s ArrayList můžete jednoduše přistupovat k požadovanému prvku pomocí indexu.
- Režie paměti: LinkedList vyžaduje více paměti než ArrayList, protože každý prvek vyžaduje dodatečnou paměť pro odkazy na jeho předchůdce a následovníky.
Příručka:
Dobrou referenční knihou pro seznámení se s Java Collections Framework a LinkedList je Java Collections od Naftalin a Wadler. Tato kniha poskytuje komplexní pohled na rámec kolekcí Java, včetně LinkedList, a obsahuje mnoho příkladů a cvičení, která vám pomohou pochopit, jak tyto třídy efektivně používat.