Gekoppelde lijst is een onderdeel van de Collectiekader aanwezig in java.util-pakket. Deze klasse is een implementatie van de dubbel gekoppelde lijstdatastructuur.
Het belangrijkste verschil tussen een normale gekoppelde lijst en een dubbel gekoppelde lijst is dat een dubbel gekoppelde lijst een extra aanwijzer bevat, doorgaans de vorige aanwijzer genoemd, samen met de volgende aanwijzer en gegevens die aanwezig zijn in de enkelvoudig gekoppelde lijst.
Constructeurs in de LinkedList:
Om een LinkedList te maken, moeten we een object van de LinkedList-klasse maken. De klasse LinkedList bestaat uit verschillende constructors die de mogelijke creatie van de lijst mogelijk maken. De volgende constructors zijn beschikbaar in deze klasse:
1. GelinkteLijst(): Deze constructor wordt gebruikt om een lege gekoppelde lijst te maken. Als we een lege LinkedList willen maken met de naam ll, kan deze worden gemaakt als:
LinkedList ll = nieuwe LinkedList();
2. LinkedList (verzameling C): Deze constructor wordt gebruikt om een geordende lijst te maken die alle elementen van een opgegeven verzameling bevat, zoals geretourneerd door de iterator van de verzameling. Als we een LinkedList met de naam ll willen maken, kan deze als volgt worden gemaakt:
LinkedList ll = nieuwe LinkedList(C);
Methoden voor Java LinkedList:
| Methode | Beschrijving |
|---|---|
| add(int index, E-element) | Deze methode Voegt het gespecificeerde element in op de gespecificeerde positie in deze lijst. |
| toevoegen(En en) | Deze methode Voegt het opgegeven element toe aan het einde van deze lijst. |
| addAll(int index, Verzameling c) | Met deze methode worden alle elementen uit de opgegeven verzameling in deze lijst ingevoegd, beginnend op de opgegeven positie. |
| addAll(verzameling c) | Deze methode voegt alle elementen in de opgegeven verzameling toe aan het einde van deze lijst, in de volgorde waarin ze worden geretourneerd door de iterator van de opgegeven verzameling. |
| addFirst(E e) | Deze methode Voegt het opgegeven element aan het begin van deze lijst in. |
| voegLaatste toe(E e) | Deze methode Voegt het opgegeven element toe aan het einde van deze lijst. |
| duidelijk() | Deze methode verwijdert alle elementen uit deze lijst. |
| kloon() | Deze methode retourneert een ondiepe kopie van deze LinkedList. |
| bevat(Object o) | Deze methode retourneert true als deze lijst het opgegeven element bevat. |
| aflopendeIterator() | Deze methode retourneert een iterator over de elementen in deze deque in omgekeerde volgorde. |
| element() | Deze methode haalt de kop (eerste element) van deze lijst op, maar verwijdert deze niet. |
| get(int-index) | Deze methode retourneert het element op de opgegeven positie in deze lijst. |
| krijgEerste() | Deze methode retourneert het eerste element in deze lijst. |
| word laatste() | Deze methode retourneert het laatste element in deze lijst. |
| indexOf(Object o) | Deze methode retourneert de index van de eerste keer dat het opgegeven element in deze lijst voorkomt, of -1 als deze lijst het element niet bevat. |
| laatsteIndexOf(Object o) | Deze methode retourneert de index van de laatste keer dat het opgegeven element in deze lijst voorkomt, of -1 als deze lijst het element niet bevat. |
| listIterator(int-index) | Deze methode retourneert een lijst-iterator van de elementen in deze lijst (in de juiste volgorde), beginnend op de opgegeven positie in de lijst. |
| aanbieding(E e) | Deze methode Voegt het opgegeven element toe als de staart (laatste element) van deze lijst. |
| offerFirst(E en) | Deze methode Voegt het opgegeven element bovenaan deze lijst in. |
| aanbiedingLaatste(E e) | Deze methode Voegt het opgegeven element aan het einde van deze lijst in. |
| kijkje() | Deze methode haalt de kop (eerste element) van deze lijst op, maar verwijdert deze niet. |
| kijkjeEerste() | Deze methode haalt het eerste element van deze lijst op, maar verwijdert het niet, of retourneert null als deze lijst leeg is. |
| kijkjeLaatste() | Deze methode haalt het laatste element van deze lijst op, maar verwijdert het niet, of retourneert null als deze lijst leeg is. |
| opiniepeiling() | Deze methode haalt de kop (eerste element) van deze lijst op en verwijdert deze. |
| opiniepeilingEerste() | Deze methode haalt het eerste element van deze lijst op en verwijdert deze, of retourneert null als deze lijst leeg is. |
| opiniepeilingLaatste() | Deze methode haalt het laatste element van deze lijst op en verwijdert deze, of retourneert null als deze lijst leeg is. |
| knal() | Deze methode Haalt een element uit de stapel die door deze lijst wordt weergegeven. |
| druk(E en) | Deze methode duwt een element op de stapel die door deze lijst wordt weergegeven. |
| verwijderen() | Deze methode haalt de kop (eerste element) van deze lijst op en verwijdert deze. |
| verwijder(int index) | Deze methode verwijdert het element op de opgegeven positie in deze lijst. |
| verwijder(Object o) | Deze methode verwijdert de eerste keer dat het opgegeven element voorkomt uit deze lijst, als dit aanwezig is. |
| verwijderEerste() | Deze methode verwijdert het eerste element uit deze lijst en retourneert het. |
| removeFirstOccurrence(Object o) | Deze methode verwijdert de eerste keer dat het opgegeven element in deze lijst voorkomt (bij het doorlopen van de lijst van kop tot staart). |
| verwijderLaatste() | Deze methode verwijdert het laatste element uit deze lijst en retourneert het. |
| removeLastOccurrence(Object o) | Deze methode verwijdert de laatste keer dat het opgegeven element in deze lijst voorkomt (bij het doorlopen van de lijst van kop tot staart). |
| set(int index, E-element) | Deze methode vervangt het element op de opgegeven positie in deze lijst door het opgegeven element. |
| maat() | Deze methode retourneert het aantal elementen in deze lijst. |
| splitter() | Deze methode creëert een laatbindende en faalsnelle spliterator over de elementen in deze lijst. |
| toArray() | Deze methode retourneert een array met alle elementen in deze lijst in de juiste volgorde (van het eerste tot het laatste element). |
| toArray(T[] a) | Deze methode retourneert een array met alle elementen in deze lijst in de juiste volgorde (van het eerste tot het laatste element); het runtimetype van de geretourneerde array is dat van de opgegeven array. |
| toString() | Deze methode retourneert een string die alle elementen in deze lijst in de juiste volgorde bevat (van het eerste tot het laatste element), elk element wordt gescheiden door komma's en de string wordt tussen vierkante haakjes geplaatst. |
Hieronder ziet u de implementatie van de bovenstaande bewerkingen:
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);> >}> }> |
>
>Uitvoer
[D, A, E, B, C] [A]>
In de bovenstaande afbeelding zijn AbstractList , CopyOnWriteArrayList en AbstractSequentialList de klassen die de lijstinterface implementeren. In elk van de genoemde klassen is een aparte functionaliteit geïmplementeerd. Zij zijn:
- AbstractList: Deze klasse wordt gebruikt om een niet-wijzigbare lijst te implementeren, waarvoor men alleen deze AbstractList-klasse hoeft uit te breiden en alleen de methoden get() en size() te implementeren. CopyOnWriteArrayList: deze klasse implementeert de lijstinterface. Het is een verbeterde versie van ArrayList waarin alle wijzigingen (toevoegen, instellen, verwijderen, enz.) worden geïmplementeerd door een nieuwe kopie van de lijst te maken.
Verschillende bewerkingen uitvoeren op LinkedList:
- Elementen toevoegen
- Elementen bijwerken
- Elementen verwijderen
- Itereren over elementen
- Naar array();
- Maat();
- verwijder Eerste();
- verwijder laatste();
Operatie 1: Elementen toevoegen
Om een element aan een ArrayList toe te voegen, kunnen we de add() methode gebruiken. Deze methode is overbelast om meerdere bewerkingen uit te voeren op basis van verschillende parameters. Zij zijn:
- add(Object): Deze methode wordt gebruikt om een element aan het einde van de LinkedList toe te voegen. add(int index, Object): Deze methode wordt gebruikt om een element toe te voegen aan een specifieke index in de LinkedList.
Hieronder ziet u de implementatie van de bovenstaande bewerking:
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);> >}> }> |
>
>Uitvoer
[Geeks, For, Geeks]>
Operatie 2: Elementen veranderen
Als we na het toevoegen van de elementen het element willen wijzigen, kan dit worden gedaan met behulp van de set() methode . Omdat een LinkedList is geïndexeerd, wordt naar het element dat we willen wijzigen verwezen door de index van het element. Daarom gebruikt deze methode een index en het bijgewerkte element dat in die index moet worden ingevoegd.
Hieronder ziet u de implementatie van de bovenstaande bewerking:
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);> >}> }> |
stringarray maken in Java
>
>Uitvoer
Initial LinkedList [Geeks, Geeks, Geeks] Updated LinkedList [Geeks, For, Geeks]>
Operatie 3: Elementen verwijderen
Om een element uit een LinkedList te verwijderen, kunnen we de remove() methode gebruiken. Deze methode is overbelast om meerdere bewerkingen uit te voeren op basis van verschillende parameters. Zij zijn:
- remove(Object): Deze methode wordt gebruikt om eenvoudig een object uit de LinkedList te verwijderen. Als er meerdere van dergelijke objecten zijn, wordt het eerste exemplaar van het object verwijderd. remove(int index): Omdat een LinkedList wordt geïndexeerd, neemt deze methode een geheel getal aan, waardoor eenvoudigweg het element wordt verwijderd dat aanwezig is in die specifieke index in de LinkedList. Na het verwijderen van het element en de indexen van elementen worden bijgewerkt, wordt ook het object van LinkedList bijgewerkt, waardoor een nieuwe lijst ontstaat na het verwijderen van element(en).
Hieronder ziet u de implementatie van de bovenstaande bewerking:
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);> >}> }> |
>
>Uitvoer
Initial LinkedList [Geeks, For, Geeks] After the Index Removal [Geeks, Geeks] After the Object Removal [Geeks]>
Bewerking 4: De LinkedList herhalen
Er zijn meerdere manieren om LinkedList te doorlopen. De bekendste manieren zijn het gebruik van de basis for-lus in combinatie met een get()-methode om het element op een specifieke index te krijgen en de geavanceerde for-loop.
Hieronder ziet u de implementatie van de bovenstaande bewerking:
Java
ontwerppatronen Java
// 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 + ' '); } }> |
>
>Uitvoer
Geeks For Geeks Geeks For Geeks>
Bewerking 4: Lijst gekoppeld aan To Array met behulp van 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+>' '>);> >}> }> |
>
>Uitvoer
LinkedList: [123, 12, 11, 1134] After converted LinkedList to Array: 123 12 11 1134>
Bewerking 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());> >}> }> |
>
>Uitvoer
The size of the linked list is: 2>
Bewerking 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);> >}> }> |
Diana Maria Zwarter
>
>Uitvoer
LinkedList:[10, 20, 30] The remove first element is: 10 Final LinkedList:[20, 30]>
Bewerking 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);> >}> }> |
>
>Uitvoer
LinkedList:[10, 20, 30] The last element is removed: 30 Final LinkedList:[10, 20] The last element is removed: 20 Final LinkedList:[10]>
De klasse LinkedList in Java maakt deel uit van het Java Collections Framework en biedt een gekoppelde lijstimplementatie van de List-interface. Het maakt de opslag en het ophalen van elementen mogelijk in een dubbel gekoppelde lijstdatastructuur, waarbij elk element is gekoppeld aan zijn voorganger en opvolgerelementen.
Hier is een eenvoudig voorbeeld dat laat zien hoe u een LinkedList in Java gebruikt:
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);> >}> >}> }> |
>
>Uitvoer
0 1 2 3 4>
Voordelen van het gebruik van LinkedList in Java:
- Dynamische grootte: Net als bij Vector kan de grootte van een LinkedList dynamisch groeien of krimpen, zodat u zich geen zorgen hoeft te maken over het instellen van een initiële grootte.
- Efficiënt invoegen en verwijderen: LinkedList is een efficiënte gegevensstructuur voor het invoegen of verwijderen van elementen in het midden van de lijst, omdat u alleen de koppelingen tussen elementen hoeft te wijzigen, in plaats van alle elementen na het invoeg- of verwijderingspunt te verschuiven.
- Flexibele iteratie: Met een gekoppelde lijst kunt u efficiënt in beide richtingen door de lijst itereren, omdat elk element een verwijzing heeft naar zowel zijn voorganger als zijn opvolger.
Nadelen van het gebruik van LinkedList in Java:
- Prestaties: LinkedList presteert langzamer dan ArrayList als het gaat om toegang tot individuele elementen. Dit komt omdat u de lijst moet doorlopen om het gewenste element te bereiken, terwijl u met ArrayList eenvoudig toegang kunt krijgen tot het gewenste element met behulp van een index.
- Geheugenoverhead: LinkedList vereist meer geheugen dan ArrayList omdat elk element extra geheugen nodig heeft voor de koppelingen naar zijn voorganger en opvolgerelementen.
Referentieboek:
Een goed naslagwerk om meer te leren over het Java Collections Framework en LinkedList is Java Collections van Naftalin en Wadler. Dit boek biedt een uitgebreid overzicht van het Java-collectieframework, inclusief LinkedList, en bevat veel voorbeelden en oefeningen om u te helpen begrijpen hoe u deze klassen effectief kunt gebruiken.