edubun
Nederlands
English한국어EspañolPortuguêsFrançaisDeutschItalianoNederlandsРусскийBahasa Indonesia日本語
Home›Programmeren

Gegevensstructuren

Zeven hoofdstukken over gegevens opslaan in programma's: arrays en dynamische arrays, stapels, wachtrijen en ringbuffers, gelinkte lijsten, hashtabellen, binaire zoekbomen en hoe je daartussen kiest. Elk hoofdstuk heeft een lab waarin je invoegen en verwijderen stap voor stap uitvoert en het werk telt, twee JavaScript-oefeningen die op de pagina worden gecontroleerd en 10 oefenvragen met uitleg.

Voortgang

Over deze cursus

Een programma moet zijn gegevens ergens bewaren. Die keuze bepaalt hoeveel stappen elke bewerking kost. a[3] uit een array lezen kost één stap: het adres is beginadres plus index maal celgrootte. De eerste van 1000 waarden uit een JavaScript-array halen met shift verplaatst de overige 999. Een ringbuffer doet hetzelfde werk in één stap. Door te tellen maak je dat verschil zichtbaar.

De zeven hoofdstukken behandelen arrays, stapels, wachtrijen, gelinkte lijsten, hashtabellen, binaire zoekbomen en de keuze ertussen. Bij dynamische arrays verdubbelt de capaciteit van 5 naar 10, zodat de volgende vier pushes elk 1 stap kosten. Een stapel werkt volgens laatst erin, eerst eruit; een wachtrij volgens eerst erin, eerst eruit. Een ringbuffer is een wachtrij met vaste grootte die een nieuwe waarde moet weigeren als er geen vrije cel is. Gelinkte lijsten lonen bij veranderingen vooraan: twee aanwijzers veranderen en verder beweegt niets. Een hashtabel toont 7 buckets met 12, 25, 33, 47 en 70 en gebruikt h(k) = k mod 7. De teller voegt 1 toe voor de hash en 1 voor elke vergeleken sleutel in de keten.

Elk hoofdstuk heeft een lab dat invoegen en verwijderen stap voor stap uitvoert en het werk telt. Eén waarschuwing is belangrijk. Geef de beginboom gesorteerde invoer en dezelfde zeven sleutels vormen een lange keten in plaats van een gebalanceerde boom. Een perfect gebalanceerde boom met 1023 knopen heeft hoogte 9. De slechtste zoekactie kost dus 10 vergelijkingen, terwijl lineair zoeken naar een ontbrekende sleutel tussen 1023 sleutels er 1023 kost.

Voor je begint

De oefeningen zijn in JavaScript geschreven. Volg daarom eerst JavaScript, vooral de onderdelen over arrays en objecten. Ook Algoritmen helpt: in deze cursus vergelijk je structuren door de stappen van elke bewerking te tellen. Daarbij komen binair zoeken en Big O steeds terug.

Als je klaar bent

Je verklaart één stap voor de miljoenste arraywaarde tegenover een miljoen verplaatsingen voor vooraan toevoegen. Je controleert {[()()]} met een stapel, bouwt een ringbufferwachtrij, wijzigt lijstverbindingen, hasht met mod, houdt een zoekboom gebalanceerd en kiest een passende structuur.

  1. 1ArraysDe miljoenste waarde van een array lezen kost één stap, maar een nieuwe waarde vooraan dezelfde array zetten verplaatst een miljoen waarden.
  2. 2StapelsControleren of de haakjes in {[()()]} goed gepaard zijn vraagt één stapel en 8 pushes en pops, één voor elk haakje.
  3. 3WachtrijenDe eerste van 1000 waarden uit een JavaScript-array halen met shift verplaatst de andere 999; een ringbuffer doet hetzelfde in één stap.
  4. 4Gelinkte lijstenVooraan een gelinkte lijst een waarde toevoegen verandert twee verwijzingen, of de lijst nu 4 waarden of 4 miljoen bevat.
  5. 5HashtabellenAls 47 in een tabel met 7 buckets staat, gaat de computer direct naar bucket 47 mod 7 = 5 in plaats van de hele tabel te doorzoeken.
  6. 6Binaire zoekbomenEen gebalanceerde binaire zoekboom met 1023 sleutels vindt elke sleutel in hoogstens 10 vergelijkingen; opgebouwd uit gesorteerde invoer kunnen dezelfde sleutels er 1023 vragen.
  7. 7Een gegevensstructuur kiezenBij 1023 sleutels doet lineair zoeken naar een ontbrekende sleutel 1023 vergelijkingen, binair zoeken 10 en een hashtabel met 1023 buckets in het lab hoogstens 6.

Verwante cursussen

  • JavaScript
    Twaalf hoofdstukken voor complete beginners, van een eerste console.log-regel tot een fooiencalculator en FizzBuzz. Elk hoofdstuk heeft code die je op de pagina kunt bewerken en uitvoeren, oefeningen die je uitvoer controleren, flitskaarten voor de termen en 10 tot 12 vragen ‘Wat drukt deze code af?’ met uitleg.
  • Algoritmen
    Zeven hoofdstukken over de methoden achter zoeken, sorteren en een weg door een doolhof vinden: het algoritme van Euclides, lineair en binair zoeken, vijf sorteermethoden, grote-O-notatie, recursie met de Torens van Hanoi en breedte-eerst en diepte-eerst zoeken. Elk hoofdstuk heeft een lab waarin je het algoritme stap voor stap uitvoert en vergelijkingen telt, JavaScript-oefeningen die op de pagina worden gecontroleerd, flitskaarten en 10 tot 12 oefenvragen met uitleg.
  • Hoe computers werken · Computerbasis en typen
    Een computer bewaart alles, van foto's tot programma's, als patronen van 0 en 1 en bewerkt die met kleine schakelaars. Zes hoofdstukken bouwen van onderaf op: binaire getallen, bytes en tekst, logische poorten, optellen met poorten, de cyclus ophalen, decoderen en uitvoeren van de CPU en het geheugen. Je kunt bits omschakelen, poorten verbinden, overdrachten door een opteller zien lopen en een kleine computer per fase door zijn programma laten gaan.
  • HTML · Websites maken
    Tien eenheden over het met de hand schrijven van webpagina's, van het skelet dat elke pagina deelt tot een kleine afgeronde pagina met een menu, een afbeelding, een tabel en een formulier. Elke eenheid heeft een live-editor die je pagina laat zien terwijl je typt en hem controleert, plus flitskaarten en 9 tot 11 oefenvragen met uitleg.
Bronnen van deze cursus (11)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
  • lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
  • 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
  • 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
  • MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
  • Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
  • ECMAScript 2025 Language Specification (tc39.es/ecma262)
  • 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
  • Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
  • D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
  • "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

Geraadpleegd: 2026-10-18