Quali sono le strutture dati esistenti?

Esistono le seguenti strutture dati principali:

Primitive:

• Numeri interi (Integer)
• Numeri a virgola mobile (Floating-point numbers)
• Valori booleani (Boolean)
• Caratteri (Character)

Astratte:

• Array: Collezione ordinata di elementi dello stesso tipo, accesso tramite indice con tempo costante.
• Lista collegata (Linked List): Collezione di nodi, ognuno contenente dati e un riferimento al nodo successivo. Inserimenti/eliminazioni efficienti all'inizio/fine, accesso tramite indice - $O(n)$.
  • Lista semplicemente collegata (Singly Linked List)
  • Lista doppiamente collegata (Doubly Linked List)
  • Lista circolare (Circular Linked List)
• Stack: Struttura LIFO (Last-In, First-Out). Operazioni: push (aggiunta), pop (rimozione), peek (visualizza l'elemento superiore).

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

• Coda (Queue): Struttura FIFO (First-In, First-Out). Operazioni: enqueue (aggiunta), dequeue (rimozione), peek (visualizza il primo elemento).

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

• Tabella hash (Hash Table) / Dizionario (Dictionary) / Array associativo (Associative Array): Collezione di coppie "chiave-valore", che consente ricerche, inserimenti e rimozioni efficienti tramite chiave usando una funzione hash.

  var dictionary = [String: Any]() // Esempio di dizionario in Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Insieme (Set): Collezione non ordinata di elementi unici. Supporta operazioni: aggiunta, rimozione, verifica presenza, unione, intersezione, differenza.

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

• Albero (Tree): Struttura gerarchica di dati, composta da nodi collegati da rami. Ha un nodo radice e nodi figli.
  • Albero binario (Binary Tree)
  • Albero binario di ricerca (Binary Search Tree - BST)
  • Albero binario bilanciato (Balanced Binary Tree) - AVL, albero rosso-nero
  • Albero B (B-Tree)
• Grafo (Graph): Insieme di vertici (nodi) e archi (connessioni) che collegano i vertici. Può essere diretto o indiretto, pesato o non pesato.

Comprendere queste strutture dati è fondamentale per scrivere codice efficiente e scalabile. La scelta della struttura giusta dipende dai requisiti di prestazioni (ricerca, inserimento, eliminazione) e dalla natura dei dati.