Gelinkte lijst
Van Wikipedia
In de informatica is een gelinkte lijst (Engels: linked list) één van de meest fundamentele datastructuren bij het programmeren van computers. Het bestaat uit een reeks van data-elementen, 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 daar onder andere zijn 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.
Inhoud |
[bewerk] Varianten
[bewerk] 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.
[bewerk] Tweevoudig gelinke lijsten
Een meer geavanceerde variant van een gelinkte lijst is een tweevoudig gelinkte lijst. Elke data-element heeft twee verwijzingen, één naar het vorige en één naar het volgende data-element.
Een voorbeeld van een tweevoudig gelinkte lijst.
[bewerk] Circulair gelinke 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, kan je beginnen bij elk willekeurig data-element in de lijst in elke richting totdat je weer bij het oorspronkelijke data-element uitkomt. 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 je bij een enkelvoudig, dan wel een dubbel gelinkte lijst respectievelijk aan het begin of aan het begin of einde van de lijst moet beginnen om alle elementen te kunnen doorlopen.
