Gelinkte lijst

In de informatica is een gelinkte lijst (Engels: linked list) een van de meest fundamentele datastructuren bij het programmeren van computers.

Het bestaat uit een reeks van data-elementen, records, elk met een aantal datavelden en één of twee verwijzingen naar een volgende en/of vorig data-element. Een gelinkte lijst wordt ook wel een zelfverwijzend datatype genoemd omdat het verwijzingen bevat naar andere data-elementen van hetzelfde type.

Het is toegestaan om op elke plek in een gelinkte lijst data-elementen in te voegen of te verwijderen door de verwijzing van het voorgaande element naar respectievelijk het nieuw toe te voegen, dan wel het tweede volgend element te laten wijzen. Het is echter niet mogelijk om meteen een willekeurig data-element direct te benaderen in tegenstelling tot bijvoorbeeld een array: om een element op de N-de positie te benaderen, moet eerst de hele lijst tot positie N doorlopen worden.

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. Talen zoals C en C++ moeten geheugenwijzers (pointers) en geheugenadressering gebruiken om deze datastructuur te realiseren.

Varianten

Enkelvoudig gelinkte lijsten

De eenvoudigste variant van een gelinkte lijst is de enkelvoudig gelinkte lijst, die alleen één verwijzing bevat naar het volgende data-element. Deze verwijzing wijst naar het volgende data-element of 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 de eerste en het laatste data-element met elkaar verbonden. Dit kan gedaan worden bij zowel enkelvoudig als tweevoudig gelinkte lijsten. Om een circulair gelinkte lijst te doorlopen, is te beginnen bij elk willekeurig data-element. Bij enkelvoudig circulair gelinkte lijsten gaat men daarna in één richting totdat je weer bij het oorspronkelijke data-element uitkomt. Bij tweevoudig circulair gelinkte lijsten kan dat in elke richting. Daardoor heeft een circulair gelinkte lijst geen begin of einde. Dit type lijst is vooral handig om buffers te beheren bij gegevensinvoer en in situaties waarbij je een verwijzing naar een willekeurig data-element bezit en toegang nodig hebt 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)

Mediabestanden

Zie de categorie Lists van Wikimedia Commons voor meer mediabestanden.