Ambos armazenam sequências, mas têm perfis de custo opostos. Um array é memória contígua com indexação O(1); uma lista vinculada é nós espalhados unidos por ponteiros, com O(1) inserção/remoção nas extremidades, mas sem indexação.
Ambos armazenam sequências, mas têm perfis de custo opostos. Um array é memória contígua com indexação O(1); uma lista vinculada é nós espalhados unidos por ponteiros, com O(1) inserção/remoção nas extremidades, mas sem indexação.
| Operação | Array (dinâmico) | Lista vinculada |
|---|
| Acesso por índice | O(1) | O(n) |
| Busca | O(n) | O(n) |
| Inserção/remoção no início | O(n) | O(1) |
| Inserção/remoção no final | O(1) amortizado | O(1) com tail ptr |
| Inserção/remoção no meio | O(n) | O(n) busca + O(1) splice |
| Overhead de memória | baixo | alto (ponteiro por nó) |
| Localidade de cache | excelente | ruim |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Na prática, arrays vencem na maioria das vezes porque a localidade de cache supera as diferenças Big-O para tamanhos típicos.
Conhecer ambos permite justificar sua escolha em entrevistas em vez de escolher cegamente — e explicar por que "inserção O(1)" raramente vence um array contíguo.