Terug in 2009 daagde ik mezelf uit om gedurende het hele jaar één blogbericht per week te schrijven. Ik had gelezen dat de beste manier om meer verkeer naar een blog te krijgen, was om consequent berichten te plaatsen. Een post per week leek een realistisch doel vanwege alle artikelideeën die ik had, maar het bleek dat ik ruim 52 ideeën te kort kwam. Ik groef in enkele half geschreven hoofdstukken die uiteindelijk Professioneel JavaScript zouden worden en vond veel materiaal over klassieke computerwetenschappelijke onderwerpen, waaronder gegevensstructuren en algoritmen. Ik nam dat materiaal en zette het om in verschillende berichten in 2009 en (en een paar in 2012), en kreeg er veel positieve feedback op.

Nu, bij het tienjarig jubileum van die berichten, heb ik besloten om ze bij te werken, opnieuw te publiceren en uit te breiden met behulp van JavaScript in 2019. Het is interessant geweest om te zien wat er is veranderd en wat niet, en ik hoop dat je ze leuk vindt.

Wat is een gekoppelde lijst?

Een gekoppelde lijst is een gegevensstructuur die meerdere waarden op een lineaire manier opslaat. Elke waarde in een gekoppelde lijst is opgenomen in zijn eigen node, een object dat de gegevens bevat samen met een link naar de volgende node in de lijst. De link is een pointer naar een ander node-object of null als er geen volgende node is. Als elke node slechts één pointer heeft naar een andere node (meestal next genoemd) dan wordt de lijst beschouwd als een singly linked list (of gewoon gelinkte lijst) terwijl als elke node twee links heeft (meestal previous en next) dan wordt het beschouwd als een doublely linked list. In deze post richt ik me op enkelvoudig gekoppelde lijsten.

Waarom een gekoppelde lijst gebruiken?

Het belangrijkste voordeel van gekoppelde lijsten is dat ze een willekeurig aantal waarden kunnen bevatten terwijl ze alleen de hoeveelheid geheugen gebruiken die nodig is voor die waarden. Geheugenbehoud was erg belangrijk op oudere computers waar geheugen schaars was. In die tijd moest je bij een ingebouwde array in C opgeven hoeveel items de array kon bevatten en het programma zou die hoeveelheid geheugen reserveren. Het reserveren van dat geheugen betekende dat het niet kon worden gebruikt voor de rest van het programma of voor andere programma’s die op hetzelfde moment draaiden, zelfs als het geheugen nooit vol was. Op machines met weinig geheugen, kon je met arrays gemakkelijk zonder beschikbaar geheugen komen te zitten. Gekoppelde lijsten werden gemaakt om dit probleem te omzeilen.

Hoewel ze oorspronkelijk bedoeld waren voor beter geheugenbeheer, werden gekoppelde lijsten ook populair wanneer ontwikkelaars niet wisten hoeveel items een array uiteindelijk zou bevatten. Het was veel eenvoudiger om een gelinkte lijst te gebruiken en waarden toe te voegen als dat nodig was, dan om het maximale aantal waarden dat een array zou kunnen bevatten nauwkeurig te schatten. Als zodanig worden linked lists vaak gebruikt als de basis voor ingebouwde datastructuren in verschillende programmeertalen.

Het ingebouwde JavaScript Array type is niet geïmplementeerd als een linked list, hoewel de grootte dynamisch is en altijd de beste optie is om mee te beginnen. Je zou je hele carrière door kunnen gaan zonder een linked list in JavaScript te hoeven gebruiken, maar linked lists zijn nog steeds een goede manier om te leren over het maken van je eigen datastructuren.

Het ontwerp van een linked list

Het belangrijkste onderdeel van een linked list is de node-structuur. Elke node moet een aantal gegevens bevatten en een pointer naar de volgende node in de lijst. Hier is een eenvoudige weergave in JavaScript:

class LinkedListNode { constructor(data) { this.data = data; this.next = null; }}

In de klasse LinkedListNode bevat de data property de waarde die het item in de gekoppelde lijst moet opslaan en de next property is een pointer naar het volgende item in de lijst. De next property begint als null omdat je de volgende node nog niet kent. U kunt dan een gelinkte lijst maken met behulp van de LinkedListNode class zoals deze:

// create the first nodeconst head = new LinkedListNode(12);// add a second nodehead.next = new LinkedListNode(99);// add a third nodehead.next.next = new LinkedListNode(37);

De eerste node in een gelinkte lijst wordt gewoonlijk de head genoemd, dus de head identifier in dit voorbeeld vertegenwoordigt de eerste node. Het tweede knooppunt wordt gemaakt en toegewezen aan head.next om een lijst met twee items te maken. Een derde node wordt toegevoegd door deze toe te wijzen aan head.next.next, dat is de next pointer van de tweede node in de lijst. De next pointer van de derde node in de lijst blijft null. De volgende afbeelding toont de resulterende gegevensstructuur.

De structuur van een gekoppelde lijst stelt u in staat om alle gegevens te doorlopen door de next pointer op elk knooppunt te volgen. Hier is een eenvoudig voorbeeld van hoe je een gelinkte lijst doorkruist en elke waarde naar de console afdrukt:

let current = head;while (current !== null) { console.log(current.data); current = current.next;}

Deze code gebruikt de variabele current als de pointer die door de gelinkte lijst beweegt. De variabele current wordt geïnitialiseerd op het hoofd van de lijst en de while-lus gaat door totdat current null is. Binnen de lus wordt de waarde die is opgeslagen op de current node afgedrukt en vervolgens wordt de next pointer gevolgd naar de volgende node.

De meeste operaties met gelinkte lijsten gebruiken dit traversal algoritme of iets dergelijks, dus het begrijpen van dit algoritme is belangrijk om gelinkte lijsten in het algemeen te begrijpen.

De klasse LinkedList

Als u een gekoppelde lijst in C zou schrijven, zou u op dit punt kunnen stoppen en uw taak als voltooid beschouwen (hoewel u een struct zou gebruiken in plaats van een klasse om elk knooppunt weer te geven). In object-georiënteerde talen zoals JavaScript is het echter gebruikelijker om een klasse te maken om deze functionaliteit in te kapselen. Hier is een eenvoudig voorbeeld:

const head = Symbol("head");class LinkedList { constructor() { this = null; }}

De klasse LinkedList vertegenwoordigt een gekoppelde lijst en zal methoden bevatten voor interactie met de gegevens die deze bevat. De enige eigenschap is een symbool eigenschap genaamd head die een pointer zal bevatten naar het eerste knooppunt in de lijst. Een symbool eigenschap wordt gebruikt in plaats van een string eigenschap om duidelijk te maken dat deze eigenschap niet bedoeld is om te worden gewijzigd buiten de klasse.

Het toevoegen van nieuwe gegevens aan de lijst

Het toevoegen van een item in een gekoppelde lijst vereist het lopen door de structuur om de juiste locatie te vinden, het creëren van een nieuwe node, en het invoegen van het op zijn plaats. Het enige speciale geval is wanneer de lijst leeg is, in welk geval u eenvoudig een nieuwe node maakt en deze toewijst aan head:

const head = Symbol("head");class LinkedList { constructor() { this = null; } add(data) { // create a new node const newNode = new LinkedListNode(data); //special case: no items in the list yet if (this === null) { // just set the head to the new node this = newNode; } else { // start out by looking at the first node let current = this; // follow `next` links until you reach the end while (current.next !== null) { current = current.next; } // assign the node into the `next` pointer current.next = newNode; } }}

De methode add() accepteert een enkel argument, een willekeurig stuk data, en voegt het toe aan het eind van de lijst. Als de lijst leeg is (this is null) dan wijst u this gelijk aan het nieuwe knooppunt toe. Als de lijst niet leeg is, dan moet je de reeds bestaande lijst doorkruisen om de laatste node te vinden. Dit gebeurt in een while-lus die begint bij this en de next-links van elke node volgt tot de laatste node is gevonden. De laatste node heeft een next eigenschap gelijk aan null, dus het is belangrijk om de traversal op dat punt te stoppen in plaats van wanneer current null is (zoals in de vorige sectie). U kunt dan de nieuwe node toewijzen aan die next eigenschap om de gegevens aan de lijst toe te voegen.

De complexiteit van de add() methode is O(n) omdat u de hele lijst moet doorkruisen om de locatie te vinden om een nieuwe node in te voegen. U kunt deze complexiteit terugbrengen tot O(1) door het einde van de lijst (meestal de staart genoemd) te volgen in aanvulling op de kop, waardoor u onmiddellijk een nieuwe knoop op de juiste positie kunt invoegen.

Gegevens uit de lijst ophalen

Gelinkte lijsten staan geen willekeurige toegang tot de inhoud toe, maar u kunt nog steeds gegevens op elke gegeven positie ophalen door de lijst te doorlopen en de gegevens terug te sturen. Om dit te doen, voegt u een methode get() toe die een op nul gebaseerde index van de op te halen gegevens accepteert, zoals deze:

class LinkedList { // other methods hidden for clarity get(index) { // ensure `index` is a positive value if (index > -1) { // the pointer to use for traversal let current = this; // used to keep track of where in the list you are let i = 0; // traverse the list until you reach either the end or the index while ((current !== null) && (i < index)) { current = current.next; i++; } // return the data if `current` isn't null return current !== null ? current.data : undefined; } else { return undefined; } }}

De methode get() controleert eerst of index een positieve waarde is, anders retourneert het undefined. De variabele i wordt gebruikt om bij te houden hoe diep de traversal in de lijst is gegaan. De lus zelf is dezelfde basis traversal die u eerder zag met de toegevoegde voorwaarde dat de lus moet eindigen wanneer i gelijk is aan index. Dat betekent dat er twee voorwaarden zijn waaronder de lus kan verlaten:

1. current is null, wat betekent dat de lijst korter is dan index.
2. i is gelijk aan index, wat betekent dat current het knooppunt is op de index positie.

Als current null is, dan wordt undefined teruggegeven en anders current.data. Deze controle zorgt ervoor dat get() nooit een fout zal gooien voor een index die niet in de lijst voorkomt (hoewel u zou kunnen besluiten om een fout te gooien in plaats van undefined terug te geven).

De complexiteit van de methode get() varieert van O(1) bij het verwijderen van het eerste knooppunt (geen traversal nodig) tot O(n) bij het verwijderen van het laatste knooppunt (traverseren van de hele lijst is vereist). Het is moeilijk om de complexiteit te reduceren omdat er altijd een zoektocht nodig is om de juiste waarde te identificeren om terug te geven.

Verwijderen van gegevens uit een gelinkte lijst

Verwijderen van gegevens uit een gelinkte lijst is een beetje lastig omdat u ervoor moet zorgen dat alle next pointers geldig blijven nadat een node is verwijderd. Als je bijvoorbeeld het tweede knooppunt in een lijst met drie knooppunten wilt verwijderen, moet je ervoor zorgen dat de next eigenschap van het eerste knooppunt nu naar het derde knooppunt wijst in plaats van naar het tweede. Door het tweede knooppunt op deze manier over te slaan, wordt het effectief uit de lijst verwijderd.

De bewerking verwijderen bestaat eigenlijk uit twee bewerkingen:

1. Vind de opgegeven index (hetzelfde algoritme als in get())
2. Verwijder de node op die index

Het vinden van de opgegeven index is hetzelfde als in de methode get(), maar in deze lus moet je ook de node opsporen die voor current komt, omdat je de next pointer van de vorige node moet aanpassen.

Er zijn ook vier speciale gevallen om te overwegen:

1. De lijst is leeg (geen traversal mogelijk)
2. De index is kleiner dan nul
3. De index is groter dan het aantal items in de lijst
4. De index is nul (verwijderen van de kop)

In de eerste drie gevallen kan de verwijderingsoperatie niet worden voltooid, en dus is het zinvol om een fout te gooien; het vierde speciale geval vereist het herschrijven van de this eigenschap. Hier volgt hoe de implementatie van een remove() methode eruit ziet:

class LinkedList { // other methods hidden for clarity remove(index) { // special cases: empty list or invalid `index` if ((this === null) || (index < 0)) { throw new RangeError(`Index ${index} does not exist in the list.`); } // special case: removing the first node if (index === 0) { // temporary store the data from the node const data = this.data; // just replace the head with the next node in the list this = this.next; // return the data at the previous head of the list return data; } // pointer use to traverse the list let current = this; // keeps track of the node before current in the loop let previous = null; // used to track how deep into the list you are let i = 0; // same loops as in `get()` while ((current !== null) && (i < index)) { // save the value of current previous = current; // traverse to the next node current = current.next; // increment the count i++; } // if node was found, remove it if (current !== null) { // skip over the node to remove previous.next = current.next; // return the value that was just removed from the list return current.data; } // if node wasn't found, throw an error throw new RangeError(`Index ${index} does not exist in the list.`); }}

De remove() methode controleert eerst op twee speciale gevallen, een lege lijst (this is null) en een index die kleiner is dan nul. In beide gevallen wordt een fout gegooid.

Het volgende speciale geval is wanneer index 0 is, wat betekent dat u de lijstkop verwijdert. De nieuwe lijstkop moet de tweede node in de lijst zijn, dus je kunt this gelijk stellen aan this.next. Het maakt niet uit of er maar één node in de lijst is, want this zou gelijk worden aan null, wat betekent dat de lijst leeg is na de verwijdering. Het enige addertje onder het gras is om de gegevens van de oorspronkelijke kop op te slaan in een lokale variabele, data, zodat die kunnen worden geretourneerd.

Met drie van de vier speciale gevallen afgehandeld, kun je nu verder gaan met een traversal vergelijkbaar met die in de get() methode. Zoals eerder vermeld, is deze lus iets anders in die zin dat de variabele previous wordt gebruikt om het knooppunt bij te houden dat net voor current staat, omdat die informatie nodig is om een knooppunt te verwijderen. Net als bij get() kan current bij het afsluiten van de lus null zijn, wat aangeeft dat de index niet werd gevonden. In dat geval wordt er een foutmelding gegeven, anders wordt previous.next op current.next gezet, waardoor current daadwerkelijk van de lijst wordt verwijderd. De gegevens die zijn opgeslagen op current worden geretourneerd als laatste stap.

De complexiteit van de methode remove() is hetzelfde als get() en varieert van O(1) bij het verwijderen van de eerste node tot O(n) bij het verwijderen van de laatste node.

De lijst iterable maken

Om gebruikt te kunnen worden met de JavaScript for-of loop en array destructuring, moeten collecties van gegevens iterables zijn. De ingebouwde JavaScript verzamelingen zoals Array en Set zijn standaard iterable, en u kunt uw eigen klassen iterable maken door een Symbol.iterator generator methode op de klasse te specificeren. Ik geef er de voorkeur aan om eerst een values()-generatormethode te implementeren (die overeenkomt met de methode die op ingebouwde verzamelingsklassen wordt gevonden) en Symbol.iterator values() dan rechtstreeks te laten aanroepen.

De methode values() hoeft alleen maar een basistraverse van de lijst uit te voeren en yield de gegevens die elk knooppunt bevat:

class LinkedList { // other methods hidden for clarity *values(){ let current = this; while (current !== null) { yield current.data; current = current.next; } } () { return this.values(); } }

De methode values() is gemarkeerd met een sterretje (*) om aan te geven dat het een generatormethode is. De methode doorloopt de lijst en gebruikt yield om elk stukje gegevens dat hij tegenkomt terug te sturen. (Merk op dat de Symbol.iterator methode niet is gemarkeerd als een generator, omdat het een iterator teruggeeft van de values() generator methode.)

Gebruik van de klasse

Eenmaal voltooid, kunt u de gelinkte lijst implementatie als volgt gebruiken:

const list = new LinkedList();list.add("red");list.add("orange");list.add("yellow"); // get the second item in the listconsole.log(list.get(1)); // "orange"// print out all itemsfor (const color of list) { console.log(color);}// remove the second item in the list console.log(list.remove(1)); // "orange" // get the new first item in the listconsole.log(list.get(1)); // "yellow"// convert to an arrayconst array1 = ;const array2 = ;

Deze basisimplementatie van een gelinkte lijst kan worden aangevuld met een size eigenschap om het aantal knooppunten in de lijst te tellen, en andere bekende methoden zoals indexOf(). De volledige broncode is beschikbaar op GitHub bij mijn Computer Science in JavaScript project.

Conclusie

Gelinkte lijsten zijn niet iets wat je waarschijnlijk elke dag zult gebruiken, maar ze zijn een fundamentele gegevensstructuur in de informatica. Het concept van het gebruik van knooppunten die naar elkaar wijzen wordt in veel andere gegevensstructuren gebruikt en is ingebouwd in veel programmeertalen op hoger niveau. Een goed begrip van hoe gelinkte lijsten werken is belangrijk voor een goed algemeen begrip van hoe je andere gegevensstructuren kunt maken en gebruiken.

Voor JavaScript-programmering ben je bijna altijd beter af met het gebruik van de ingebouwde verzamelingsklassen zoals Array dan met het maken van je eigen. De ingebouwde verzamelingsklassen zijn al geoptimaliseerd voor productiegebruik en worden goed ondersteund in verschillende uitvoeringsomgevingen.