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.