Capítulo 05: Estruturas de Dados Lineares: Vetores, Listas, Pilhas e Filas

Módulo 01: Fundamentos da Computação • Ciência da Computação Formal

🗺️ 1. Mapa Comparativo das Estruturas Lineares

flowchart LR
    A["Estruturas Lineares"] --> VEC["Vetor / Array Contíguo
(Acesso O(1), Inserção O(n), Cache Friendly)"]
    A --> LIST["Lista Encadeada
(Inserção O(1), Acesso O(n), Ponteiros)"]
    A --> STACK["Pilha (LIFO)
(Push/Pop O(1), Call Stack)"]
    A --> QUEUE["Fila (FIFO)
(Enqueue/Dequeue O(1), Buffers)"]

    style VEC fill:#e1f5fe,stroke:#03a9f4,stroke-width:2px
    style LIST fill:#ede7f6,stroke:#7e57c2,stroke-width:2px
    style STACK fill:#fff3e0,stroke:#ff9800,stroke-width:2px
    style QUEUE fill:#e8f5e9,stroke:#4caf50,stroke-width:2px

🏛️ 2. Fundamentação Teórica e Análise de Complexidade

As estruturas de dados lineares organizam elementos sequencialmente em memória. A escolha da estrutura ideal depende da proporção entre leituras aleatórias e inserções/remoções dinâmicas.

Estrutura de Dados Acesso por Índice Busca de Elemento Inserção no Início Inserção no Fim Remoção no Início Localidade de Cache
Vetor Estático (Array) $O(1)$ $O(n)$ $O(n)$ $O(1)$ $O(n)$ Excelente (Contíguo)
Vetor Dinâmico (List/Vector) $O(1)$ $O(n)$ $O(n)$ $O(1)$ Amortizado $O(n)$ Excelente
Lista Simplesmente Encadeada $O(n)$ $O(n)$ $O(1)$ $O(1)^*$ $O(1)$ Baixa (Nós espalhados)
Lista Duplamente Encadeada $O(n)$ $O(n)$ $O(1)$ $O(1)$ $O(1)$ Baixa
Pilha (LIFO - Stack) $O(n)$ $O(n)$ $O(1)$ — $O(1)$ Alta se baseada em array
Fila (FIFO - Queue) $O(n)$ $O(n)$ — $O(1)$ $O(1)$ Alta se circular em array

2.1 Análise de Memória: Alocação Contígua vs Ponteiros Dispersos

  1. Vetores e Arrays Contíguos:
    • Ocupam um bloco ininterrupto na memória RAM.
    • O acesso a A[i] é calculado aritmeticamente em tempo constante por hardware: \(\text{Endereço}(A[i]) = \text{EndereçoBase} + (i \times \text{TamanhoElemento})\)
    • Permitem aproveitamento máximo das linhas de cache L1/L2 do processador (Spatial Locality).
  2. Listas Encadeadas:
    • Cada nó exige memória extra para armazenar 1 ou 2 ponteiros de 64 bits (8 a 16 bytes adicionais por valor).
    • O percurso provoca constantes falhas de cache (Cache Misses), pois os nós estão espalhados pela Heap.
  3. Crescimento Geométrico de Vetores Dinâmicos:
    • Quando a capacidade de um vetor dinâmico (std::vector em C++, List<T> em C#, list em Python) esgota, ele aloca um novo bloco com o dobro do tamanho ($2 \times$ ou $1.5 \times$) e copia os elementos.
    • Isso garante um custo Amortizado $O(1)$ por inserção, pois o custo pesado da cópia $O(n)$ ocorre com frequência exponencialmente decrescente.

💻 3. Implementação de Lista Duplamente Encadeada com Sentinela em Python

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        # Uso de nós sentinela para eliminar checagens de ponteiro nulo (Clean Code)
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def append(self, val):
        """Insere no final em O(1) tempo."""
        new_node = Node(val)
        penultimo = self.tail.prev

        penultimo.next = new_node
        new_node.prev = penultimo
        new_node.next = self.tail
        self.tail.prev = new_node
        self.size += 1

    def prepend(self, val):
        """Insere no início em O(1) tempo."""
        new_node = Node(val)
        primeiro = self.head.next

        self.head.next = new_node
        new_node.prev = self.head
        new_node.next = primeiro
        primeiro.prev = new_node
        self.size += 1

    def to_list(self):
        result = []
        curr = self.head.next
        while curr != self.tail:
            result.append(curr.val)
            curr = curr.next
        return result

if __name__ == "__main__":
    lista = DoublyLinkedList()
    lista.append(10)
    lista.append(20)
    lista.prepend(5)
    print(f"Lista Duplamente Encadeada: {lista.to_list()} (Tamanho: {lista.size})")
    assert lista.to_list() == [5, 10, 20], "Falha estrutural na lista!"