Jakie istnieją struktury danych?

Istnieją następujące główne struktury danych:

Prymitywne:

• Liczby całkowite (Integer)
• Liczby zmiennoprzecinkowe (Floating-point numbers)
• Wartości logiczne (Boolean)
• Znaki (Character)

Abstrakcyjne:

• Tablica (Array): Posortowana kolekcja elementów tego samego typu, dostęp przez indeks w czasie stałym.
• Lista powiązana (Linked List): Kolekcja węzłów, z których każdy zawiera dane i odniesienie do następnego węzła. Efektywne dodawanie/usuwanie na początku/końcu, dostęp przez indeks - $O(n)$.
  • Lista jednokierunkowa (Singly Linked List)
  • Lista dwukierunkowa (Doubly Linked List)
  • Lista cykliczna (Circular Linked List)
• Stos (Stack): Struktura LIFO (Last-In, First-Out). Operacje: push (dodanie), pop (usunięcie), peek (podgląd górnego elementu).

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

• Kolejka (Queue): Struktura FIFO (First-In, First-Out). Operacje: enqueue (dodanie), dequeue (usunięcie), peek (podgląd pierwszego elementu).

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

• Tablica mieszająca (Hash Table) / Słownik (Dictionary) / Tablica asocjacyjna (Associative Array): Kolekcja par "klucz-wartość", umożliwiająca efektywne wyszukiwanie, dodawanie i usuwanie po kluczu za pomocą funkcji hash.

  var dictionary = [String: Any]() // Przykład słownika w Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Zbiór (Set): Nieuporządkowana kolekcja unikalnych elementów. Obsługuje operacje: dodawanie, usuwanie, sprawdzanie istnienia, sumę, przecięcie, różnicę.

  var set: Set<Int> = [1, 2, 3] // Przykład zbioru w Swift
  set.insert(4)
  let containsTwo = set.contains(2)
  

• Drzewo (Tree): Hierarchiczna struktura danych, składająca się z węzłów połączonych krawędziami. Ma korzeń i węzły potomne.
  • Drzewo binarne (Binary Tree)
  • Drzewo binarne wyszukiwania (Binary Search Tree - BST)
  • Zrównoważone drzewo binarne (Balanced Binary Tree) - AVL, drzewo czerwono-czarne
  • Drzewo B (B-Tree)
• Graf (Graph): Zbiór wierzchołków (węzłów) i krawędzi (połączeń), łączących wierzchołki. Może być skierowany lub nieskierowany, ważony lub nieważony.

Zrozumienie tych struktur danych jest kluczowe do pisania wydajnego i skalowalnego kodu. Wybór odpowiedniej struktury zależy od wymagań dotyczących wydajności operacji (wyszukiwanie, wstawianie, usuwanie) i charakterystyki danych.