Problema de codificação diária: remova o k-ésimo índice da lista encadeada em uma passagem

Removendo k-ésimo índice da lista vinculada em uma passagem

Bem-vindo de volta, com mais um problema para resolver! Hoje, estamos lidando com listas encadeadas e remoção de seus elementos. Discutiremos um pouco sobre o que são listas encadeadas, criaremos uma e veremos como remover elementos dela.

Antes de começar, as isenções de responsabilidade habituais:

• Esses problemas são fornecidos pelo maravilhoso boletim Daily Coding Problem, que você pode assinar aqui . Confira e tente resolver seus desafios também!

• Não sou um programador especialista: apenas um cara que gosta de compartilhar suas fotos! Se você tiver uma solução melhor ou mais rápida para um algoritmo, envie-a nos comentários! Eu adoraria aprender um pouco mais sobre isso!

  
  

Chega de barulho; vamos pular para o problema!

Este problema foi inicialmente solicitado pela Amazon

Dada uma lista encadeada e um inteiro k , remova o k-ésimo nó do final da lista e retorne o início da lista.

k tem a garantia de ser menor que o comprimento da lista.

Faça isso em uma passagem.

Tudo bem então, vamos explicar um pouco o que está acontecendo aqui: temos uma lista encadeada e um elemento de índice k para remover da lista. Depois disso, devemos retornar o cabeçalho da lista encadeada.

Por fim, devemos fazer tudo isso em apenas uma passagem, o que significa que não podemos percorrer a lista mais de uma vez.

Também temos a garantia de que o índice k está contido na lista, portanto não precisamos verificar se ele ultrapassa o tamanho real da lista.

Usaremos Go para construir o algoritmo hoje, pois sua sintaxe é incrível para esse tipo de trabalho e, ao mesmo tempo, permanece bastante simples de entender.

Vamos começar do começo: construindo uma lista encadeada simples.

A lista vinculada

O conceito por trás da lista encadeada é bem simples: é uma lista feita de objetos (geralmente chamados de nós ), e cada nó deve ter pelo menos duas propriedades: um valor (algo realmente contido pelo nó) e um link para o próximo nó.

Normalmente, um ponteiro é usado como um link para pular de um nó para outro.

Além disso, o primeiro nó da lista é geralmente chamado de cabeça da lista, que também é o nó que devemos retornar pelo problema.

Aqui está um exemplo gráfico:

O primeiro nó à esquerda é o cabeçalho da lista, que contém seu valor v₀ e um ponteiro de memória P(n₁) que redireciona a lista para o próximo nó n₁. O próximo nó n₁ conterá seu valor e um ponteiro P(n₂) para o próximo nó e assim por diante.

O nó final, é claro, não terá nada para apontar, então o valor de seu ponteiro será null .

Vamos ver o código para criar um!

O código é bem simples: criamos duas estruturas, uma para o nó interno e outra para a lista encadeada.

• O nó, como acabamos de ver, terá duas propriedades, a saber, a propriedade Value e a propriedade Next , que contém um tipo *Node como um ponteiro para o próximo nó.

• A lista encadeada, uma estrutura para “inicializar” a lista encadeada, que terá apenas uma propriedade, o Head da lista.

  
  

Depois disso, simplesmente inicializamos a lista na função principal e damos à sua cabeça um nó com um valor aleatório de 10.

A chave por trás da compreensão da lista encadeada é que agora o nó Head , já que é do tipo Node , terá inerentemente uma propriedade Next , que conterá o próximo nó. Este último nó então terá sua propriedade Next para pular para o próximo nó, e assim sucessivamente.

Tudo ficará mais claro assim que adicionarmos alguns nós à lista, então vamos lá! Temos duas opções: ou fazemos manualmente, um trabalho realmente tedioso, ou escrevemos um método para a classe de lista encadeada para adicionar mais alguns nós. Vamos conferir!

Adicionando nós: lista mutável disfarçada

Mesmo que você tenha pouca experiência em programação, em quase todas as linguagens de programação, um dos primeiros conceitos sobre os quais você deve ter ouvido falar é a diferença entre listas mutáveis e imutáveis .

Como seus nomes sugerem, listas mutáveis são listas que você pode manipular e adicionar elementos a . Os imutáveis, em vez disso, têm um tamanho fixo e não podem ser acrescentados a novos elementos. Mas por que é assim?

As listas imutáveis são contíguas na memória , o que significa que seus elementos são armazenados na memória sequencialmente : para uma lista de 3 elementos, se o primeiro elemento for armazenado em 0x00, o segundo estará em 0x01 e o último em 0x02.

É por isso que é tão rápido iterar sobre uma matriz fixa, uma lista imutável ou uma tupla em Python porque a CPU simplesmente recupera os índices de memória um por um.

Por outro lado, as listas mutáveis são contíguas na memória apenas quando inicializadas: nesse ponto, se elementos forem adicionados, eles não serão mais sequenciais. Então, como podemos passar por cima deles?

Bem, porque o último elemento da primeira iniciação terá um ponteiro que o elemento adicionado depois dele , que nos trará o elemento to anexado e assim por diante. Então, sim, as listas mutáveis são muitas vezes listas encadeadas disfarçadas!

Agora vamos ver o código:

Adicionamos o método AddNode aos métodos de nossa lista encadeada. O processo para adicionar um nó é assim:

• Primeiro, armazenamos o valor Head em uma variável chamada current

• Em seguida, percorremos a lista encadeada atualizando a variável current com o próximo nó todas as vezes, até que o próximo nó seja nulo. Uma vez que o nó em que estamos atualmente tem um ponteiro nulo, sabemos que estamos no último nó da lista.

• Por fim, atualizamos este último nó com um novo nó e um novo valor (o ponteiro Next deste novo nó será definido como nulo se o deixarmos em branco)

  
  

Graficamente, esse processo é mais ou menos assim:

Podemos verificar o correto funcionamento deste método na função main, imprimindo os valores dos nós da lista encadeada.

Removendo o Nó

Agora, para a parte final e solução do nosso problema: remover um nó com o índice correto. Em primeiro lugar, o que significa remover um nó de uma lista encadeada? Se pensarmos bem, um nó em uma lista encadeada só existe se estiver conectado ao anterior , certo?

Por exemplo, se dermos a n-1ᵗʰ um valor Next nulo, podemos desconectar o valor nᵗʰ da lista.

E se o elemento que queremos remover não for o último? Bem, podemos desvincular o elemento conectando o anterior ao próximo dele !

Portanto, para remover o elemento kᵗʰ, devemos encontrar o elemento k-1ᵗʰ e vinculá-lo ao nó k+1ᵗʰ. Precisamos armazenar o nó anterior (k-1ᵗʰ) .

Obviamente, não podemos indexar diretamente a lista : tente algo como linkedlist[n] apenas gerará um erro. Dado isso, porém, podemos considerar a cabeça da lista como índice 0, e seu próximo nó como índice 1, e assim por diante, e também podemos percorrer os nós, como fizemos antes.

O que podemos fazer então é implementar um contador para rastrear o nó em que estamos!

Vamos codificar então.

Vejamos a função RemoveNode que aceita um atributo index . Depois disso, inicializamos três variáveis:

• previousNode , que manterá o nó anterior

• current , que manterá o nó em que estamos durante o loop

• counter , inicialmente igual a 0, que manterá nossa posição na lista

  
  

Vamos pular o primeiro bloco if por enquanto e nos concentrar no loop for. Começamos o loop até que nossa variável counter seja estritamente menor que nosso index : cada loop atualizará o nó anterior com o atual e passará a atualizar o nó atual e o contador.

Quando o loop é interrompido, significa que estamos apenas no nó anterior ao nosso índice desejado: precisamos apenas atualizar o ponteiro do nó anterior, prev.Next , com o próximo nó na lista a partir deste em que estamos, que será current.Next . Por fim, retornamos o cabeçalho da lista encadeada.

Agora, o que acontece se o índice a ser removido for a cabeça, que tem índice 0? O loop nunca iniciaria porque iniciaria com counter = 0 e index = 0 , e a condição seria instantaneamente falsa. Podemos gerenciar este primeiro caso com o bloco if no topo.

Basicamente, se o índice for 0, podemos atualizar diretamente o cabeçalho da lista encadeada com o nó próximo a ele e retorná-lo. Gostaria de chamar sua atenção, principalmente para a linha 31: Go, como em muitas outras linguagens, passa os atributos para as funções por value , o que significa que a função retém uma cópia do objeto passado, não o objeto real que você está passando .

Este conceito é visto claramente neste exemplo:

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

Criamos uma função para imprimir o endereço de memória do valor passado como atributo. Então, na função principal, criamos uma variável a e imprimimos seu endereço de memória. Então passamos a mesma variável para a função e imprimimos seu endereço de memória.

Como você pode ver, se você tentar, os resultados serão diferentes: isso porque os atributos são passados para as funções como valor, ou seja, uma cópia de a é criada apenas com o objetivo de passá-lo para a função.

De volta à nossa lista vinculada, devemos usar ponteiros para obter a cabeça real para o mesmo problema acima. Portanto, para chegar ao ll.Node “real” , devemos recuperar seu ponteiro, *ll.Node e movê-lo ainda mais com *ll.Node = *ll.Node.Next .

Na função principal, adicionamos as chamadas ao método, por exemplo, chamando ll.RemoveNode(0) e ll.RemoveNode(2) , e podemos verificar o resultado onde o nó 0 e o nó 2 estarão ausentes.

Conclusão

Chegamos ao fim!

Se você leu até aqui, toda a minha gratidão vai para você. Se você estiver disposto a deixar um ou dois likes e compartilhar o artigo, isso fará meu dia e me ajudará a continuar escrevendo esses artigos!

Até o próximo artigo e, como sempre, obrigado pela leitura.

Nicola