Arrays e Listas Encadeadas

Arrays e listas encadeadas são as duas formas básicas de armazenar uma sequência ordenada de elementos: arrays os colocam em memória contígua para acesso indexado em tempo constante, enquanto listas encadeadas os conectam através de ponteiros para inserção e exclusão de baixo custo.

Definition

Um array armazena elementos em locais de memória contíguos indexados por posição, permitindo acesso aleatório em tempo constante; uma lista encadeada armazena elementos em nós separados, cada um contendo uma referência para o próximo (e possivelmente anterior) nó, permitindo inserção ou remoção em tempo constante dada uma referência de nó.

Scope

Este tópico abrange estruturas lineares baseadas em sequência e os tipos de dados abstratos construídos sobre elas — arrays estáticos e dinâmicos, listas encadeadas simples e duplas, e os ADTs de pilha e fila. Ele contrasta seus custos de acesso, inserção e exclusão, aborda o redimensionamento de arrays dinâmicos e sua análise amortizada, e explica as consequências do layout da memória, como a localidade de cache. Exclui estruturas associativas e hierárquicas cobertas em tabelas hash e árvores de busca.

Core questions

• Quando o armazenamento contíguo (array) supera o armazenamento ligado por ponteiros (lista)?
• Como um array dinâmico alcança anexação em tempo constante amortizado, apesar do redimensionamento ocasional?
• Quais são as compensações de custo de arrays versus listas encadeadas para inserção, exclusão e acesso?
• Como pilhas e filas são implementadas sobre essas estruturas?
• Como o layout da memória afeta o desempenho no mundo real através do comportamento do cache?

Key concepts

• memória contígua
• acesso indexado
• redimensionamento de array dinâmico
• listas encadeadas simples e duplas
• pilhas (LIFO)
• filas (FIFO)
• custo amortizado
• localidade de cache

Key theories

Acesso aleatório versus ligação sequencial

Arrays suportam acesso indexado O(1), mas inserção ou exclusão O(n) no meio, enquanto listas encadeadas suportam emenda O(1) dado um nó, mas acesso O(n) por posição; a escolha certa depende da combinação de operações.

Crescimento amortizado de arrays dinâmicos

Um array dinâmico que dobra sua capacidade quando cheio realiza cópias O(n) ocasionais, mas se amortiza para O(1) por anexação ao longo de qualquer sequência de operações, pelo método agregado ou potencial.

Clinical relevance

Arrays e listas são o substrato de quase todo programa: arrays dinâmicos implementam os tipos de lista/vetor padrão na maioria das linguagens, filas sustentam o escalonamento e a busca em largura, pilhas sustentam o gerenciamento de chamadas de função e a avaliação de expressões, e a troca entre array e lista é uma decisão rotineira de design prático que afeta o desempenho.

History

Arrays estão entre as primeiras estruturas de dados, presentes nas primeiras linguagens de programação, e listas encadeadas foram introduzidas para processamento simbólico e de listas (notavelmente no IPL de Newell, Shaw e Simon e posteriormente no Lisp) no final da década de 1950. O tratamento sistemático de Knuth em The Art of Computer Programming estabeleceu sua análise canônica.

Key figures

• Donald Knuth
• Robert Sedgewick

Seminal works

• knuth1997vol1
• cormen2009

Frequently asked questions

Por que usar uma lista encadeada se arrays suportam acesso aleatório rápido?

Listas encadeadas permitem inserção ou exclusão em tempo constante dada uma referência a um nó, sem deslocar outros elementos, o que arrays não conseguem fazer no meio. Elas são úteis quando a sequência muda frequentemente e o acesso aleatório posicional não é necessário.

Por que as anexações de array são consideradas de tempo constante se o redimensionamento copia tudo?

O redimensionamento ocorre raramente porque a capacidade geralmente dobra, então o trabalho total de cópia ao longo de n anexações é proporcional a n. Distribuído por todas as anexações, isso resulta em um custo constante amortizado por anexação, embora redimensionamentos individuais sejam O(n).