Gelinkte lijst

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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.

Op elke plek in een gelinkte lijst kunnen data-elementen worden ingevoegd verwijderd door de verwijzing van het voorgaande element naar respectievelijk het nieuwe 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: om een element op de N-de positie te benaderen, moet eerst de hele lijst tot positie N doorlopen worden. Met bijvoorbeeld een array kan dit wel: dan kan het adres van het N-de 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[bewerken]

Enkelvoudig gelinkte lijsten[bewerken]

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.

Singly-linked-list.svg
Een enkelvoudig gelinkte lijst die drie gehele (integer) getallen bevat.

Tweevoudig gelinkte lijsten[bewerken]

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.

Doubly-linked-list.svg
Een tweevoudig gelinkte lijst met drie elementen.

Circulair gelinkte lijst[bewerken]

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.

Circularly-linked-list.svg
Een enkelvoudig circulair gelinkte lijst met drie elementen.

Zie ook[bewerken]