Share
Wat je gaat creërenTwee van de meest onderwezen datastructuren in de informatica zijn de enkelvoudig gekoppelde lijst en dubbel gelinkte lijst.
Toen ik deze datastructuren leerde, vroeg ik mijn collega's naar analogieën om ze te conceptualiseren. Wat ik hoorde waren verschillende voorbeelden, zoals een lijst met boodschappen en een trein. Deze analogieën, zoals ik uiteindelijk leerde, waren onnauwkeurig. Een boodschappenlijstje was meer analoog een wachtrij; een trein was meer analoog aan een array.
Naarmate er meer tijd verstreek, ontdekte ik uiteindelijk een analogie die een enkelvoudig gelinkte lijst en een dubbel gelinkte lijst nauwkeurig beschreef: een speurtocht. Als je nieuwsgierig bent naar de relatie tussen een speurtocht en een gekoppelde lijst, lees dan hieronder voor het antwoord!
In de informatica is een enkelvoudig gekoppelde lijst een datastructuur die een reeks gekoppelde knooppunten bevat. Elk knooppunt bevat op zijn beurt gegevens en een aanwijzer, die naar een ander knooppunt kunnen wijzen.
Knopen van een enkelvoudig gelinkte lijst lijken erg op stappen in een speurtocht. Elke stap bevat een bericht (bijvoorbeeld "U bent in Frankrijk aangekomen") en wijst naar de volgende stap (bijvoorbeeld "Deze breedtegraad- en lengtegraadcoördinaten bezoeken"). Wanneer we deze afzonderlijke stappen gaan sequencen om een reeks stappen te vormen, creëren we een speurtocht.
Nu we een conceptueel model hebben van een enkelvoudig gekoppelde lijst, laten we de werking van een enkelvoudig gekoppelde lijst verkennen.
Omdat een enkelvoudig gekoppelde lijst knooppunten bevat, die een afzonderlijke constructor kunnen zijn van een enkelvoudig gekoppelde lijst, schetsen we de werking van beide constructeurs: Knooppunt en SinglyList.
Accentsconagua
gegevens slaat een waarde op.volgende wijst naar het volgende knooppunt in de lijst._lengte haalt het aantal knooppunten in een lijst op.hoofd wijst een knooppunt toe als de kop van een lijst.waarde toevoegen) voegt een knooppunt toe aan een lijst.searchNodeAt (positie) zoekt naar een knoop op de n-positie in onze lijst.Verwijder (positie) verwijdert een knooppunt uit een lijst.Voor onze implementatie zullen we eerst een constructor met de naam definiëren Knooppunt en dan een constructor genaamd SinglyList.
Elke instantie van Knooppunt heeft de mogelijkheid nodig om gegevens op te slaan en de mogelijkheid om naar een ander knooppunt te wijzen. Om deze functionaliteit toe te voegen, zullen we twee eigenschappen creëren: gegevens en volgende, respectievelijk.
function Node (data) this.data = data; this.next = null;
Vervolgens moeten we definiëren SinglyList:
function SinglyList () this._length = 0; this.head = null;
Elke instantie van SinglyList zal twee eigenschappen hebben: _lengte en hoofd. De eerste krijgt het aantal knooppunten in een lijst toegewezen; de laatste wijst naar de kop van de lijst - het knooppunt vooraan in de lijst. Sinds elke nieuwe instantie van SinglyList bevat geen knooppunt, de standaardwaarde van hoofd is nul en de standaardwaarde van _lengte is 0.
We moeten methoden definiëren die een knooppunt uit een lijst kunnen toevoegen, doorzoeken en verwijderen. Laten we beginnen met het toevoegen van een knooppunt.
1 van 3: waarde toevoegen)
Geweldig, laten we nu de functionaliteit implementeren om knooppunten aan een lijst toe te voegen.
SinglyList.prototype.add = function (value) var node = new Node (value), currentNode = this.head; // 1e use-case: een lege lijst als (! CurrentNode) this.head = node; this._length ++; return node; // 2e use-case: een niet-lege lijst while (currentNode.next) currentNode = currentNode.next; currentNode.next = knooppunt; this._length ++; return node; ;
Het toevoegen van een knoop aan onze lijst omvat vele stappen. Laten we beginnen vanaf het begin van onze methode. We gebruiken het argument van waarde toevoegen) om een nieuw exemplaar van een te maken Knooppunt, die is toegewezen aan een variabele met de naam knooppunt. We verklaren ook een variabele met de naam currentNode en initialiseer het voor de _hoofd van onze lijst. Als er geen knooppunten in de lijst staan, is de waarde van hoofd is nul.
Na dit punt in onze code behandelen we twee use-cases.
De eerste use case is het toevoegen van een knooppunt aan een lege lijst. Als hoofd wijst niet naar een knooppunt en wijst het toe knooppunt als het hoofd van onze lijst, verhoog de lengte van onze lijst met één, en keer terug knooppunt.
De tweede use case is het toevoegen van een knooppunt aan een niet-lege lijst. We gaan de terwijl loop en tijdens elke iteratie evalueren we of currentNode.next wijst naar een ander knooppunt. (Tijdens de eerste iteratie, currentNode wijst altijd naar de kop van een lijst.)
Als het antwoord nee is, wijzen we het toe knooppunt naar currentNode.next En terugkomen knooppunt.
Als het antwoord ja is, komen we in het lichaam van de terwijl lus. In het lichaam, we opnieuw toewijzen currentNode naar currentNode.next. Dit proces wordt herhaald tot currentNode.next wijst niet langer naar een ander knooppunt. Met andere woorden, currentNode wijst naar het laatste knooppunt van onze lijst.
De terwijl lus breekt. Eindelijk, we wijzen knooppunt naar currentNode.next, we verhogen _lengte door één, en dan keren we terug knooppunt.
2 van 3: searchNodeAt (positie)
We kunnen nu knooppunten aan onze lijst toevoegen, maar we kunnen niet naar knooppunten op specifieke posities in onze lijst zoeken. Laten we deze functionaliteit toevoegen en een methode met de naam maken searchNodeAt (positie), welke een argument genaamd accepteert positie. Het argument is naar verwachting een geheel getal dat een node op de n-positie in onze lijst aangeeft.
SinglyList.prototype.searchNodeAt = function (positie) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.'; // 1e use-case: een ongeldige positie als (lengte === 0 || positie < 1 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: een geldige positie tijdens (tel < position) currentNode = currentNode.next; count++; return currentNode; ;
De als statementcontroles voor de eerste use-case: een ongeldige positie wordt doorgegeven als een argument.
Als de index is doorgegeven aan searchNodeAt (positie) is geldig, dan bereiken we de tweede use case-the terwijl lus. Tijdens elke iteratie van de terwijl lus, currentNode-waar eerst naar wijst hoofd-wordt opnieuw toegewezen aan het volgende knooppunt in de lijst. Deze iteratie gaat door totdat de telling gelijk is aan de positie.
Wanneer de lus eindelijk breekt, currentNode wordt teruggestuurd.
3 van 3: Verwijder (positie)
De uiteindelijke methode die we zullen maken, wordt genoemd Verwijder (positie).
SinglyList.prototype.remove = function (positie) var currentNode = this.head, length = this._length, count = 0, message = failure: 'Failure: non-existent node in this list.', BeforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // 1e use-case: een ongeldige positie als (positie < 0 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: het eerste knooppunt wordt verwijderd als (positie === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; // 3e use-case: elk ander knooppunt is verwijderd terwijl (tel < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Onze implementatie van Verwijder (positie) omvat drie use-cases:
hoofd van een lijst) wordt doorgegeven als een argument.De eerste en tweede use-cases zijn de eenvoudigste om te hanteren. Met betrekking tot het eerste scenario wordt een fout gegenereerd als de lijst leeg is of als een niet-bestaande positie wordt doorgegeven.
De tweede use case behandelt de verwijdering van het eerste knooppunt in de lijst, wat ook het geval is hoofd. Als dit het geval is, gebeurt de volgende logica:
hoofd is opnieuw toegewezen aan currentNode.next.deletedNode wijst naar currentNode. currentNode is opnieuw toegewezen aan nul. _lengte van onze lijst met één.deletedNode wordt teruggestuurd. Het derde scenario is het moeilijkst te begrijpen. De complexiteit komt voort uit de noodzaak om twee knooppunten te volgen tijdens elke iteratie van a terwijl lus. Tijdens elke iteratie van onze lus volgen we zowel het knooppunt vóór het knooppunt dat moet worden verwijderd en het knooppunt dat moet worden verwijderd. Wanneer onze lus uiteindelijk het knooppunt bereikt op de positie die we willen verwijderen, eindigt de lus.
Op dit punt houden we verwijzingen naar drie knooppunten: beforeNodeToDelete, nodeToDelete, en deletedNode. Voor het verwijderen nodeToDelete, we moeten de waarde ervan toewijzen volgende naar de volgende waarde van beforeNodeToDelete. Als het doel van deze stap onduidelijk lijkt, herinner jezelf eraan dat we een lijst met gekoppelde knooppunten hebben; alleen het verwijderen van een knoop breekt de link van het eerste knooppunt van de lijst naar het laatste knooppunt van de lijst.
Vervolgens wijzen we toe deletedNode naar nodeToDelete. Vervolgens stellen we de waarde in van nodeToDelete naar nul, verlaag de lengte van de lijst met één, en keer terug deletedNode.
De volledige implementatie van onze lijst is hier:
function Node (data) this.data = data; this.next = null; function SinglyList () this._length = 0; this.head = null; SinglyList.prototype.add = function (value) var node = new Node (value), currentNode = this.head; // 1e use-case: een lege lijst als (! CurrentNode) this.head = node; this._length ++; return node; // 2e use-case: een niet-lege lijst while (currentNode.next) currentNode = currentNode.next; currentNode.next = knooppunt; this._length ++; return node; ; SinglyList.prototype.searchNodeAt = function (positie) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.'; // 1e use-case: een ongeldige positie als (lengte === 0 || positie < 1 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: een geldige positie tijdens (tel < position) currentNode = currentNode.next; count++; return currentNode; ; SinglyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 0, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: het eerste knooppunt wordt verwijderd als (positie === 1) this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; // 3e use-case: elk ander knooppunt is verwijderd terwijl (tel < position) beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; ;
Geweldig, onze implementatie van een enkelvoudig gekoppelde lijst is voltooid. We kunnen nu een gegevensstructuur gebruiken die knooppunten in een lijst toevoegt, verwijdert en doorzoekt die niet-aaneengesloten ruimte in het geheugen innemen.
Op dit moment beginnen al onze bewerkingen vanaf het begin van een lijst en lopen ze naar het einde van een lijst. Met andere woorden, ze zijn unidirectioneel.
Er kunnen gevallen zijn waarin we willen dat onze activiteiten bidirectioneel zijn. Als u deze gebruikssituatie hebt overwogen, heeft u zojuist een dubbel gelinkte lijst beschreven.
Een dubbel gelinkte lijst neemt alle functionaliteit van een enkelvoudig gekoppelde lijst en breidt deze uit voor bidirectionele verplaatsing in een lijst. We kunnen met andere woorden een gekoppelde lijst doorlopen van het eerste knooppunt in de lijst naar het laatste knooppunt in de lijst; en we kunnen van het laatste knooppunt in de lijst doorlopen naar het eerste knooppunt in de lijst.
In deze sectie zullen we onze aandacht primair blijven richten op de verschillen tussen een dubbel gelinkte lijst en een enkelvoudig gekoppelde lijst.
Onze lijst bevat twee constructeurs: Knooppunt en DoublyList. Laten we hun activiteiten schetsen.
gegevens slaat een waarde op.volgende wijst naar het volgende knooppunt in de lijst.voorgaand wijst naar het vorige knooppunt in de lijst._lengte haalt het aantal knooppunten in een lijst op.hoofd wijst een knooppunt toe als de kop van een lijst.staart wijst een knoop toe als de staart van een lijst.waarde toevoegen) voegt een knooppunt toe aan een lijst.searchNodeAt (positie) zoekt naar een knoop op de n-positie in onze lijst.Verwijder (positie) verwijdert een knooppunt uit een lijst.Laat een code schrijven!
Voor onze implementatie maken we een constructor genaamd Knooppunt:
function Node (waarde) this.data = value; this.previous = null; this.next = null;
Om de tweerichtingsbeweging van een dubbel gelinkte lijst te maken, hebben we eigenschappen nodig die in beide richtingen van een lijst wijzen. Deze eigenschappen zijn genoemd voorgaand en volgende.
Vervolgens moeten we een DoublyList en voeg drie eigenschappen toe: _lengte, hoofd, en staart. In tegenstelling tot een enkelvoudig gekoppelde lijst, bevat een dubbel gelinkte lijst een verwijzing naar zowel het begin van een lijst als het einde van een lijst. Sinds elke instantie van een DoublyList wordt geïnstantieerd zonder knooppunten, de standaardwaarden van hoofd en staart zijn ingesteld op nul.
function DoublyList () this._length = 0; this.head = null; this.tail = null;
We gaan nu de volgende methoden verkennen: waarde toevoegen), Verwijder (positie), en searchNodeAt (positie). Al deze methoden werden gebruikt voor een enkelvoudig gekoppelde lijst; ze moeten echter wel herschreven worden voor beweging in twee richtingen.
1 van 3: waarde toevoegen)
DoublyList.prototype.add = function (value) var node = new Node (value); if (this._length) this.tail.next = node; node.previous = this.tail; this.tail = knooppunt; else this.head = node; this.tail = knooppunt; this._length ++; return node; ;
In deze methode hebben we twee scenario's. Ten eerste, als een lijst leeg is, wijs dan toe aan zijn hoofd en staart het knooppunt dat wordt toegevoegd. Ten tweede, als de lijst knooppunten bevat, zoek dan de staart van de lijst en wijs deze toe tail.next het knooppunt dat wordt toegevoegd; evenzo moeten we de nieuwe staart configureren voor bidirectionele beweging. We moeten met andere woorden instellen, tail.previous naar de originele staart.
2 van 3: searchNodeAt (positie)
De implementatie van searchNodeAt (positie) is identiek aan een enkelvoudig gekoppelde lijst. Als je vergeten bent hoe je het moet implementeren, heb ik het hieronder toegevoegd:
DoublyList.prototype.searchNodeAt = function (positie) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.'; // 1e use-case: een ongeldige positie als (lengte === 0 || positie < 1 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: een geldige positie tijdens (tel < position) currentNode = currentNode.next; count++; return currentNode; ;
3 van 3: Verwijder (positie)
Deze methode zal het meest uitdagend zijn om te begrijpen. Ik zal de code weergeven en het dan uitleggen.
DoublyList.prototype.remove = function (positie) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.', BeforeNodeToDelete = null , nodeToDelete = null, deletedNode = null; // 1e use-case: een ongeldige positie als (lengte === 0 || positie < 1 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: het eerste knooppunt wordt verwijderd als (positie === 1) this.head = currentNode.next; // 2e use-case: er is een tweede knooppunt als (! This.head) this.head.previous = null; // 2e use-case: er is geen tweede node else this.tail = null; // 3e use-case: het laatste knooppunt is verwijderd else if (position === this._length) this.tail = this.tail.previous; this.tail.next = null; // 4e use-case: een middelste knooppunt is verwijderd else while (count < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
Verwijder (positie) behandelt vier use-cases:
Verwijder (positie) bestaat niet. In dit geval gooien we een fout. Verwijder (positie) is het eerste knooppunt (hoofd) van een lijst. Als dit het geval is, zullen we toewijzen deletedNode naar hoofd en vervolgens opnieuw toewijzen hoofd naar het volgende knooppunt in de lijst. Op dit moment moeten we overwegen of onze lijst meer dan één knoop heeft. Als het antwoord nee is, hoofd wordt toegewezen aan nul en we zullen de als onderdeel van onze if-else uitspraak. In het lichaam van als, we moeten ook gaan staart naar nul-met andere woorden, we keren terug naar de oorspronkelijke staat van een lege dubbel gelinkte lijst. Als we het eerste knooppunt in een lijst verwijderen en we meer dan één knooppunt in onze lijst hebben, voeren we het anders sectie van onze if-else uitspraak. In dit geval moeten we het juiste instellen voorgaand eigendom van hoofd naar nul-er zijn geen knooppunten voor het hoofd van een lijst. Verwijder (positie) is de staart van een lijst. Eerste, deletedNode is toegewezen aan staart. Tweede, staart wordt opnieuw toegewezen aan het knooppunt voorafgaand aan de staart. Ten derde heeft de nieuwe staart er geen knoop achter en heeft hij de waarde ervan nodig volgende worden ingesteld op nul. terwijl eenmaal lus currentNode wijst naar het knooppunt op de positie die als argument wordt doorgegeven aan Verwijder (positie). Op dit moment wordt de waarde van opnieuw toegewezen beforeNodeToDelete.next naar het knooppunt erna nodeToDelete en omgekeerd, we herwaarderen de waarde van afterNodeToDelete.previous naar het knooppunt ervoor nodeToDelete. Met andere woorden, we verwijderen verwijzingen naar het verwijderde knooppunt en wijzen deze opnieuw toe aan de juiste knooppunten. Vervolgens wijzen we toe deletedNode naar nodeToDelete. Eindelijk, we wijzen nodeToDelete naar nul. Ten slotte verlagen we de lengte van onze lijst en keren we terug deletedNode.
Dit is de volledige implementatie:
function Node (waarde) this.data = value; this.previous = null; this.next = null; function DoublyList () this._length = 0; this.head = null; this.tail = null; DoublyList.prototype.add = function (value) var node = new Node (value); if (this._length) this.tail.next = node; node.previous = this.tail; this.tail = knooppunt; else this.head = node; this.tail = knooppunt; this._length ++; return node; ; DoublyList.prototype.searchNodeAt = function (positie) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.'; // 1e use-case: een ongeldige positie als (lengte === 0 || positie < 1 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: een geldige positie tijdens (tel < position) currentNode = currentNode.next; count++; return currentNode; ; DoublyList.prototype.remove = function(position) var currentNode = this.head, length = this._length, count = 1, message = failure: 'Failure: non-existent node in this list.', beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > lengte) gooi nieuwe fout (message.failure); // 2e use-case: het eerste knooppunt wordt verwijderd als (positie === 1) this.head = currentNode.next; // 2e use-case: er is een tweede knooppunt als (! This.head) this.head.previous = null; // 2e use-case: er is geen tweede node else this.tail = null; // 3e use-case: het laatste knooppunt is verwijderd else if (position === this._length) this.tail = this.tail.previous; this.tail.next = null; // 4e use-case: een middelste knooppunt is verwijderd else while (count < position) currentNode = currentNode.next; count++; beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return message.success; ;
We hebben veel informatie in dit artikel behandeld. Als iets daarvan verwarrend lijkt, lees het dan opnieuw en experimenteer met de code. Als het uiteindelijk logisch voor je is, voel je je trots. U hebt zojuist de mysteries blootgelegd van zowel een afzonderlijk gelinkte lijst als een dubbel gelinkte lijst. U kunt deze gegevensstructuren toevoegen aan uw coderingstoolgordel!
