Welche Datenstrukturen gibt es?

Es gibt die folgenden grundlegenden Datenstrukturen:

Primitive:

• Ganze Zahlen (Integer)
• Gleitkommazahlen (Floating-point numbers)
• Boolesche Werte (Boolean)
• Zeichen (Character)

Abstrakte:

• Array: Geordnete Sammlung von Elementen desselben Typs, Zugriff per Index mit konstanter Zeit.
• Verkettete Liste (Linked List): Sammlung von Knoten, jeder enthält Daten und eine Referenz auf den nächsten Knoten. Effiziente Einfügungen/Entfernungen am Anfang/Ende, Zugriff per Index - $O(n)$.
  • Einfach verkettete Liste (Singly Linked List)
  • Doppelt verkettete Liste (Doubly Linked List)
  • Kreisförmige Liste (Circular Linked List)
• Stapel (Stack): LIFO-Struktur (Last-In, First-Out). Operationen: push (hinzufügen), pop (entfernen), peek (oberes Element ansehen).

  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
      }
  }
  

• Warteschlange (Queue): FIFO-Struktur (First-In, First-Out). Operationen: enqueue (hinzufügen), dequeue (entfernen), peek (erstes Element ansehen).

  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
      }
  }
  

• Hashtabelle (Hash Table) / Wörterbuch (Dictionary) / Assoziatives Array (Associative Array): Sammlung von Schlüssel-Wert-Paaren, ermöglicht effiziente Suche, Hinzufügen und Entfernen nach Schlüssel unter Verwendung einer Hash-Funktion.

  var dictionary = [String: Any]() // Beispiel für ein Wörterbuch in Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Menge (Set): Unsortierte Sammlung von einzigartigen Elementen. Unterstützt Operationen: Hinzufügen, Entfernen, Überprüfung auf Existenz, Vereinigung, Schnittmenge, Differenz.

  var set: Set<Int> = [1, 2, 3] // Beispiel für eine Menge in Swift
  set.insert(4)
  let containsTwo = set.contains(2)
  

• Baum (Tree): Hierarchische Datenstruktur, bestehend aus Knoten, die durch Kanten verbunden sind. Hat eine Wurzel und Kindknoten.
  • Binärbaum (Binary Tree)
  • Binärer Suchbaum (Binary Search Tree - BST)
  • Ausbalancierter Binärbaum (Balanced Binary Tree) - AVL, Rot-Schwarz-Baum
  • B-Baum (B-Tree)
• Graph: Menge von Knoten (Vertices) und Kanten (Verbindungen), die Knoten verbinden. Kann gerichtet oder ungerichtet, gewichtet oder ungewichtet sein.

Das Verständnis dieser Datenstrukturen ist entscheidend für das Schreiben von effizientem und skalierbarem Code. Die Wahl der richtigen Datenstruktur hängt von den Leistungsanforderungen (Suche, Einfügen, Löschen) und der Natur der Daten ab.