Gelinkte lijst

In de informatica is een gelinkte lijst (Engels: linked list) een van de fundamentele datastructuren bij het programmeren van computers. Een gelinkte lijst bestaat uit een reeks van data-elementen, records genoemd, elk met een aantal datavelden en een verwijzing (link) naar het volgende data-element; sommige typen hebben ook nog een verwijzing naar het vorige element. Een gelinkte lijst wordt ook wel een zelfverwijzend datatype genoemd, omdat het verwijzingen bevat naar andere data-elementen van hetzelfde type.

Op elke plek in een gelinkte lijst kunnen data-elementen worden ingevoegd of verwijderd door de verwijzingen aan te passen. Het is echter niet mogelijk een willekeurig data-element direct te benaderen: om een element op de nde positie te benaderen, moet eerst de hele lijst tot positie n doorlopen worden. Met bijvoorbeeld een array kan dit wel: daarbij kan het adres van het nde element in één keer worden berekend.

Er zijn diverse typen van gelinkte lijsten, zoals de enkelvoudig, tweevoudig en circulair gelinkte lijsten. Het beginelement van de lijst wordt het hoofd (head) genoemd en meestal heeft het laatste element van de lijst een verwijzing naar een zogenaamde "aarding" (ground of terminator): een speciale waarde, meestal "Null" of een voor de programmeertaal vergelijkbare constante, die het einde van de lijst aanduidt.

Gelinkte lijsten kunnen worden geïmplementeerd in de meeste programmeertalen. Programmeertalen zoals Lisp en Scheme hebben een ingebouwde datastructuur met bijhorende operaties om gelinkte lijsten te gebruiken. In talen zoals C en C++ worden gewoonlijk (pointers) en geheugenadressering gebruikt om deze datastructuur te realiseren.

Varianten

Enkelvoudig gelinkte lijst

De eenvoudigste variant van een gelinkte lijst is de enkelvoudig gelinkte lijst, waarvan elk element alleen een verwijzing heeft naar het volgende data-element of voor het laatste element naar een nulwaarde die het einde van een gelinkte lijst aangeeft.

Een enkelvoudig gelinkte lijst die drie gehele (integer) getallen bevat.

Tweevoudig gelinkte lijsten

Een meer geavanceerde variant van een gelinkte lijst is een tweevoudig gelinkte lijst. Elk data-element heeft twee verwijzingen, één naar het vorige en één naar het volgende data-element.

Een tweevoudig gelinkte lijst met drie elementen.

Circulair gelinkte lijst

In een circulair gelinkte lijst zijn alle data-element met elkaar verbonden. Daardoor heeft een circulair gelinkte lijst geen begin of einde. Dit kan net als bij enkelvoudige en tweevoudig gelinkte lijsten in één richting of in beide richtingen gedaan worden. Om een circulair gelinkte lijst te doorlopen kan begonnen worden bij elk willekeurig data-element. Bij enkelvoudig circulair gelinkte lijsten gaat men daarna in één richting totdat men weer bij het oorspronkelijke data-element uitkomt. Bij tweevoudig circulair gelinkte lijsten kan dat in beide richtingen. Dit type lijst is vooral handig om buffers te beheren bij gegevensinvoer en in situaties waarbij men een verwijzing naar een willekeurig data-element bezit en toegang nodig heeft tot alle andere data-elementen in de lijst – aangezien men bij een enkelvoudig, dan wel een dubbel gelinkte lijst respectievelijk aan het begin of aan het einde van de lijst moet beginnen om alle elementen te kunnen doorlopen.

Een enkelvoudig circulair gelinkte lijst met drie elementen.

Zie ook

Stack (informatica)

Zie de categorie Linked lists van Wikimedia Commons voor mediabestanden over dit onderwerp.