Lijststructuren

Lijststructuren zijn data-structuren die een geordende verzameling elementen bewaren en bewerkingen op die volgorde mogelijk maken, zoals het toevoegen of verwijderen van elementen, het opvragen van een element op een specifieke positie en het doorlopen van de lijst.

Er zijn verschillende typen lijststructuren, elk met eigen voor- en nadelen. Dynamische array-achtige lijsten (ook wel resizable arrays of vectors genoemd) gebruiken contigu geheugen en bieden snelle random access (O(1)) en efficiënte opslag wanneer de lijst niet vaak wordt gewijzigd. Bij uitbreiding kan de opslag groeien, wat een amortized O(1) tijd per append oplevert maar bij verschuivingen kosten meebrengt.

Koppelde lijsten bestaan uit knopen met een waarde en verwijzingen naar opvolger(s). Een singly linked list heeft een verwijzing naar de volgende knoop; een doubly linked list heeft ook een verwijzing naar de vorige knoop. Voordelen: efficiënte inserties en verwijderingen op elk punt zonder verschuivingen; nadeel: langzame toegang tot het n-de element (O(n)). Circulaire varianten zorgen ervoor dat de laatste knoop terugverwijst naar de eerste.

Andere gangbare lijststructuren zijn stacks en queues die vaak zijn opgebouwd uit lijsten. Een stack volgt het LIFO-principe; een queue het FIFO-principe. Een deque combineert de mogelijkheden van beide kanten. Deze structuren kunnen op zowel arrays als gekoppelde lijsten zijn gebaseerd.

Keuzes hangen af van de vereisten voor snelheden van toegang, insertie, geheugengebruik en cache-efficiëntie. In de praktijk vormen lijststructuren een basis in algoritmes en programmeertalen voor het beheren van sequentiële data.