linked list java linked list implementation java examples
In deze zelfstudie wordt uitgelegd wat een gekoppelde lijstgegevensstructuur in Java is en hoe u een gekoppelde Java-lijst kunt maken, initialiseren, implementeren, doorlopen, omkeren en sorteren:
In Java is een LinkedList een datastructuur waarin elementen op een niet-aangrenzende locatie worden opgeslagen. Het is een lineaire datastructuur.
Elk gegevensitem wordt een ‘Knooppunt’ genoemd en elk knooppunt heeft een gegevensdeel en een adresdeel. Het adresgedeelte slaat de link op naar het volgende knooppunt in de LinkedList.
Bezoek hier om de Java-trainingsserie voor iedereen te zien.
Wat je leert:
- LinkedList in Java
- Java LinkedList-klasse
- Hoe maak je een gekoppelde lijst in Java
- Linked List-implementatie in Java
- Doorkruisen / afdrukken van gekoppelde lijst in Java
- LinkedList-methoden
- Omgekeerde gekoppelde lijst in Java
- Sorteer een gekoppelde lijst in Java
- Verwijder duplicaten
- Circulaire gekoppelde lijst in Java
- Java 8 LinkedList
- Veel Gestelde Vragen
- Gevolgtrekking
LinkedList in Java
Hieronder is de algemene lay-out van LinkedList weergegeven:
Zoals getoond in de bovenstaande weergave van LinkedList, is elk item in de LinkedList de 'Node'. Elk knooppunt heeft twee delen, het eerste deel slaat de gegevens op en het tweede deel heeft een referentie of pointer of adres van het volgende knooppunt in de LinkedList.
wat is beschrijvend programmeren in qtp
Deze opstelling is nodig omdat de gegevens in LinkedList worden opgeslagen op niet-aangrenzende locaties, in tegenstelling tot Arrays.
De 'Head' van de LinkedList is een pointer die het adres van het eerste element in de LinkedList bevat. Het laatste knooppunt in de LinkedList is de staart. Zoals weergegeven in de bovenstaande afbeelding, is het adresgedeelte van het laatste knooppunt in de LinkedList ingesteld op ‘Null’, wat het einde van de LinkedList aangeeft.
Het bovenstaande diagram geeft een “ Enkelvoudig gekoppelde lijst ”Die het adres van alleen het volgende knooppunt in de LinkedList opslaat.
Er is een andere versie die bekend staat als ' Dubbel gekoppelde lijst 'Waarvan elk knooppunt uit drie delen bestaat:
- Adres of verwijzing of pointer naar het vorige element in de LinkedList.
- Gegevensgedeelte
- Adres of verwijzing of pointer naar het volgende element in de LinkedList.
Het vorige adres van het eerste element in de LinkedList wordt ingesteld op Null, terwijl de volgende pointer van het laatste element in de LinkedList wordt ingesteld op Null.
Vertegenwoordiging van dubbel gelinkte lijst:
Zoals getoond in de bovenstaande weergave, heeft elk knooppunt in de dubbel gekoppelde lijst verwijzingen naar zijn vorige en volgende knooppunt (dus weergegeven zonder pijlen). De vorige aanwijzer van het eerste knooppunt wijst naar nul terwijl de volgende aanwijzer van het laatste knooppunt naar nul wijst.
In deze LinkedList-zelfstudie behandelen we voornamelijk de enkelvoudig gelinkte lijst. We zullen de dubbel gelinkte lijst in onze volgende tutorial bespreken.
Java LinkedList-klasse
In Java wordt de gelinkte lijst geïmplementeerd door de ' LinkedList ”Klasse. Deze klasse behoort tot de “ java.util ' pakket. De klasse LinkedList implementeert de interfaces List en Deque en neemt de klasse AbstractList over.
Hieronder is de klassenhiërarchie van de LinkedList-klasse weergegeven.
Het bovenstaande diagram toont de hiërarchie van de klasse LinkedList. Zoals getoond implementeert de klasse LinkedList de interfaces List en Deque.
Zoals eerder vermeld, maakt de klasse LinkedList deel uit van de ' java.util ' pakket. Daarom zou u de klasse LinkedList in uw programma moeten kunnen gebruiken door een van de volgende uitspraken in uw programma op te nemen.
Of
Dus op basis van de bovenstaande hiërarchie is een typische definitie van de LinkedList-klasse als volgt:
Hieronder staan enkele kenmerken van de LinkedList-klasse die u moet onthouden:
- Deze klasse is niet gesynchroniseerd.
- Het staat dubbele waarden toe.
- Behoudt de invoegopdracht.
- Omdat elementen niet hoeven te worden verschoven tijdens het verplaatsen, is de manipulatie van elementen erin sneller.
- Deze klasse kan worden gebruikt om een stapel, wachtrij en lijst te implementeren.
Hoe maak je een gekoppelde lijst in Java
Voordat we verder gaan met het maken van een gekoppelde lijst in Java, bespreken we eerst een knooppunt met gekoppelde lijsten in Java.
Zoals reeds besproken, bestaat een gekoppelde lijst uit knooppunten. In Java kunnen we dus een LinkedList voorstellen als een klasse met zijn Node als een aparte klasse. Daarom heeft deze klasse een verwijzing naar het knooppunttype.
Dit wordt hieronder weergegeven:
Om een object van het type LinkedList te maken, zijn er twee hoofdconstructors:
# 1) LinkedList ()
De algemene syntaxis voor deze constructor is:
De bovenstaande instructie creëert een lege LinkedList.
Bijvoorbeeld,
Dit zal een lege gekoppelde lijst creëren met de naam l_list.
# 2) LinkedList (collectie c)
De algemene syntaxis is:
De bovenstaande verklaring maakt een LinkedList met elementen uit de collectie c als de oorspronkelijke elementen.
Net als andere lijstgegevensstructuren die we al hebben gezien, kan de gekoppelde lijst ook worden geïnitialiseerd met behulp van de add-methode, Arrays.asList () -methode of door de constructor te gebruiken met de verzameling als een argument.
Linked List-implementatie in Java
Hieronder wordt een eenvoudig voorbeeld gegeven van een LinkedList-datastructuur in Java. In dit implementatievoorbeeld zullen we de add-methode en de asList-methode gebruiken om de LinkedList-objecten te initialiseren.
Uitgang:
Inhoud van de eerste LinkedList: (10, 20, 30, 40, 50)
Inhoud van tweede LinkedList: (Rood, Groen, Blauw, Cyaan, Magenta)
Het bovenstaande programma toont de aanmaak en initialisatie van de LinkedList. Eerst maken we een LinkedList van het type Integer en bieden we een array van Integers die zijn geconverteerd naar een lijst met behulp van de asList-methode als initiële waarden voor de LinkedList.
Vervolgens maken we een lege LinkedList van het type String en met behulp van de add-methode voegen we waarden toe aan de LinkedList.
Ten slotte geven we zowel de LinkedList-objecten weer als een string.
Doorkruisen / afdrukken van gekoppelde lijst in Java
Om de inhoud af te drukken of bewerkingen uit te voeren op de elementen van de LinkedList, moet u door de elementen bladeren. We hebben deze methoden al gezien in onze vorige tutorials. In deze sectie bespreken we de voorbeelden van elk met betrekking tot LinkedList.
Gebruik voor lus
Uitgang:
LinkedList-elementen die for loop gebruiken:
Rood Groen Blauw
Gebruik voor elke lus
Uitgang:
LinkedList-elementen die forEach-lus gebruiken:
Rood Groen Blauw
Met behulp van Iterator
Uitgang:
De inhoud van Linked List:
Rood Groen Blauw Geel
software testen hervatten monsters 2 jaar ervaring
LinkedList-methoden
De klasse LinkedList biedt API die verschillende methoden ondersteunt om de gekoppelde lijst te manipuleren. We hebben de methoden in de LinkedList API hieronder in tabelvorm weergegeven.
We zullen de belangrijkste bewerkingen / methoden in de volgende sectie bespreken.
| Methode | Voorlopig ontwerp | Omschrijving |
|---|---|---|
| Doorzichtig | leegte duidelijk () | Verwijdert alle elementen uit de lijst. |
| Toevoegen | boolean add (E e) | Voeg een gespecificeerd element toe aan de LinkedList |
| void add (int index, E element) | Voeg element toe aan de opgegeven index in LinkedList | |
| Voeg alles toe | boolean addAll (verzameling c) | Voegt de elementen van de gegeven collectie c toe aan het einde van de LinkedList. |
| boolean addAll (int index, verzameling c) | Voegt de elementen van de gegeven verzameling c toe aan de opgegeven index in de LinkedList | |
| addFirst | leegte addFirst (E e) | Voeg het gegeven element toe als het eerste element aan de LinkedList. |
| addLast | leegte addLast (E e) | Voeg het gegeven element toe aan het einde van de lijst. |
| Kloon | Object kloon () | Maakt een ondiepe kopie van LinkedList |
| Bevat | Boolean bevat (Object o) | Controleert of de lijst gespecificeerde elementen bevat; zo ja geeft true terug. |
| aflopendIterator | Iterator aflopend | Retourneert een omgekeerd geordende iterator voor de LinkedList. |
| Element | E-element () | Retourneert het element bovenaan de lijst. |
| Krijgen | E get (int index) | Haalt het element op de opgegeven index. |
| getFirst | E getFirst () | Haalt het eerste element in de LinkedList op. |
| word laatste | E getLast () | Haalt het laatste element in de LinkedList op. |
| index van | Int indexOf (Object o) | Zoek de index van de eerste keer dat de gegeven elementen in de lijst voorkomen en retourneer de index. -1 als element niet gevonden is. |
| lastIndexOf | Int lastIndexOf (Object o) | Geeft de positie terug van de laatste keer dat het gegeven element in de LinkedList voorkomt; -1 als het gegeven element niet aanwezig is |
| listIterator | ListIterator listIterator (int index) | Retourneert de listIterator van de opgegeven index in de gekoppelde lijst. |
| Aanbod | booleaanse aanbieding (E e) | Voegt het gegeven element toe als het laatste element (staart) in de LinkedList. |
| aanbieding First | Booleaanse aanbiedingFirst (E e) | Voegt het gegeven element toe als het eerste element in de LinkedList. |
| aanbieding Laatste | Booleaanse aanbiedingLaatste (E e) | Voeg het gegeven element e toe aan het einde van de LinkedList. |
| Kijkje | E peek () | Retourneert de kop van de lijst zonder deze te verwijderen. |
| eerste | E peekFirst () | Retourneert het eerste element in de lijst. geeft null terug als de lijst leeg is. |
| laatste | E peekLast () | Retourneert het laatste element of null als de lijst leeg is. Het verwijdert het element niet. |
| Poll | E poll () | Retourneert de kop van de LinkedList en verwijdert deze ook. |
| pollFirst | E pollFirst () | Retourneert en verwijdert het eerste element in de lijst; geeft null terug als de lijst leeg is. |
| pollLast | E pollLast () | Retourneert en verwijdert het laatste element in de lijst; geeft null terug als de lijst leeg is. |
| Knal | E pop () | Verwijdert het element uit de stapelweergave van LinkedList. |
| Duwen | Void push (E e) | Duwt of voegt een element in de stapelweergave van de LinkedList. |
| Verwijderen | E verwijderen () | Verwijdert en retourneert het hoofd van de LinkedList. |
| E verwijderen (int index) | Verwijdert het element op de gegeven index uit de LinkedList. | |
| boolean remove (Object o) | Verwijdert het eerste exemplaar van het gegeven element uit de LinkedList. | |
| removeFirst | E removeFirst () | Retourneert en verwijdert het eerste element uit de lijst. |
| removeFirstOccurence | boolean removeFirstOccurrence (Object o) | Verwijdert het eerste exemplaar van het gegeven element uit de lijst wanneer de lijst van kop tot staart wordt doorlopen. |
| removeLast | E removeLast () | Retourneert het laatste element in de LinkedList en verwijdert het ook. |
| removeLastOccurence | boolean removeLastOccurrence (Object o) | Verwijdert het laatste exemplaar van het gegeven element uit de LinkedList wanneer het van kop tot staart wordt doorlopen |
| Set | E set (int index, E element) | Stelt het gegeven element in op de gegeven index. Vervangt het huidige element door nieuw. |
| Grootte | Int maat () | Retourneert de grootte of het aantal elementen in de LinkedList |
| toArray | Object () toArray () | Converteert de LinkedList naar een array met alle lijstelementen in de juiste volgorde |
| T () toArray (T () a) | Converteert LinkedList naar een array met hetzelfde runtime-type als argument a. |
Het onderstaande Java-programma demonstreert de verschillende methoden die we hierboven hebben genoemd.
Uitgang:
Gelinkte lijst: (A, B, C, D, G, E, F)
Gekoppelde lijst nadat ArrayList-inhoud is toegevoegd: (A, B, C, D, G, E, F, H, I)
Gelinkte lijst na verwijdering: (C, D, E, F, H)
Lijst bevat niet het element ‘G’
Grootte van gekoppelde lijst = 5
Element geretourneerd door get (): F
Gelinkte lijst na wijziging: (C, D, E, J, H)
Matrix verkregen uit gekoppelde lijst: (C, D, E, J, H)
Het bovenstaande programma demonstreert verschillende methoden van de LinkedList-klasse. Eerst declareren we een LinkedList van het type String. Vervolgens gebruiken we verschillende versies van de add-methode zoals add, andFirst, addLast, addAll, etc. om de LinkedList met waarden te vullen.
Hier kunnen we het element direct aan het einde van de lijst toevoegen of het element op een gespecificeerde positie in de lijst.
We gebruiken ook de addFirst-methode om een element aan het begin van de lijst toe te voegen en addLast om een element aan het einde van de lijst toe te voegen. Vervolgens voeren we verwijderingsbewerkingen uit op de LinkedList, zoals remove, removeFirst, removeLast, etc.
Voor de verwijdermethode kunnen we het element specificeren dat verwijderd moet worden of we kunnen de index of de positie in de LinkedList specificeren waarop het element verwijderd moet worden. De methoden removeFirst en removeLast verwijderen respectievelijk het eerste en het laatste element uit de lijst.
Vervolgens zoeken we in de lijst naar een bepaald element met behulp van de methode bevat. Vervolgens gebruiken we de methode size () om de grootte of lengte van de LinkedList op te halen. Vervolgens gebruiken we get / set-methoden om de waarde op een bepaalde index in de lijst op te halen en vervolgens een waarde op een opgegeven positie in de lijst te vervangen.
Ten slotte converteren we de LinkedList naar een Array met behulp van de toArray-methode.
Omgekeerde gekoppelde lijst in Java
Om een gekoppelde lijst in Java om te keren, gebruiken we de 'descendingIterator ()' - methode die een omgekeerde iterator voor de lijst retourneert. We kunnen deze iterator vervolgens gebruiken om door de lijst- en weergave-elementen te bladeren.
Het onderstaande programma keert de gekoppelde lijst om met behulp van de methode descendingIterator ().
Uitgang:
Gelinkte lijst: (Pune, Mumbai, Nagpur)
Gelinkte lijst in omgekeerde volgorde:
Nagpur Mumbai Pune
In het bovenstaande programma declareren we een gekoppelde lijst en drukken deze vervolgens af. Vervolgens krijgen we een omgekeerde iterator en doorlopen we de lijst met behulp hiervan en geven we elk element weer. De uitvoer toont de gekoppelde inhoud van de lijst, eerst in de volgorde waarin de elementen zijn toegevoegd en vervolgens toont de uitvoer de inhoud in omgekeerde volgorde.
Sorteer een gekoppelde lijst in Java
LinkedList klasseobjecten kunnen worden gesorteerd met de methode Collections.sort (). Deze methode biedt twee versies met of zonder gebruik van een comparator. Wanneer de methode Collections.sort () wordt aangeroepen zonder een vergelijker, wordt de verzameling in de natuurlijke volgorde gesorteerd.
Wanneer de comparator wordt gebruikt met deze methode, kunnen we onze eigen sorteercriteria definiëren door de methode CompareTo te overschrijven.
Het onderstaande Java-programma sorteert een LinkedList met Collections.sort (). Hier sorteren we arrays met behulp van natuurlijke ordening en met behulp van een comparator.
Uitgang:
Oorspronkelijke LinkedList (ongesorteerd): (jan, feb, mrt, apr, mei, jun)
LinkedList (in natuurlijke volgorde gesorteerd): (apr, feb, jan, jun, mrt, mei)
LinkedList (gesorteerd met Comparator): (apr, feb, jan, jun, mrt, mei)
Verwijder duplicaten
Om duplicaten te verwijderen, moet u elk knooppunt doorkruisen en vergelijken met het volgende knooppunt. Als beide knooppunten hetzelfde zijn, slaan we een knooppunt over en gaan we naar het volgende.
Op deze manier krijgen we, na het doorlopen van elk knooppunt en het verwijderen van dubbele knooppunten, de resulterende lijst zonder dubbele elementen.
Hieronder wordt een Java-programma gegeven om duplicaten te verwijderen.
Uitgang:
Originele Linkedlist:
1 1 2 3 5 2 1 1
LinkedList na het verwijderen van duplicaten:
1 2 3 5
In het bovenstaande programma hebben we een gekoppelde lijstklasse gemaakt om duplicaten te verwijderen. We hebben ook een klasse om elk knooppunt te definiëren. Met andere woorden, de knooppunten in de lijst zijn de objecten van dit klasseknooppunt. We hebben een methode om het knooppunt aan een gekoppelde lijst toe te voegen.
Vervolgens doorlopen we in de methode removeDuplicate elk knooppunt in de gekoppelde lijst, beginnend bij het hoofd, en vergelijken we elk volgend knooppunt voor het duplicaat. Als er een duplicaat wordt gevonden, slaan we dat knooppunt over en gaan we verder naar het volgende knooppunt.
Op deze manier wordt de ist opgebouwd door de dubbele knooppunten over te slaan en wordt de gewijzigde lijst afgedrukt met de methode print ().
Circulaire gekoppelde lijst in Java
Een circulaire gekoppelde lijst is een lijst waarvan de staart of het laatste knooppunt is verbonden met het hoofd of het eerste knooppunt.
Het onderstaande diagram toont de circulaire gekoppelde lijst in Java.
Zoals getoond in het bovenstaande diagram, is het adresgedeelte van het laatste knooppunt of de staart van de gekoppelde lijst niet ingesteld op nul. In plaats daarvan verwijst het terug naar het eerste knooppunt of hoofd van de lijst en vormt zo een cirkelvormige gekoppelde lijst.
Het onderstaande programma implementeert een circulaire gekoppelde lijst waarin we individuele knooppunten van de gekoppelde lijst moeten manipuleren.
Uitgang:
Circulaire gekoppelde lijstknooppunten:
10 20 30 40
Java 8 LinkedList
Hoewel er in Java 8 geen specifieke functies meer zijn toegevoegd aan de klasse LinkedList, zijn er nog steeds streams geïntroduceerd om gegevens te manipuleren.
Het onderstaande programma toont het gebruik van Java 8-stream om LinkedList weer te geven.
Uitgang:
De inhoud van LinkedList:
Netto
Groen
Blauw
Cyaan
Magenta
Veel Gestelde Vragen
V # 1) Wanneer wordt de gekoppelde lijst gebruikt in Java?
Antwoord: Omdat het sneller is dan verzamelingen zoals ArrayList bij wijzigingsbewerkingen, moet het worden gebruikt in toepassingen die vaak moeten worden toegevoegd / verwijderd. Voor toepassingen die voornamelijk alleen-lezen gegevens hebben, kunnen ArrayList of vergelijkbare verzamelingen worden gebruikt.
Q # 2) Wat is ListNode?
Antwoord: Een ListNode is een basisklasse die is gekoppeld aan een gekoppelde lijst in Java en vertegenwoordigt informatie die is gekoppeld aan een enkel element of een knooppunt. Elke ListNode bestaat uit gegevens en een pointer of verwijzing naar het volgende element.
Q # 3) Staat de gekoppelde lijst null-waarden toe?
Antwoord: Ja, de gekoppelde lijst staat elk aantal null-waarden toe.
Q # 4) Wat zijn de voordelen van een gekoppelde lijst?
Antwoord: Enkele voordelen zijn:
- Manipulatiebewerkingen zoals optellen en verwijderen zijn er sneller in.
- Het is niet nodig om vooraf geheugen toe te wijzen aan een gekoppelde lijst, wat resulteert in een efficiënt geheugengebruik.
- Het biedt snellere toegangstijd en zonder extra overhead voor geheugen, en kan in constante tijd worden uitgebreid.
- Het is een dynamische datastructuur
- Groeit en krimpt tijdens runtime, afhankelijk van toegevoegde of verwijderde waarden.
Q # 5) Wat is de toepassing van de gekoppelde lijst?
Antwoord: Het wordt voornamelijk gebruikt in de volgende toepassingen:
- Om de functie 'ongedaan maken' te implementeren in software zoals MS-Word, Photoshop, enz.
- Om datastructuren zoals stack en wachtrij te implementeren.
- We kunnen ook grafieken implementeren met behulp van een gekoppelde lijst.
- Voor bucket-hashing kan elke bucket worden geïmplementeerd als een gekoppelde lijst.
Q # 6 Wat zijn de beperkingen van een gekoppelde lijst?
Antwoord: Enkele van de beperkingen zijn:
- Met een extra aanwijzer om de referentie van het volgende element in elk knooppunt vast te houden, is het gebruikte geheugen veel meer dan arrays.
- Dit is een strikt opeenvolgend toegankelijke datastructuur en daarom moeten knooppunten van de gekoppelde lijst altijd vanaf het begin worden gelezen.
- Het is moeilijk om achteruit te gaan, vooral de enkelvoudig gelinkte lijsten.
- Omdat de knooppunten zijn opgeslagen op niet-aangrenzende locaties, kan de tijd die nodig is voor toegang hoog zijn.
Gevolgtrekking
In deze tutorial hebben we de basisgegevensstructuur van een gekoppelde lijst geleerd. Daarna gingen we verder met de klasse java.util.LinkedList in Java. We hebben deze klasse in detail besproken, inclusief de constructors, methoden, enz.
We hebben ook enkele speciale bewerkingen besproken met betrekking tot gekoppelde lijsten, zoals sorteren, een lijst omkeren, duplicaten verwijderen, circulaire gekoppelde lijsten, enz.
webservices die interviewvragen en antwoorden testen
In onze volgende tutorial bespreken we specifieke kenmerken van de dubbel gelinkte lijst.
Bekijk hier de complete Java-trainingsgids.
Aanbevolen literatuur
- Dubbel gekoppelde lijst in Java - Implementatie en codevoorbeelden
- Java-lijst - Hoe u een lijst in Java kunt maken, initialiseren en gebruiken
- Java-lijstmethoden - lijst sorteren, bevat, lijst toevoegen, lijst verwijderen
- Binair zoekalgoritme in Java - implementatie en voorbeelden
- Invoegsortering in Java - Invoegsorteeralgoritme en voorbeelden
- Java-interface en abstracte les met voorbeelden
- Gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Covert List To Array en andere collecties in Java