Lista encadeada – Como remover um nó

LISTA ENCADEADA REMOVER UM NÓ

Nós já falamos sobre alguns métodos, adicionamos itens na lista, criamos nó com complexidade O(n) e O(1) e agora vamos remover um nó desse nosso algoritmo.

Primeiro temos que criar um método remove, vamos passar um nó para ele e, baseado nesse nó, ele vai excluir da lista.

Lembrando que em return temos que adicionar o remove:

O primeiro cenário que temos é se a lista for igual a null:

Agora, se o nó for igual ao primeiro nó da minha lista, eu simplesmente vou fazer meu head ser o node.next

Agora temos a parte complexa, afinal já cobrimos a situação em que nossa lista está vazia, remover o primeiro item e agora precisamos remover o item que escolhermos. Vamos imaginar que queremos, por exemplo, excluir o nó 2, temos que pegar o next do nó 1 e apontar para o nó 3, então temos que descobrir quem é o nó 1 para fazermos esse mapeamento:

Agora eu quero pegar o valor 2 da nossa lista e checar se eu peguei realmente esse valor:

Agora eu preciso mandar excluir esse nó 2:

Pronto, conseguimos excluir, agora precisamos pegar nosso currentNode, que é nosso nó 1 e apontar para o nó 3, já que ele seria nosso next a partir do momento em que excluímos o nó 2:

Fizemos o currentNode ser igual ao head, logo ele será o nosso nó 1, em seguida fiz uma condição: se eu tenho um próximo para andar e esse próximo não é o node, vou fazer o currentNode igual a currentNode.next, com isso vou caminhar para frente. Porém, na primeira vez que roda, ele já descobre que o Nó 1 já é o next, então precisamos fazer mais um caso de teste. Vamos adicionar uma posição 4 e em seguida remover a posição 3:

Lembrando que eu estou mostrando o que eu geralmente faço de testes, afinal o teste seria bastante viciado caso eu testasse apenas com o nó 1. Então conseguimos fazer ele caminhar nos nós e só depois então caminhar nele de verdade.

A complexidade desse código é O(n), não tem como ser diferente, pois temos que passar em todos os nós, basicamente é quase o mesmo cenário de adicionar com O(n).

Assista ao vídeo:

Curta o DevPleno no Facebookinscreva-se no canal e não se esqueça de cadastrar seu e-mail para não perder as novidades. Abraço!