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  . Confira e tente resolver seus desafios também!   aqui  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      , remova o k-ésimo nó do final da lista e retorne o início da lista. Dada uma lista encadeada e um inteiro k    tem a garantia de ser menor que o comprimento da lista. k   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   para remover da lista. Depois disso, devemos retornar o cabeçalho da lista encadeada. k  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   está   na lista, portanto não precisamos verificar se ele ultrapassa o tamanho real da lista. k contido  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   ), e cada nó deve ter pelo menos duas propriedades: um   (algo realmente contido pelo nó) e um   para o próximo nó. de nós valor link  Normalmente, um   é usado como um link para pular de um nó para outro. ponteiro  Além disso, o primeiro nó da lista é geralmente chamado de   da lista, que também é o nó que devemos retornar pelo problema. cabeça  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   que redireciona a lista para o próximo nó   O próximo nó   conterá seu valor e um ponteiro   para o próximo nó e assim por diante. P(n₁) n₁. n₁ P(n₂)  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!   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true  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   e a propriedade   , que contém um tipo   como um ponteiro para o próximo nó. Value Next *Node  A lista encadeada, uma estrutura para “inicializar” a lista encadeada, que terá apenas uma propriedade, o   da lista. Head  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   nó             , que conterá o próximo nó. Este último nó então terá sua propriedade   para pular para o próximo nó, e assim sucessivamente. o Head , já que é do tipo Node , terá inerentemente uma propriedade Next Next  Tudo ficará mais claro assim que adicionarmos alguns nós à lista, então vamos lá! Temos duas opções: ou fazemos manualmente, um trabalho   tedioso, ou escrevemos um método para a classe de lista encadeada para adicionar mais alguns nós. Vamos conferir! realmente  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   e   . mutáveis imutáveis  Como seus nomes sugerem,   . Os imutáveis, em vez disso, têm um   a novos elementos. Mas por que é assim? listas mutáveis são listas que você pode manipular e adicionar elementos a tamanho fixo e não podem ser acrescentados  As listas imutáveis são   , o que significa que seus elementos são   : para uma lista de 3 elementos, se o primeiro elemento for armazenado em 0x00, o segundo estará em 0x01 e o último em 0x02. contíguas na memória armazenados na memória sequencialmente  É 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?    , que nos trará o elemento to anexado e assim por diante.  Bem, porque o último elemento da primeira iniciação terá um ponteiro que o elemento adicionado depois dele Então, sim, as listas mutáveis são muitas vezes listas encadeadas disfarçadas!  Agora vamos ver o código:   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true  Adicionamos o método   aos métodos de nossa lista encadeada. O processo para adicionar um nó é assim: AddNode  Primeiro, armazenamos o valor   em uma variável chamada  Head current  Em seguida, percorremos a lista encadeada atualizando a variável   com o próximo nó todas as vezes, até que o próximo nó seja nulo.  current 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   deste novo nó será definido como nulo se o deixarmos em branco) Next  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,   , certo? um nó em uma lista encadeada só existe se estiver conectado ao anterior  Por exemplo, se dermos a n-1ᵗʰ um valor   nulo, podemos desconectar o valor nᵗʰ da lista.  Next  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,   : tente algo como   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. não podemos indexar diretamente a lista linkedlist[n]  O que podemos fazer então é implementar um   para rastrear o nó em que estamos! contador  Vamos codificar então.   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true  Vejamos a função   que aceita um atributo   . Depois disso, inicializamos três variáveis: RemoveNode index    , que manterá o nó anterior previousNode    , que manterá o nó em que estamos durante o loop current    , inicialmente igual a 0, que manterá nossa posição na lista counter  Vamos pular o primeiro bloco if por enquanto e nos concentrar no loop for. Começamos o loop até que nossa variável   seja estritamente menor que nosso   : cada loop  counter index atualizará o nó anterior com o atual e passará a atualizar o nó atual e o contador.    significa que            Quando o loop é interrompido, 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   e   , e a condição seria instantaneamente falsa. Podemos gerenciar este primeiro caso com o bloco if no topo. counter = 0 index = 0  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,   , o que significa que a função retém uma   do objeto passado,   . passa os atributos para as funções por value cópia 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   é criada apenas com o objetivo de passá-lo para a função. a  De volta à nossa lista vinculada, devemos usar ponteiros para obter a cabeça real para o mesmo problema acima.     “real”          Portanto, para chegar ao ll.Node , 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   e   , e podemos verificar o resultado onde o nó 0 e o nó 2 estarão ausentes. ll.RemoveNode(0) ll.RemoveNode(2)  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

Read My Stories

Este áudio é produzido no idioma original da história!

Muito longo; Para ler

Make resilience your competitive advantage

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

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

As camadas invisíveis: por que as entrevistas com usuários são um ativo insubstituível

Telegram: a ponte da Crypto Island para o continente

O guia completo para uma migração bem-sucedida para a nuvem: estratégias e práticas recomendadas

Guia do arquiteto para construir arquitetura de referência para um Datalake de IA/ML

As camadas invisíveis: por que as entrevistas com usuários são um ativo insubstituível

Telegram: a ponte da Crypto Island para o continente

O guia completo para uma migração bem-sucedida para a nuvem: estratégias e práticas recomendadas

Guia do arquiteto para construir arquitetura de referência para um Datalake de IA/ML

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps