Arrays e Listas Encadeadas

Arrays

Um array armazena um número fixo de posições de um mesmo tipo, endereçadas por índices inteiros. Java verifica os limites em tempo de execução. Um array dinâmico, como ArrayList, mantém um array subjacente e o expande quando a capacidade se esgota.

Operação no array dinâmico	Limite típico
Ler ou substituir por índice	Θ(1)
Adicionar ao final	Θ(1) amortizado, Θ(n) no pior caso
Inserir/remover perto do início	Θ(n)
Buscar valores não ordenados	Θ(n)

O redimensionamento copia as referências existentes para um array maior. O crescimento geométrico torna linear o custo total das cópias ao longo de muitas inserções, resultando em tempo constante amortizado por inserção ao final.

Listas encadeadas

Um nó simplesmente encadeado armazena um valor e uma referência ao próximo nó. Um nó duplamente encadeado também referencia seu predecessor.

final class Node<T> {
    final T value;
    Node<T> next;

    Node(T value, Node<T> next) {
        this.value = value;
        this.next = next;
    }
}

A inserção após um nó já conhecido é Θ(1). Encontrar essa posição continua sendo Θ(n). Essa distinção evita a afirmação enganosa de que uma inserção arbitrária em lista encadeada sempre leva tempo constante.

Escolha

Prefira um array dinâmico para acesso indexado e iteração favorável ao cache. Prefira uma representação encadeada quando o algoritmo já possuir referências aos nós e realizar muitas alterações estruturais locais. Em aplicações Java, ArrayList costuma ser a sequência padrão; escolha LinkedList somente quando houver evidências de que seus compromissos são adequados à carga de trabalho.

Exercícios

1. Derive o custo amortizado de duplicar a capacidade.
2. Inverta uma lista simplesmente encadeada e declare um invariante de laço.
3. Explique por que o acesso indexado em uma lista encadeada é Θ(n).