Linked lists en stacks
Voorbij Arrays - Dynamische Data
Arrays zijn geweldig als je de grootte van je data vooraf kent. Maar wat als data onvoorspelbaar binnenkomt - een stroom sensorwaarden, een wachtrij met taken voor een AI, of een gespreksgeschiedenis die bij elk bericht groeit? Dan heb je structuren nodig die soepel mee groeien en krimpen.
Hier komen linked lists, stacks en queues in beeld - het dynamische trio.
Linked Lists - Knooppunten en Pointers
Een linked list slaat items op als een keten van knooppunten (nodes). Elk knooppunt bevat twee dingen: de data zelf en een pointer (verwijzing) naar het volgende knooppunt.
[data: "A" | next: →] → [data: "B" | next: →] → [data: "C" | next: null]
Anders dan bij arrays staan knooppunten niet naast elkaar in het geheugen. Ze kunnen overal staan - de pointer vertelt je simpelweg waar het volgende knooppunt te vinden is.
Linked Lists vs Arrays
| Operatie | Array | Linked List | |----------|-------|-------------| | Toegang via index | O(1) ⚡ | O(n) 🐢 | | Invoegen aan begin | O(n) 🐢 | O(1) ⚡ | | Invoegen in midden | O(n) 🐢 | O(1)* ⚡ | | Verwijderen uit midden | O(n) 🐢 | O(1)* ⚡ | | Geheugengebruik | Compact | Extra (pointers) |
*Zodra je de positie gevonden hebt - het vinden is nog steeds O(n).
Wanneer Linked Lists Winnen
- Veel invoegingen en verwijderingen: Als je constant items toevoegt en verwijdert in het midden, vermijden linked lists het kostbare opschuiven dat arrays vereisen.
- Onbekende grootte: Als je niet weet hoeveel items je gaat opslaan, groeit een linked list per knooppunt zonder herschaling.
- Basis voor andere structuren: Stacks, queues en complexere structuren worden vaak bovenop linked lists gebouwd.
De tabbalk van je browser laat je vrij tabbladen openen, sluiten en herschikken. Zou een array of een linked list beter passen voor het beheren van open tabbladen? Bedenk wat er gebeurt als je een tabblad in het midden sluit.
Stacks - Last In, First Out (LIFO)
Een stack werkt precies als een stapel borden: je legt bovenop en pakt van bovenaf. Het laatst geplaatste item is het eerste dat eraf gaat.
Discussion
Sign in to join the discussion