Quais são as estruturas de dados existentes?

Existem as seguintes estruturas de dados principais:

Primitivas:

• Números inteiros (Integer)
• Números de ponto flutuante (Floating-point numbers)
• Valores booleanos (Boolean)
• Caracteres (Character)

Abstratas:

• Array: Coleção ordenada de elementos do mesmo tipo, acesso por índice com tempo constante.
• Lista ligada (Linked List): Coleção de nós, cada um contendo dados e uma referência ao próximo nó. Inserções/exclusões eficientes no início/fim, acesso por índice - $O(n)$.
  • Lista ligada simples (Singly Linked List)
  • Lista duplamente ligada (Doubly Linked List)
  • Lista circular (Circular Linked List)
• Pilha (Stack): Estrutura LIFO (Last-In, First-Out). Operações: push (adicionar), pop (remover), peek (ver o elemento superior).

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

• Fila (Queue): Estrutura FIFO (First-In, First-Out). Operações: enqueue (adicionar), dequeue (remover), peek (ver o primeiro 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
      }
  }
  

• Tabela hash (Hash Table) / Dicionário (Dictionary) / Array associativo (Associative Array): Coleção de pares "chave-valor", permitindo busca, inserção e remoção eficientes por chave usando função hash.

  var dictionary = [String: Any]() // Exemplo de dicionário em Swift
  dictionary["key1"] = "value1"
  let value = dictionary["key1"]
  

• Conjunto (Set): Coleção não ordenada de elementos únicos. Suporta operações: adição, remoção, verificação de existência, união, interseção, diferença.

  var set: Set<Int> = [1, 2, 3] // Exemplo de conjunto em Swift
  set.insert(4)
  let containsTwo = set.contains(2)
  

• Árvore (Tree): Estrutura hierárquica de dados, composta por nós ligados por arestas. Possui nó raiz e nós filhos.
  • Árvore binária (Binary Tree)
  • Árvore binária de pesquisa (Binary Search Tree - BST)
  • Árvore binária balanceada (Balanced Binary Tree) - AVL, árvore vermelho-preto.
  • Árvore B (B-Tree)
• Grafo (Graph): Conjunto de vértices (nós) e arestas (ligações), conectando vértices. Pode ser dirigido ou não, ponderado ou não.

Compreender essas estruturas de dados é fundamental para escrever código eficiente e escalável. A escolha da estrutura correta depende dos requisitos de desempenho (busca, inserção, remoção) e da natureza dos dados.