Pular para o conteúdo
</> Entendendo Algoritmos

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
0
20
1
30
2
40
3
50
4

Lista encadeada

10
→
20
→
30
→
40
→
50
→
null
OperaçãoArrayLista encadeada
LerO(1)O(n)
InserirO(n)O(1)*
RemoverO(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.