doubly linked list java implementation code examples
In deze zelfstudie wordt de dubbel gekoppelde lijst in Java uitgelegd, samen met de implementatie van dubbele gekoppelde lijsten, de circulaire Java-code met dubbele gekoppelde lijst en voorbeelden:
De gekoppelde lijst is een opeenvolgende weergave van elementen. Elk element van de gekoppelde lijst wordt een ‘Knooppunt’ genoemd. Een type gelinkte lijst wordt 'Enkelvoudig gelinkte lijst' genoemd.
Hierin bevat elk knooppunt een gegevensdeel dat feitelijke gegevens opslaat en een tweede deel dat een aanwijzer opslaat naar het volgende knooppunt in de lijst. We hebben de details van de enkelvoudig gelinkte lijst al geleerd in onze vorige tutorial.
Bekijk hier ALLE Java-tutorials.
Wat je leert:
Dubbel gekoppelde lijst in Java
Een gelinkte lijst heeft nog een variant genaamd 'dubbel gelinkte lijst'. Een dubbel gekoppelde lijst heeft een extra aanwijzer die bekend staat als de vorige aanwijzer in zijn knooppunt, afgezien van het gegevensgedeelte en de volgende aanwijzer zoals in de enkelvoudig gekoppelde lijst.
Een knooppunt in de dubbel gelinkte lijst ziet er als volgt uit:
c en c ++ verschillen
Hier zijn 'Prev' en 'Next' verwijzingen naar respectievelijk de vorige en volgende elementen van het knooppunt. De ‘Data’ is het feitelijke element dat in het knooppunt is opgeslagen.
De volgende afbeelding toont een dubbel gelinkte lijst.
Het bovenstaande diagram toont de dubbel gelinkte lijst. Er zijn vier knooppunten in deze lijst. Zoals u kunt zien, is de vorige aanwijzer van het eerste knooppunt en de volgende aanwijzer van het laatste knooppunt ingesteld op nul. De vorige aanwijzer die is ingesteld op nul, geeft aan dat dit het eerste knooppunt is in de dubbel gekoppelde lijst, terwijl de volgende aanwijzer die is ingesteld op nul aangeeft dat het knooppunt het laatste knooppunt is.
Voordelen
- Omdat elk knooppunt wijzers heeft die naar de vorige en volgende knooppunten wijzen, kan de dubbel gekoppelde lijst zowel voorwaarts als achterwaarts gemakkelijk worden doorlopen
- U kunt het nieuwe knooppunt snel toevoegen door de aanwijzers te wijzigen.
- Evenzo is het verwijderen voor de verwijderbewerking, aangezien we zowel vorige als volgende verwijzingen hebben, gemakkelijker en hoeven we niet de hele lijst te doorlopen om het vorige knooppunt te vinden, zoals in het geval van de enkelvoudig gekoppelde lijst.
Nadelen
- Aangezien er een extra aanwijzer in de dubbelgekoppelde lijst staat, d.w.z. de vorige aanwijzer, is extra geheugenruimte vereist om deze aanwijzer samen met de volgende aanwijzer en het volgende gegevensitem op te slaan.
- Alle bewerkingen zoals toevoegen, verwijderen, enz. Vereisen dat zowel vorige als volgende verwijzingen worden gemanipuleerd, waardoor operationele overhead wordt opgelegd.
Implementatie in Java
De implementatie van een dubbel gekoppelde lijst in Java omvat het maken van een dubbel gekoppelde lijstklasse, de knooppuntklasse en het toevoegen van knooppunten aan de dubbel gekoppelde lijst
Het toevoegen van nieuwe knooppunten gebeurt meestal aan het einde van de lijst. Het onderstaande diagram toont de toevoeging van het nieuwe knooppunt aan het einde van de dubbelgekoppelde lijst.
Zoals te zien is in het bovenstaande diagram, wijst de volgende aanwijzer van het laatste knooppunt nu naar het nieuwe knooppunt in plaats van naar null om een nieuw knooppunt aan het einde van de lijst toe te voegen. De vorige aanwijzer van het nieuwe knooppunt wijst naar het laatste knooppunt. Ook wijst de volgende wijzer van het nieuwe knooppunt naar nul, waardoor het een nieuw laatste knooppunt wordt.
Het onderstaande programma toont de Java-implementatie van een dubbelgekoppelde lijst met de toevoeging van nieuwe knooppunten aan het einde van de lijst.
Uitgang:
Knooppunten van dubbel gelinkte lijst:
10 20 30 40 50
Naast het toevoegen van een nieuw knooppunt aan het einde van de lijst, kunt u ook een nieuw knooppunt aan het begin van de lijst of tussen de lijst toevoegen. We laten deze implementatie over aan de lezer zodat de lezers de operaties beter kunnen begrijpen.
Circulaire dubbel gekoppelde lijst in Java
Een circulaire dubbelgekoppelde lijst is een van de complexe structuren. In deze lijst bevat het laatste knooppunt van de dubbelgekoppelde lijst het adres van het eerste knooppunt en het eerste knooppunt het adres van het laatste knooppunt. Dus in een circulaire dubbelgekoppelde lijst is er een cyclus en wordt geen van de knooppuntaanwijzers op nul gezet.
Het volgende diagram toont de circulaire dubbelgekoppelde lijst.
Zoals weergegeven in het bovenstaande diagram, wijst de volgende wijzer van het laatste knooppunt naar het eerste knooppunt. De vorige aanwijzer van het eerste knooppunt wijst naar het laatste knooppunt.
Circulaire dubbelgekoppelde lijsten hebben brede toepassingen in de software-industrie. Een van die toepassingen is de muzikale app met een afspeellijst. Als u in de afspeellijst alle nummers hebt afgespeeld, gaat u aan het einde van het laatste nummer automatisch terug naar het eerste nummer. Dit gebeurt met behulp van cirkelvormige lijsten.
Voordelen van een circulaire dubbele gekoppelde lijst:
- De circulaire dubbel gekoppelde lijst kan van kop tot staart of van staart tot kop worden doorlopen.
- Van kop naar staart of van staart naar kop gaan is efficiënt en kost alleen constante tijd O (1).
- Het kan worden gebruikt voor het implementeren van geavanceerde datastructuren, waaronder Fibonacci-heap.
Nadelen:
- Omdat elk knooppunt ruimte moet maken voor de vorige aanwijzer, is extra geheugen vereist.
- Bij het uitvoeren van bewerkingen op een circulaire dubbelgekoppelde lijst hebben we met veel tips te maken. Als pointers niet goed worden afgehandeld, kan de implementatie breken.
Het onderstaande Java-programma toont de implementatie van de circulaire dubbel gelinkte lijst.
Uitgang:
Circulaire dubbel gelinkte lijst: 40 50 60 70 80
Circulaire dubbel gelinkte lijst achteruit gegaan:
80 70 60 50 40
In het bovenstaande programma hebben we het knooppunt aan het einde van de lijst toegevoegd. Aangezien de lijst cirkelvormig is, zal de volgende aanwijzer van het nieuwe knooppunt naar het eerste knooppunt wijzen en de vorige aanwijzer van het eerste knooppunt naar het nieuwe knooppunt wanneer het nieuwe knooppunt wordt toegevoegd.
Op dezelfde manier zal de vorige wijzer van het nieuwe knooppunt naar het huidige laatste knooppunt wijzen dat nu het voorlaatste knooppunt zal worden. We laten de implementatie van het toevoegen van een nieuw knooppunt aan het begin van de lijst en tussen de knooppunten over aan de lezers.
Veel Gestelde Vragen
V # 1) Kan de dubbel gelinkte lijst circulair zijn?
Antwoord: Ja. Het is een meer complexe datastructuur. In een circulaire dubbelgekoppelde lijst bevat de vorige pointer van het eerste knooppunt het adres van het laatste knooppunt en de volgende pointer van het laatste knooppunt het adres van het eerste knooppunt.
Vraag 2) Hoe creëer je een dubbel circulaire gekoppelde lijst?
Antwoord: U kunt een klasse maken voor een dubbel circulaire gekoppelde lijst. Binnen deze klasse zal er een statische klasse zijn die het knooppunt vertegenwoordigt. Elk knooppunt bevat twee verwijzingen: vorige en volgende en een gegevensitem. Vervolgens kunt u bewerkingen uitvoeren om knooppunten aan de lijst toe te voegen en door de lijst te lopen.
V # 3) Is dubbel gelinkte lijst lineair of circulair?
Antwoord: De dubbelgekoppelde lijst is een lineaire structuur maar een cirkelvormige dubbelgekoppelde lijst waarvan de staart naar de kop wijst en de kop naar de staart. Daarom is het een ronde lijst.
V # 4) Wat is het verschil tussen de dubbel gelinkte lijst en de circulaire gelinkte lijst?
Antwoord: Een dubbel gelinkte lijst heeft knooppunten die informatie bewaren over de vorige en volgende knooppunten met respectievelijk de vorige en volgende verwijzingen. Ook wordt de vorige pointer van het eerste knooppunt en de volgende pointer van het laatste knooppunt op nul gezet in de dubbel gekoppelde lijst.
In de circulaire gekoppelde lijst zijn er geen start- of eindknooppunten en vormen de knooppunten een cyclus. Ook is geen van de pointers ingesteld op null in de circulaire gekoppelde lijst.
V # 5) Wat zijn de voordelen van een dubbel gelinkte lijst?
Antwoord: De voordelen van de dubbel gelinkte lijst zijn:
- Het kan zowel in voorwaartse als achterwaartse richting worden doorlopen.
- Invoegen is eenvoudiger omdat we niet de hele lijst hoeven te doorlopen om het vorige element te vinden.
- Verwijderen is efficiënt omdat we weten dat de vorige en volgende knooppunten en manipulatie eenvoudiger zijn.
Gevolgtrekking
In deze tutorial hebben we de Dubbel gelinkte lijst in Java in detail besproken. Een dubbelgekoppelde lijst is een complexe structuur waarin elk knooppunt verwijzingen bevat naar zowel het vorige als het volgende knooppunt. Het beheer van deze links is soms moeilijk en kan leiden tot uitval van code als deze niet correct wordt afgehandeld.
Over het algemeen zijn de bewerkingen van een dubbel gekoppelde lijst efficiënter omdat we tijd kunnen besparen voor het doorlopen van de lijst, aangezien we zowel de vorige als de volgende aanwijzingen hebben.
De circulaire dubbelgekoppelde lijst is complexer en ze vormen een cirkelvormig patroon waarbij de vorige aanwijzer van het eerste knooppunt naar het laatste knooppunt wijst en de volgende aanwijzer van het laatste knooppunt naar het eerste knooppunt. Ook in dit geval zijn de operaties efficiënt.
c ++ binaire boomimplementatie
Hiermee zijn we klaar met de gekoppelde lijst in Java. Blijf ons volgen voor nog veel meer tutorials over zoek- en sorteertechnieken in Java.
Bezoek hier voor de exclusieve Java Training Tutorial Series.
Aanbevolen literatuur
- Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Binair zoekalgoritme in Java - implementatie en voorbeelden
- Java-lijst - Hoe u een lijst in Java kunt maken, initialiseren en gebruiken
- Java-interface en abstracte les met voorbeelden
- Java-lijstmethoden - lijst sorteren, bevat, lijst toevoegen, lijst verwijderen
- Invoegsortering in Java - Invoegsorteeralgoritme en voorbeelden
- JAVA-zelfstudie voor beginners: 100+ praktische Java-videotutorials
- Bubbelsortering in Java - Java-sorteeralgoritmen en codevoorbeelden