10 gemeenschappelijke gegevensstructuren uitgelegd met video's + oefeningen

“Slechte programmeurs maken zich zorgen over de code. Goede programmeurs maken zich zorgen over datastructuren en hun relaties. ”- Linus Torvalds, maker van Linux
** Update ** Mijn videocursus over algoritmen is nu live! Bekijk Algorithms in Motion from Manning Publications. Krijg 39% korting op mijn cursus door code ‘39carnes’ te gebruiken! Of je krijgt 50% korting op mijn cursus Deep Learning in Motion met de code ‘vlcarnes2’.

Datastructuren zijn een cruciaal onderdeel van softwareontwikkeling en een van de meest voorkomende onderwerpen voor sollicitatiegesprekvragen van ontwikkelaars.

Het goede nieuws is dat het in feite alleen maar gespecialiseerde indelingen zijn voor het organiseren en opslaan van gegevens.

Ik ga je 10 van de meest voorkomende datastructuren leren - hier in dit korte artikel.

Ik heb video's ingesloten die ik voor elk van deze gegevensstructuren heb gemaakt. Ik heb ook voor elk daarvan codevoorbeelden gekoppeld, die laten zien hoe deze in JavaScript kunnen worden geïmplementeerd.

En om je wat oefening te geven, heb ik gekoppeld aan uitdagingen uit het curriculum van freeCodeCamp.

Merk op dat sommige van deze gegevensstructuren tijdcomplexiteit bevatten in Big O-notatie. Dit is niet voor iedereen inbegrepen, omdat de tijdcomplexiteit soms is gebaseerd op hoe het is geïmplementeerd. Als je meer wilt weten over Big O Notation, bekijk dan mijn artikel erover of deze video van Briana Marie.

Merk ook op dat hoewel ik laat zien hoe deze datastructuren in JavaScript te implementeren, je voor de meeste daarvan nooit zelf zou moeten implementeren, tenzij je een taal op laag niveau zoals C zou gebruiken.

JavaScript (zoals de meeste talen op hoog niveau) heeft ingebouwde implementaties van veel van deze gegevensstructuren.

Als je echter weet hoe je deze gegevensstructuren moet implementeren, krijg je een enorme voorsprong in het zoeken naar een baan voor ontwikkelaars, en kan het handig zijn wanneer je probeert om krachtige code te schrijven.

Gekoppelde lijsten

Een gekoppelde lijst is een van de meest elementaire gegevensstructuren. Het wordt vaak vergeleken met een array, omdat veel andere gegevensstructuren kunnen worden geïmplementeerd met een array of een gekoppelde lijst. Ze hebben elk voor- en nadelen.

Weergave van gekoppelde lijsten

Een gekoppelde lijst bestaat uit een groep knooppunten die samen een reeks vertegenwoordigen. Elk knooppunt bevat twee dingen: de feitelijke gegevens die worden opgeslagen (wat in principe elk type gegevens kan zijn) en een pointer (of link) naar het volgende knooppunt in de reeks. Er zijn ook dubbel gekoppelde lijsten waarbij elke knoop een wijzer heeft naar zowel het volgende item als het vorige item in de lijst.

De meest elementaire bewerkingen in een gekoppelde lijst zijn het toevoegen van een item aan de lijst, het verwijderen van een item uit de lijst en het zoeken in de lijst naar een item.

Bekijk hier de code voor een gekoppelde lijst in JavaScript.

Gelinkte lijst tijd complexiteit
╔═══════════╦═════════╦════════════╗
║ Algoritme ║ Gemiddeld ║ Slechtste geval ║
╠═══════════╬═════════╬════════════╣
║ Spatie ║ O (n) ║ O (n) ║
║ Zoeken ║ O (n) ║ O (n) ║
║ Plaats ║ O (1) ║ O (1) ║
║ Verwijderen ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

freeCodeCamp-uitdagingen

  • Werk met knooppunten in een gekoppelde lijst
  • Maak een Linked List Class
  • Elementen verwijderen uit een gekoppelde lijst
  • Zoeken in een gekoppelde lijst
  • Elementen verwijderen uit een gekoppelde lijst per index
  • Voeg elementen toe aan een specifieke index in een gekoppelde lijst
  • Maak een dubbel gekoppelde lijst
  • Een dubbel gekoppelde lijst omkeren

stapels

Een stapel is een basisgegevensstructuur waarin u alleen items boven aan de stapel kunt invoegen of verwijderen. Het lijkt een beetje op een stapel boeken. Als je een boek in het midden van de stapel wilt bekijken, moet je eerst alle boeken erboven verwijderen.

De stapel wordt beschouwd als LIFO (Last In First Out) - wat betekent dat het laatste item dat u in de stapel plaatst, het eerste item is dat uit de stapel komt

Stack weergave

Er zijn drie hoofdbewerkingen die op stapels kunnen worden uitgevoerd: een item in een stapel plaatsen ('push' genoemd), een item uit de stapel verwijderen ('pop' genoemd) en de inhoud van de stapel weergeven (soms 'pip' genoemd) ').

Bekijk de code voor een stapel in JavaScript hier.

Stapel tijd complexiteit
╔═══════════╦═════════╦════════════╗
║ Algoritme ║ Gemiddeld ║ Slechtste geval ║
╠═══════════╬═════════╬════════════╣
║ Spatie ║ O (n) ║ O (n) ║
║ Zoeken ║ O (n) ║ O (n) ║
║ Plaats ║ O (1) ║ O (1) ║
║ Verwijderen ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

freeCodeCamp-uitdagingen

  • Leer hoe een stapel werkt
  • Maak een stapelklasse

wachtrijen

Je kunt een rij als een rij mensen in een supermarkt beschouwen. De eerste in de rij is de eerste die wordt geserveerd. Net als een wachtrij.

Wachtrijweergave

Een wachtrij wordt beschouwd als FIFO (First In First Out) om aan te tonen hoe deze toegang heeft tot gegevens. Dit betekent dat zodra een nieuw element is toegevoegd, alle elementen die eerder zijn toegevoegd, moeten worden verwijderd voordat het nieuwe element kan worden verwijderd.

Een wachtrij heeft slechts twee hoofdbewerkingen: enqueue en dequeue. Enqueue betekent een item achter in de wachtrij plaatsen en dequeue betekent het verwijderen van het voorste item.

Bekijk hier de code voor een wachtrij in JavaScript.

Wachttijd complexiteit
╔═══════════╦═════════╦════════════╗
║ Algoritme ║ Gemiddeld ║ Slechtste geval ║
╠═══════════╬═════════╬════════════╣
║ Spatie ║ O (n) ║ O (n) ║
║ Zoeken ║ O (n) ║ O (n) ║
║ Plaats ║ O (1) ║ O (1) ║
║ Verwijderen ║ O (1) ║ O (1) ║
╚═══════════╩═════════╩════════════╝

freeCodeCamp-uitdagingen

  • Maak een wachtrijklasse
  • Maak een Priority Queue Class
  • Maak een cirkelvormige wachtrij

sets

Stel weergave in

De ingestelde gegevensstructuur slaat waarden op zonder een bepaalde volgorde en zonder herhaalde waarden. Naast het toevoegen en verwijderen van elementen aan een set, zijn er een paar andere belangrijke setfuncties die met twee sets tegelijk werken.

  • Union - Dit combineert alle items van twee verschillende sets en retourneert dit als een nieuwe set (zonder duplicaten).
  • Kruising - Gegeven twee sets, retourneert deze functie een andere set met alle items die deel uitmaken van beide sets.
  • Verschil: hiermee wordt een lijst met items geretourneerd die zich in één set bevinden, maar NIET in een andere set.
  • Subset - Dit retourneert een Booleaanse waarde die aangeeft of alle elementen in een set zijn opgenomen in een andere set.

Bekijk hier de code om een ​​set in JavaScript te implementeren.

freeCodeCamp-uitdagingen

  • Maak een Set Class
  • Verwijderen uit een set
  • Grootte van de set
  • Voer een Union uit op twee sets
  • Voer een kruising uit op twee gegevenssets
  • Voer een verschil uit op twee gegevenssets
  • Voer een subsetcontrole uit op twee gegevenssets
  • Maken en toevoegen aan sets in ES6
  • Verwijder items uit een set in ES6
  • Gebruik .heeft en .grootte op een ES6-set
  • Gebruik Spread en Notes voor ES5 Set () -integratie

Kaarten

Een kaart is een gegevensstructuur die gegevens opslaat in sleutel / waarde-paren waarbij elke sleutel uniek is. Een kaart wordt soms een associatieve array of woordenboek genoemd. Het wordt vaak gebruikt voor het snel opzoeken van gegevens. Kaarten staan ​​de volgende dingen toe:

Kaartweergave
  • de toevoeging van een paar aan de collectie
  • het verwijderen van een paar uit de verzameling
  • de aanpassing van een bestaand paar
  • het opzoeken van een waarde die aan een bepaalde sleutel is gekoppeld

Bekijk hier de code om een ​​kaart in JavaScript te implementeren.

freeCodeCamp-uitdagingen

  • Maak een kaartgegevensstructuur
  • Maak een ES6 JavaScript-kaart

Hashtafels

Weergave van hashtabel en hashfunctie

Een hashtabel is een kaartgegevensstructuur die sleutel / waarde-paren bevat. Het gebruikt een hash-functie om een ​​index te berekenen in een reeks emmers of slots, waaruit de gewenste waarde kan worden gevonden.

De hash-functie neemt meestal een string als invoer en voert een numerieke waarde uit. De hash-functie moet altijd hetzelfde uitvoernummer voor dezelfde invoer geven. Wanneer twee ingangen hash naar dezelfde numerieke uitgang, wordt dit een botsing genoemd. Het doel is om weinig botsingen te hebben.

Dus wanneer u een sleutel / waarde-paar in een hashtabel invoert, wordt de sleutel door de hash-functie geleid en omgezet in een getal. Deze numerieke waarde wordt vervolgens gebruikt als de feitelijke sleutel waarmee de waarde wordt opgeslagen. Wanneer u opnieuw toegang probeert te krijgen tot dezelfde sleutel, zal de hashing-functie de sleutel verwerken en hetzelfde numerieke resultaat retourneren. Het nummer wordt vervolgens gebruikt om de bijbehorende waarde op te zoeken. Dit biedt gemiddeld een zeer efficiënte O (1) -opzoektijd.

Bekijk hier de code voor een hashtabel.

Hash tabel tijd complexiteit
╔═══════════╦═════════╦════════════╗
║ Algoritme ║ Gemiddeld ║ Slechtste geval ║
╠═══════════╬═════════╬════════════╣
║ Spatie ║ O (n) ║ O (n) ║
║ Zoeken ║ O (1) ║ O (n) ║
║ Plaats ║ O (1) ║ O (n) ║
║ Verwijderen ║ O (1) ║ O (n) ║
╚═══════════╩═════════╩════════════╝

freeCodeCamp-uitdagingen

  • Maak een hashtabel

Binaire zoekboom

Binaire zoekboom

Een boom is een gegevensstructuur die bestaat uit knooppunten. Het heeft de volgende kenmerken:

  1. Elke boom heeft een wortelknoop (bovenaan).
  2. Het hoofdknooppunt heeft nul of meer onderliggende knooppunten.
  3. Elk kindknooppunt heeft nul of meer kindknooppunten, enzovoort.

Een binaire zoekboom voegt deze twee kenmerken toe:

  1. Elke knoop heeft maximaal twee kinderen.
  2. Voor elke knoop zijn de linker afstammelingen kleiner dan de huidige knoop, die kleiner is dan de rechter afstammelingen.

Met binaire zoekbomen kunnen items snel worden opgezocht, toegevoegd en verwijderd. De manier waarop ze zijn ingesteld, betekent dat elke vergelijking gemiddeld de bewerkingen toelaat om ongeveer de helft van de boom over te slaan, zodat elke opzoeking, invoeging of verwijdering evenredig is aan de logaritme van het aantal items dat in de boom is opgeslagen.

Bekijk hier de code voor een binaire zoekboom in JavaScript.

Binaire zoektijd complexiteit
╔═══════════╦══════════╦════════════╗
║ Algoritme ║ Gemiddeld ║ Slechtste geval ║
╠═══════════╬══════════╬════════════╣
║ Spatie ║ O (n) ║ O (n) ║
║ Zoeken ║ O (log n) ║ O (n) ║
║ Invoegen ║ O (log n) ║ O (n) ║
║ Verwijderen ║ O (log n) ║ O (n) ║
╚═══════════╩══════════╩════════════╝

freeCodeCamp-uitdagingen

  • Zoek de minimum- en maximumwaarde in een binaire zoekboom
  • Voeg een nieuw element toe aan een binaire zoekboom
  • Controleer of een element aanwezig is in een binaire zoekboom
  • Vind de minimale en maximale hoogte van een binaire zoekboom
  • Gebruik Depth First Search in een binaire zoekboom
  • Gebruik eerst breedte zoeken in een binaire zoekboom
  • Verwijder een bladknooppunt in een binaire zoekboom
  • Verwijder een knooppunt met één kind in een binaire zoekboom
  • Verwijder een knooppunt met twee kinderen in een binaire zoekboom
  • Keer een binaire boom om

proberen

De trie (uitgesproken als 'probeer'), of prefixboom, is een soort zoekboom. Een trie slaat gegevens op in stappen waarbij elke stap een knooppunt in de trie is. Probaties worden vaak gebruikt om woorden op te slaan voor snel zoeken, zoals een functie voor het automatisch aanvullen van woorden.

Trie-weergave

Elke knoop in een taal trie bevat een letter van een woord. Je volgt de takken van een trie om een ​​woord te spellen, één letter per keer. De stappen beginnen te vertakken wanneer de volgorde van de letters afwijkt van de andere woorden in de trie of wanneer een woord eindigt. Elke knoop bevat een letter (gegevens) en een boolean die aangeeft of de knoop de laatste knoop in een woord is.

Kijk naar de afbeelding en je kunt woorden vormen. Begin altijd bij de root-knoop bovenaan en werk naar beneden. De hier getoonde trie bevat het woord ball, bat, doll, do, dork, dorm, send, sense.

Bekijk hier de code voor een trie in JavaScript.

freeCodeCamp-uitdagingen

  • Maak een Trie-zoekboom

Binaire Hoop

Een binaire heap is een ander type boomgegevensstructuur. Elk knooppunt heeft maximaal twee kinderen. Het is ook een complete boom. Dit betekent dat alle niveaus volledig zijn ingevuld tot het laatste niveau en het laatste niveau van links naar rechts is gevuld.

Min en max heap representaties

Een binaire heap kan een minimale of een maximale hoop zijn. In een maximale heap zijn de toetsen van bovenliggende knooppunten altijd groter dan of gelijk aan die van de kinderen. In een min hoop zijn de toetsen van ouderknooppunten kleiner dan of gelijk aan die van de kinderen.

De volgorde tussen niveaus is belangrijk, maar de volgorde van knooppunten op hetzelfde niveau is niet belangrijk. In de afbeelding ziet u dat het derde niveau van de min heap de waarden 10, 6 en 12 heeft. Die getallen zijn niet in orde.

Bekijk hier de code voor een hoop in JavaScript.

Binaire heap tijd complexiteit
╔═══════════╦══════════╦════════════╗
║ Algoritme ║ Gemiddeld ║ Slechtste geval ║
╠═══════════╬══════════╬════════════╣
║ Spatie ║ O (n) ║ O (n) ║
║ Zoeken ║ O (n) ║ O (n) ║
║ Plaats ║ O (1) ║ O (log n) ║
║ Verwijderen ║ O (log n) ║ O (log n) ║
║ Peek ║ O (1) ║ O (1) ║
╚═══════════╩══════════╩════════════╝

freeCodeCamp-uitdagingen

  • Plaats een element in een maximale hoop
  • Verwijder een element uit een maximale hoop
  • Implementeer Heap Sorteer met een minimale hoop

diagram

Grafieken zijn verzamelingen knooppunten (ook hoekpunten genoemd) en de verbindingen (randen genoemd) daartussen. Grafieken worden ook wel netwerken genoemd.

Een voorbeeld van grafieken is een sociaal netwerk. De knooppunten zijn mensen en de randen zijn vriendschap.

Er zijn twee hoofdtypen grafieken: gericht en niet-gericht. Niet-gerichte grafieken zijn grafieken zonder enige richting op de randen tussen knooppunten. Gerichte grafieken zijn daarentegen grafieken met een richting in de randen.

Twee veel voorkomende manieren om een ​​grafiek weer te geven zijn een aangrenzende lijst en een aangrenzende matrix.

Nabijheid matrix grafiek

Een aangrenzende lijst kan worden weergegeven als een lijst waarbij de linkerkant de knoop is en de rechterkant een lijst met alle andere knooppunten waarmee deze is verbonden.

Een aangrenzende matrix is ​​een raster met getallen, waarbij elke rij of kolom een ​​ander knooppunt in de grafiek vertegenwoordigt. Op het snijpunt van een rij en een kolom staat een getal dat de relatie aangeeft. Nullen betekenen dat er geen rand of relatie is. Eén betekent dat er een relatie is. Getallen hoger dan één kunnen worden gebruikt om verschillende gewichten te tonen.

Traversale algoritmen zijn algoritmen om knooppunten in een grafiek te doorlopen of te bezoeken. De belangrijkste soorten traversale algoritmen zijn breedte-eerst zoeken en diepte-eerst zoeken. Een van de toepassingen is om te bepalen hoe dicht knooppunten bij een hoofdknooppunt zijn. Bekijk de eerste breedte-zoekopdracht in JavaScript in de onderstaande video.

Bekijk de code voor breedte-eerst zoeken op een aangrenzende matrixgrafiek in JavaScript.

Adjacency list (graph) tijdcomplexiteit
╔═══════════════╦════════════╗
║ Algoritme ║ Tijd ║
╠═══════════════╬════════════╣
║ Opslag ║ O (| V | + | E |) ║
║ Voeg Vertex ║ O (1) ║ toe
║ Rand toevoegen ║ O (1) ║
║ Verwijder Vertex ║ O (| V | + | E |) ║
║ Verwijder rand ║ O (| E |) ║
║ Vraag ║ O (| V |) ║
╚═══════════════╩════════════╝

freeCodeCamp-uitdagingen

  • Adjacency List
  • Nabijheid Matrix
  • Incidentie Matrix
  • Breedte-eerste zoekopdracht
  • Diepte-eerste zoekopdracht

Meer

Het boek Grokking Algorithms is het beste boek over dit onderwerp als je nieuw bent met datastructuren / algoritmen en geen computerwetenschappelijke achtergrond hebt. Het gebruikt eenvoudig te begrijpen uitleg en leuke, met de hand getekende illustraties (door de auteur die een hoofdontwikkelaar is bij Etsy) om enkele van de gegevensstructuren in dit artikel uit te leggen.

Of bekijk mijn videocursus op basis van dat boek: Algorithms in Motion from Manning Publications. Krijg 39% korting op mijn cursus door code ‘39carnes’ te gebruiken!