Welke gegevensstructuren bestaan er?

De volgende hoofdgegevensstructuren bestaan:

Primitive:

• Gehele getallen (Integer)
• Kommagetallen (Floating-point numbers)
• Booleaanse waarden (Boolean)
• Tekens (Character)

Abstract:

• Array: Geordende verzameling van elementen van hetzelfde type, toegang via index met constante tijd.
• Gekoppelde lijst (Linked List): Verzameling van knooppunten, elk bevat gegevens en een verwijzing naar de volgende knoop. Efficiënt toevoegen/verwijderen aan begin/eind, toegang via index - $O(n)$.
  • Enkelvoudig gekoppelde lijst (Singly Linked List)
  • Dubbel gekoppelde lijst (Doubly Linked List)
  • Circulaire gekoppelde lijst (Circular Linked List)
• Stack: LIFO-structuur (Last-In, First-Out). Operaties: push (toevoegen), pop (verwijderen), peek (bekijken bovenste element).

  struct Stack<Element> {
      private var elements: [Element] = []
  
      mutating func push(_ element: Element) {
          elements.append(element)
      }
  
      mutating func pop() -> Element? {
          return elements.popLast()
      }
  
      func peek() -> Element? {
          return elements.last
      }
  
      var isEmpty: Bool {
          return elements.isEmpty
      }
  }
  

• Queue: FIFO-structuur (First-In, First-Out). Operaties: enqueue (toevoegen), dequeue (verwijderen), peek (eerste element bekijken).

  struct Queue<Element> {
      private var elements: [Element] = []
  
      mutating func enqueue(_ element: Element) {
          elements.append(element)
      }
  
      mutating func dequeue() -> Element? {
          guard !elements.isEmpty else { return nil }
          return elements.removeFirst()
      }
  
      func peek() -> Element? {
          return elements.first
      }
  
      var isEmpty: Bool {
          return elements.isEmpty
      }
  }
  

• Hash-tabel (Hash Table) / Woordenboek (Dictionary) / Associatieve array (Associative Array): Collectie van "sleutel-waarde" paren, die efficiënte zoek-, toevoeg- en verwijderbewerkingen mogelijk maken op basis van de sleutel met behulp van een hashfunctie.

  var dictionary = [String: Any]() // Voorbeeld van woordenboek in Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Set: Ongeordende collectie van unieke elementen. Ondersteunt operaties: toevoegen, verwijderen, controleren op aanwezigheid, vereniging, doorsnede, verschil.

  var set: Set<Int> = [1, 2, 3] // Voorbeeld van set in Swift
  set.insert(4)
  let containsTwo = set.contains(2)
  

• Boom (Tree): Hiërarchische datastructuur, bestaande uit knooppunten verbonden door takken. Heeft een wortelknoop en afstammende knooppunten.
  • Binaire boom (Binary Tree)
  • Binaire zoekboom (Binary Search Tree - BST)
  • Gebalanceerde binaire boom (Balanced Binary Tree) - AVL, rood-zwart boom
  • B-Tree (B-Tree)
• Graf (Graph): Verzamelings van knooppunten (vertices) en verbindingen (edges), die de knooppunten verbinden. Kan gericht of ongericht, gewogen of ongewogen zijn.

Het begrijpen van deze datastructuren is cruciaal voor het schrijven van efficiënte en schaalbare code. De juiste structuur kiezen hangt af van de prestatie-eisen (zoeken, invoegen, verwijderen) en de aard van de gegevens.