Arrays e listas encadeadas
Em um array os itens ficam lado a lado na memória; em uma lista encadeada cada nó aponta para o próximo e pode estar em qualquer lugar. Cada estrutura é boa em uma coisa: experimente ler, inserir e remover e compare os passos.
Explicação do algoritmo: escolha um nível para ler.
{ }Ver o código
// Array: inserir na posição i desloca todos os itens seguintes
function inserirNoArray(array, i, valor) {
for (let j = array.length; j > i; j--) {
array[j] = array[j - 1]; // um passo por item deslocado
}
array[i] = valor;
}
// Lista encadeada: cada nó aponta para o próximo
function inserirNaLista(cabeca, i, valor) {
const novo = { valor, proximo: null };
if (i === 0) { // início: nada a percorrer
novo.proximo = cabeca;
return novo;
}
let anterior = cabeca;
for (let k = 0; k < i - 1; k++) {
anterior = anterior.proximo; // um passo por nó percorrido
}
novo.proximo = anterior.proximo; // só dois ponteiros mudam
anterior.proximo = novo;
return cabeca;
}Percorrido ou deslocadoItem lido, inserido ou ponto de alteração
Array
10
020
130
240
350
4Lista encadeada
10
→20
→30
→40
→50
→| Operação | Array | Lista encadeada |
|---|---|---|
| Ler | O(1) | O(n) |
| Inserir | O(n) | O(1)* |
| Remover | O(n) | O(1)* |
* Na lista, inserir e remover são O(1) quando você já está na posição (por exemplo, no início). Chegar a uma posição do meio ainda exige percorrer os nós, como mostra a contagem de passos acima.