Gelinkte lijsten

Vooraan een gelinkte lijst een waarde toevoegen verandert twee verwijzingen, of de lijst nu 4 waarden of 4 miljoen bevat.

Waarden die naar de volgende wijzen

Een array bewaart waarden naast elkaar, waardoor de voorkant veranderen duur is. Een gelinkte lijst laat die regel los. Elke waarde staat in een eigen klein record, een knoop, en de knopen kunnen overal in het geheugen staan. De MIT-notities van 6.006 beschrijven een knoop met twee velden: het item en next, een verwijzing naar de volgende knoop. De lijst zelf onthoudt alleen de eerste knoop, de head. De next van de laatste knoop is null en markeert het einde.

Om de lijst te lezen begin je bij head en volg je next-verwijzingen één voor één, zoals een keten briefjes die elk zeggen waar het volgende verstopt ligt. Dat kost iets. Er bestaat geen formule voor het adres van de vierde knoop, dus de waarde op positie i krijgen betekent i + 1 knopen bezoeken. MIT geeft get at(i) voor een gelinkte lijst als O(n), terwijl de array het in één stap kon.

// one node per value: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// walk the list
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

De lijst veranderen door opnieuw te koppelen

De winst komt wanneer je de lijst verandert. Om vooraan een nieuwe waarde te zetten, maak je een knoop waarvan next de huidige head is en laat je head naar de nieuwe knoop wijzen. Twee gewijzigde verwijzingen en niets anders beweegt. De voorste knoop verwijderen is één wijziging: laat head naar head.next wijzen. Vergelijk dat met de array, waar dezelfde bewerkingen elke waarde verplaatsten.

In het midden zit het werk in de plek vinden. Om op positie i in te voegen, loop je naar de knoop ervoor (i bezoeken) en verander je dan dezelfde twee verwijzingen: new.next = prev.next en dan prev.next = new. De volgorde telt. Als je eerst prev.next instelt, gaat de rest van de lijst verloren omdat niets er meer naar wijst. In het lab is één stap een knoop bezoeken of een verwijzing wijzigen. Invoegen op positie 2 in een lijst van 4 knopen kost dus 2 bezoeken plus 2 wijzigingen, 4 stappen.

Wanneer gebruik je er een?

Een gelinkte lijst past goed als de meeste wijzigingen plaatsvinden op een plek waar je al een verwijzing naar hebt, zoals vooraan, en je zelden positie i nodig hebt. Je kunt wachtrijen en stapels uit gelinkte lijsten bouwen en ook de ketens binnen een hashtabel in het volgende hoofdstuk. Er zijn varianten. Een dubbel gelinkte lijst geeft elke knoop ook een prev-verwijzing, zodat je achteruit kunt lopen en een knoop in één stap kunt verwijderen zodra je die hebt. Naast head ook een tail-verwijzing bijhouden maakt achteraan toevoegen goedkoop.

In dagelijks JavaScript schrijf je zelden een gelinkte lijst, omdat arrays goed zijn geoptimaliseerd en caches in moderne processors waarden naast elkaar bevoordelen. Het idee blijft belangrijk: bomen, grafen en veel bibliotheekstructuren worden precies zo uit knopen en verwijzingen opgebouwd.