Als je een gegeven wil opslaan, gebruik je een variabele. Wil je een rij gegevens opslaan, een array. Meerdere rijen, een array van arrays. En als je pas tijdens de uitvoering van je programma weet hoeveel je wilt gaan opslaan, een dynamische array, die je ook nog eens in zelf gealloceerd geheugen kan zetten. Wordt het nog gekker? Jazeker wel, we gaan het nog gekker maken met de linked list.

In de basis is dit nog niet eens zo gek. Bij een linked list werk je met structs die, naast de data die je wilt vastleggen, ook minimaal één pointer bevat naar het volgende element. Eén zo’n element wordt ook wel een node genoemd. Twee nodes zien er dan, schematisch, ongeveer zo uit:

De laatste pointer in de lijst heeft de waarde NULL, zodat je weet dat de lijst aan zijn eind is. En om deze lijst te kunnen benaderen heb je natuurlijk nog een pointer nodig die naar de eerste node wijst.

Deze constructie vergt dat je heel exact zelf regelt waar je data blijft, dat de keten in tact blijft. Je zult geheugen moeten alloceren en vrij geven als je nodes toevoegt of verwijdert. Maar de mogelijkheden zijn daarna wel eindeloos. Waar een dynamische array kan worden gevormd op het moment dat je weet hoe groot die moet worden, kan een linked list groeien en weer krimpen terwijl het programma loopt. Maar het wordt nog mooier. Je kan een node natuurlijk ook van meerdere pointers voorzien, waardoor je bijvoorbeeld ook terug kan wijzen naar de vorige node in je lijst. Of waardoor je aftakkingen in de lijst kan maken. Kortom, je kan de meest complexe samenhangen bouwen die je maar wilt. En ook aan de gegevenskant van een node kan je alle kanten op. Je node is toch al een struct, dus je kan daar iedere combinatie van gegevens in plaatsen die je maar handig vindt. Arrays, strings, hoe wild je maar wilt.

Het is wel echt héél belangrijk dat je het conceptuele model van de linked list constant voor ogen houdt, als je er mee aan de gang wil gaan. Als je dat doet, realiseer je je al snel dat een linked list twee belangrijke elementen van een array mist.

Neem de array int getal[10]. Een belangrijke zaak is dat de array een naam heeft, een soort startpunt dus. Je weet misschien niet waar getal[] in het geheugen staat, maar dat is ook niet nodig. Je kan de array immers simpelweg vinden via de naam getal. Vervolgens is het ook simpel een specifiek element in de array te vinden. Volgnummer achter de naam en je hebt het goede element te pakken. Het derde element hier vindt je bijvoorbeeld simpelweg als getal[2]. En als je alle getallen wilt hebben doet for(int i=0;i++;i<10)getal[i]=i;  de truc al.

Een linked list mist die twee zaken. Als je niet zelf een pointer maakt naar het begin van de lijst, dan ben je je lijst gewoon kwijt. Ook als je na creatie van de lijst die pointer naar de kop van de lijst verandert: lijst weg. Er is geen naam van de lijst waarmee je de lijst kan terugvinden, de pointer naar de kop vervult die functie. Evenmin is er een index-nummer. Je zal moeten werken met een pointer die als het ware over de lijst kan lopen totdat je het gewenste element gevonden hebt. Tenslotte moet je opletten dat je de node-pointers naar de volgende node absoluut in tact houdt, anders verbreek je je lijst en ben je alles waar niet langer een (keten van) pointer(s) naar wijst kwijt. Los van verlies van data betekent het ook nog eens een memory leak. Niet zo fraai dus.

Maar daar staat tegenover dat als je het concept van de list goed begrijpt, de mogelijkheden eindeloos zijn. Het is bijvoorbeeld heel eenvoudig gegevenselementen toe te voegen of te verwijderen aan het einde van de list, maar ook aan het begin of ergens middenin. Bij verwijderen van een element moet je overigens opletten dat je het element eerst losknipt uit de list, en vervolgens met free(*node) het voor die node gereserveerde geheugen vrij geeft. Anders, alweer, een memory leak en dus garbage.

Op GitHub heb ik weer een klein programmaatje opgenomen waarin het principe van een linked list wordt getoond. Wat daarin gebeurt, is het maken van een node-type en dan het starten van een list. Hier worden enkele elementen aan toegevoegd en vervolgens wordt de inhoud op het scherm gezet.

Let op, als je hiermee zelf verder wil gaan, dat je op het eind het gereserveerde geheugen ook weer vrij geeft.

Wie mee wil doen met #klooienmetcomputers kan dat doen via GitHub. Maak een account op www.github.com en zoek naar Abmvk/kmc. Het account Abmvk volgen kan ook. Lezers zijn vrij te gebruiken wat ze willen en om zelf zaken toe te voegen of aan te passen, vragen te stellen of commentaar te leveren.