Pular para o conteúdo

Percurso e busca

Aula 2 de 10 · 4 min

Percurso e busca

Passo 1 de 11

Percorrer é um ponteiro e uma regra: continue reatribuindo-o a node.next até ele cair do fim.

A ideia

O percurso (traversal) consiste em colocar um ponteiro no head e reatribuí-lo a current.next até ele passar do fim. A busca é um percurso com uma comparação dentro. Os dois são O(n), e nenhum consegue pular adiante.

Exemplo do mundo real

O audioguia de um museu numera as estações, mas cada gravação só termina com “agora siga para a próxima parada”. Você não tem mapa na mão, então ouvir a estação doze significa passar pelas onze anteriores, em ordem.

O código

Sua vez

Coloque os passos em ordem.

  1. Avance current para current.next
  2. Aponte current para o nó head
  3. Compare current.value com o alvo
  4. Pare quando current for None e informe que não encontrou

Mini quiz

1 / 3

Por que uma lista encadeada (linked list) não pode usar busca binária?