Nederlands
Menu

Array versus gelinkte lijst: toegang, invoegen en verwijderen, geheugenindeling, cache en tijdcomplexiteit

Een array slaat elementen van hetzelfde type zonder tussenruimte naast elkaar in het geheugen op, zodat de positie van elk element uit zijn index kan worden berekend en in constante tijd kan worden gelezen of geschreven. Een gelinkte lijst is een datastructuur waarin elk element een waarde en een pointer naar het volgende element bevat, en de elementen worden verbonden door die pointers te volgen, zodat ze op verschillende plaatsen in het geheugen kunnen staan. Een array leest snel, maar invoegen of verwijderen in het midden betekent dat de elementen erachter moeten opschuiven. Een gelinkte lijst kan invoegen of verwijderen door alleen pointers te veranderen zodra de positie bekend is, maar het i-de element lezen betekent vanaf het begin doorlopen. De vuistregel: gebruik een array als je vooral op index leest, en een gelinkte lijst als je vaak op bekende posities invoegt of verwijdert.

KenmerkArrayGelinkte lijst
GeheugenindelingDe elementen staan naast elkaar in één aaneengesloten blokDe elementen liggen verspreid en zijn met pointers verbonden
Het i-de element lezenO(1): het adres is beginadres + i × elementgrootteO(n): vanaf het begin i keer de pointers volgen
Een waarde zoekenO(n) lineair zoeken als niet gesorteerd; O(log n) met binair zoeken als gesorteerdO(n), ook als gesorteerd; binair zoeken kan niet, omdat je niet naar het midden kunt springen
Invoegen of verwijderen in het middenO(n): de elementen erachter schuiven één voor één opO(1) als de positie (het voorgaande element) bekend is; alleen pointers veranderen
Achteraan toevoegenO(1) als er vrije ruimte is; een dynamische array die zijn capaciteit verdubbelt, kopieert af en toe alles, maar is gemiddeld (geamortiseerd) O(1)O(1) als een pointer naar het laatste element wordt bijgehouden
Van grootte veranderenDe grootte van een array met vaste grootte ligt vast bij het aanmaken; vergroten betekent een nieuw blok reserveren en kopiërenRuimte wordt per element gereserveerd, dus de lijst groeit alleen zoveel als nodig
GeheugengebruikAlleen de elementen zelf (een dynamische array houdt wat reservecapaciteit aan)Extra ruimte voor een pointer per element (twee in een dubbel gelinkte lijst)
CachevriendelijkheidGoed: de elementen zijn aaneengesloten, dus sequentieel lezen benut caches en prefetching goedSlecht: de elementen liggen vaak verspreid, dus zelfs dezelfde O(n)-doorloop kan veel trager zijn dan bij een array
Typische toepassingenTabellen die op index worden gelezen en geschreven, matrices en afbeeldingen, data om te sorteren of binair te doorzoeken, implementaties van stacks en wachtrijenReeksen met veel invoegingen en verwijderingen, chaining in hashtabellen, beheer van vrije ruimte

De getalswaarden zijn typische ordegroottes en variëren per procesgeneratie en product.

Wanneer welke variant?

Array
Wanneer elementen vooral op index worden gelezen en geschreven of van voor naar achter worden gelezen. Omdat caches er goed mee werken, zijn arrays (ook dynamische arrays) op hedendaagse computers in veel situaties sneller.
Gelinkte lijst
Wanneer er veel invoegingen en verwijderingen in het midden zijn en je al een pointer naar de positie hebt. Omdat elementen opnieuw worden gekoppeld zonder te verplaatsen, wordt hij ook gebruikt wanneer de adressen van elementen niet mogen veranderen.

Veelgestelde vragen

Invoegen in een gelinkte lijst is O(1), dus waarom zijn arrays in de praktijk soms sneller?

Om twee redenen. Ten eerste: als de invoegpositie vanaf het begin moet worden gezocht, kost dat zoeken O(n), dus de hele bewerking is O(n), net als bij een array, ook al is het invoegen zelf O(1). Ten tweede: elementen in een array opschuiven is een kopie van aaneengesloten geheugen die caches goed benut en zeer snel is, terwijl het doorlopen van een gelinkte lijst verspreide adressen element voor element leest en vaak missers in de cache oplevert. Tijdcomplexiteit beschrijft hoe de kosten groeien als de data groeit; de werkelijke snelheid moet je meten.

Hoe verschillen enkel en dubbel gelinkte lijsten?

In een enkel gelinkte lijst heeft elk element alleen een pointer naar het volgende element, dus je kunt hem alleen van voor naar achter doorlopen. Een dubbel gelinkte lijst heeft ook een pointer naar het vorige element, dus je kunt hem ook achterwaarts doorlopen, en met een pointer naar een element kan dat element in O(1) worden verwijderd. Daar staat tegenover dat elk element één pointer meer heeft en dat er meer pointers moeten worden bijgewerkt.

Wat is een dynamische array?

Een array die van grootte kan veranderen: als de capaciteit opraakt, reserveert hij een groter blok en kopieert hij alles daarheen. Als de capaciteit elke keer verdubbelt, is het totale aantal kopieën maar ongeveer gelijk aan het aantal elementen, dus achteraan toevoegen is gemiddeld O(1). Lezen op index is O(1), net als bij een gewone array.

Test uw begrip

Welke beschrijving van een gelinkte lijst (een lijst waarin elk element een pointer naar het volgende element bevat) is juist in vergelijking met een array?

  1. AAls het element vlak vóór de invoegpositie bekend is, kan een element worden ingevoegd door alleen pointers te wijzigen, zonder andere elementen te verplaatsen; om het i-de element te lezen moet de lijst echter vanaf het begin worden doorlopen
  2. BDe positie van het i-de element kan worden berekend, dus elk element kan in constante tijd O(1) worden gelezen
  3. CDe elementen staan zonder tussenruimte aaneengesloten in het geheugen, dus bij het lezen in volgorde werken caches en prefetching goed
Antwoord en toelichting tonen

Antwoord: A. Als het element vlak vóór de invoegpositie bekend is, kan een element worden ingevoegd door alleen pointers te wijzigen, zonder andere elementen te verplaatsen; om het i-de element te lezen moet de lijst echter vanaf het begin worden doorlopen

In een gelinkte lijst kost invoegen of verwijderen O(1) zodra de positie bekend is, want alleen de pointers van de buren hoeven te worden herschreven. Om het i-de element te lezen moeten echter vanaf het begin i pointers worden gevolgd, wat O(n) kost. Een array kan het adres van het i-de element berekenen uit het beginadres en de elementgrootte en leest dus elk element in O(1), maar invoegen in het midden kost O(n), omdat de elementen erachter moeten opschuiven. Bovendien staan de elementen van een array aaneengesloten, zodat caches en prefetching goed werken, terwijl de knopen van een gelinkte lijst vaak verspreid in het geheugen liggen; daardoor kan zelfs een doorloop van dezelfde orde O(n) veel trager zijn.

Een dynamische array reserveert, als er een element wordt toegevoegd terwijl hij vol is, een nieuw gebied met de dubbele capaciteit en kopieert alle elementen daarheen. Hoeveel elementkopieën worden er in totaal gemaakt als 1000 elementen één voor één worden toegevoegd aan een lege array met capaciteit 1?

  1. A10
  2. B1023
  3. C499.500
Antwoord en toelichting tonen

Antwoord: B. 1023

De capaciteit verdubbelt telkens als de array vol is, van 1 naar 2, 4, …, 512, en elke keer worden alle aanwezige elementen gekopieerd, dus het totale aantal kopieën is 1 + 2 + 4 + … + 512 = 1023. Voor 1000 toevoegingen is dat ongeveer één kopie per element, dus de kosten per toevoeging zijn gemiddeld constant: geamortiseerd O(1). Zou de capaciteit telkens maar met 1 groeien, dan zouden de kopieën samen 1 + 2 + … + 999 = 499.500 bedragen, wat O(n²) is. 10 is het aantal keren dat opnieuw geheugen is gereserveerd, niet het aantal gekopieerde elementen.

Welke vergelijking van chaining (de elementen op dezelfde positie aan elkaar koppelen in een gelinkte lijst) en open adressering (een andere vrije positie in de tabel zoeken) als methoden om botsingen in een hashtabel af te handelen is juist? De bezettingsgraad (load factor) is het aantal opgeslagen elementen gedeeld door de grootte van de tabel.

  1. AChaining kan elementen opslaan ook als de bezettingsgraad groter is dan 1, maar open adressering kan niet meer elementen opslaan dan de tabel groot is, en het aantal pogingen neemt sterk toe als de bezettingsgraad 1 nadert
  2. BBij open adressering treden geen botsingen op, dus een zoekactie kost altijd één poging, ongeacht de bezettingsgraad
  3. CBij chaining blijft de zoekinspanning gelijk, hoe hoog de bezettingsgraad ook wordt
Antwoord en toelichting tonen

Antwoord: A. Chaining kan elementen opslaan ook als de bezettingsgraad groter is dan 1, maar open adressering kan niet meer elementen opslaan dan de tabel groot is, en het aantal pogingen neemt sterk toe als de bezettingsgraad 1 nadert

Chaining koppelt elementen op dezelfde positie tot lijsten en kan dus meer elementen opslaan dan de tabel groot is, maar de gemiddelde lijstlengte groeit evenredig met de bezettingsgraad, en de zoekinspanning ook. Open adressering slaat alles in de tabel zelf op en kan dus hoogstens zoveel elementen bevatten als de tabel groot is; het aantal pogingen om een vrije plaats te vinden neemt sterk toe als de bezettingsgraad 1 nadert. Bij beide methoden is het gebruikelijk om de tabel te vergroten en alle elementen opnieuw in te voegen (rehashing) zodra de bezettingsgraad een gekozen grens overschrijdt, bijvoorbeeld ongeveer 0,5 tot 0,75. Ook bij open adressering treden botsingen op; ze worden opgevangen door een vrije positie te zoeken.

  1. Wat is de meest passende reden dat open adressering met lineair proberen bij een hashtabel met veel elementen en een bezettingsgraad van ongeveer 0,5 vaak sneller is dan chaining (elementen koppelen met gelinkte lijsten)?
  2. Wat is een voorwaarde om binair zoeken te kunnen gebruiken, dat de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert?

Oefenvragen over Datastructuren en algoritmen

Belangrijke termen uitgelegd

Array
Een datastructuur die waarden van hetzelfde type achter elkaar opslaat en elk element aanwijst met een index. Omdat de elementen aaneengesloten in het geheugen staan, kan de positie van elk element uit de index worden berekend, zodat elk element in constante tijd kan worden gelezen of geschreven. Sommige talen laten indexen bij 0 beginnen, sommige notaties bij 1.
Gelinkte lijst (linked list)
Datastructuur waarin elk element een waarde en een pointer naar het volgende element bevat, en de elementen worden verbonden door de pointers te volgen. Is de positie bekend, dan zijn invoegen en verwijderen pointerwijzigingen van O(1), maar het i-de element lezen vraagt een doorloop vanaf het begin, O(n). De elementen liggen vaak verspreid in het geheugen, dus caches werken minder goed dan bij arrays.
Pointer
Een variabele waarvan de waarde het geheugenadres is van een variabele, een array-element, een functie of een ander object. In C wordt een pointer gedeclareerd zoals in int *p; &x levert het adres van x op, en *p leest of schrijft het object waarnaar p wijst. Als een geheel getal bij een pointer wordt opgeteld, schuift die op in eenheden van de grootte van het type waarnaar hij wijst. In de meeste expressies wordt de naam van een array omgezet in een pointer naar het eerste element, zodat a[i] hetzelfde betekent als *(a + i). Een pointerwaarde die nergens naar wijst, heet een NULL-pointer.
Tijdcomplexiteit (O-notatie)
Beschrijving van hoe de rekeninspanning (tijdcomplexiteit) of het geheugen (ruimtecomplexiteit) dat een algoritme nodig heeft, groeit met het aantal gegevens n. Ze wordt geschreven in O-notatie, zoals O(n), O(n log n) of O(n²), waarbij constante factoren en termen van lagere orde wegvallen.
Binair zoeken (binary search)
Zoekmethode voor gesorteerde gegevens die de gezochte waarde met het middelste element vergelijkt en het zoekbereik telkens halveert. Ze vindt een waarde tussen n gegevens in hoogstens ⌊log₂ n⌋ + 1 vergelijkingen, dus haar complexiteit is O(log n). De gegevens moeten gesorteerd zijn.
Hashtabel (hash table)
Datastructuur die met een hashfunctie uit een sleutel een opslagpositie berekent, waardoor zoeken, invoegen en verwijderen gemiddeld O(1) kosten. Botsingen, waarbij verschillende sleutels op dezelfde positie uitkomen, worden afgehandeld met chaining of open adressering.
Ruimtelijke lokaliteit (spatial locality)
Eigenschap dat na toegang tot een bepaald adres er snel ook toegang tot nabijgelegen adressen is. Een voorbeeld is het achtereenvolgens lezen van een array; dit is de reden dat per cacheline in één keer wordt ingelezen.

Verwante vergelijkingen