Nederlands
Menu

Wat is 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.

Japanse benaming: 連結リスト

“Gelinkte lijst (linked list)” komt voor in 10 oefenvragen uit 5 onderwerpen, bijv. Datastructuren en algoritmen, Geheugenhiërarchie en prestaties, Basis van programmeren (pseudocode traceren).

Vakgebied: Datastructuren en algoritmen

Nu oefenen: vragen over Gelinkte lijst (linked list)

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.

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.

“Gelinkte lijst (linked list)” in de toelichting

Vragen met “Gelinkte lijst (linked list)” (10)

  1. Waarom is het doorlopen van bovenstaande gekoppelde lijst doorgaans veel trager dan het sequentieel lezen van een array met evenveel elementen?
  2. 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?
  3. 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.
  4. 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)?
  5. Het volgende programma drukt een gelinkte lijst af, waarvan de elementen met de array next aan elkaar zijn gekoppeld, door die te volgen vanaf het element met index 1. Array-indexen beginnen bij 1. Een next-waarde van 0 markeert het einde van de lijst. Welke reeks waarden wordt afgedrukt?
  6. Het volgende programma voegt „F”, in val[6], direct na „C” (index 3) in de gelinkte lijst A → C → E → D → B in, waarvan de elementen met de array next aan elkaar zijn gekoppeld, en drukt daarna de lijst af vanaf het element met index 1. Array-indexen beginnen bij 1. Een next-waarde van 0 markeert het einde van de lijst. Wat moet er op de plaats van 【a】 staan, zodat de uitvoer A, C, F, E, D, B is?
  7. Bij welke toegang is hardware-prefetching bijzonder effectief?
  8. Welke uitleg over het ABA-probleem, dat bij lock-free datastructuren met CAS aandacht vraagt, is juist?
  9. Welke bewerking wordt op een GPU waarschijnlijk inefficiënt uitgevoerd?
  10. De waarden 1, 2, 3, …, 1000 worden in deze volgorde ingevoegd in een lege binaire zoekboom (zonder herbalancering). Met hoeveel knopen wordt, vanaf de wortel, vergeleken voordat 1000 wordt gevonden?

Verwante termen

Array Prefetching Pointer Hashtabel (hash table) Cacheregel (cache line) Tijdcomplexiteit (O-notatie) ABA-probleem Lock-free LR/SC GPU

Naar de woordenlijst