Eliminación del k-ésimo índice de la lista vinculada en un solo paso  ¡Bienvenido de nuevo, con otro problema por resolver! Hoy nos ocupamos de las listas enlazadas y la eliminación de sus elementos. Discutiremos un poco sobre qué son las listas enlazadas, crearemos una y veremos cómo eliminar elementos de ella.  Antes de comenzar, los descargos de responsabilidad habituales:  Estos problemas son proporcionados por el maravilloso boletín Daily Coding Problem, al que puede suscribirse  . ¡Compruébalo y trata de resolver tus desafíos también!   aquí  No soy un programador experto: ¡solo un tipo al que le gusta compartir sus tomas! Si tiene una solución mejor o más rápida para un algoritmo, envíela en los comentarios. ¡Me encantaría aprender algo más sobre esto!  Suficiente alboroto; saltemos al problema!  Este problema fue inicialmente planteado por Amazon      , elimine el k-ésimo nodo del final de la lista y devuelva el encabezado de la lista. Dada una lista enlazada y un entero k    está garantizado que es más pequeño que la longitud de la lista. k   Haz esto en una sola pasada.  Muy bien, entonces, expliquemos un poco lo que está sucediendo aquí: se nos da una lista enlazada y un elemento de índice   para eliminar de la lista. Después de eso, deberíamos devolver el encabezado de la lista enlazada. k  Finalmente, debemos hacer todo esto en una sola pasada, lo que significa que no podemos recorrer la lista más de una vez.  También tenemos la garantía de que el índice   está   en la lista, por lo que no tenemos que verificar que vaya más allá de la longitud real de la lista. k contenido  Usaremos Go para construir el algoritmo hoy, ya que su sintaxis es increíble para este tipo de trabajo y, al mismo tiempo, sigue siendo bastante simple de entender.  Comencemos desde el principio: construyendo una lista enlazada simple.  La lista enlazada  El concepto detrás de la lista enlazada es bastante simple: es una lista hecha de objetos (generalmente llamados   ), y cada nodo debe tener al menos dos propiedades: un   (algo que realmente contiene el nodo) y un   al siguiente nodo. nodos valor enlace  Por lo general, se utiliza un   como enlace para saltar de un nodo a otro. puntero  Además, el primer nodo de la lista suele llamarse   de la lista, que también es el nodo que el problema nos pide que devuelva. encabezado  He aquí un ejemplo gráfico:   El primer nodo a la izquierda es el encabezado de la lista, que contiene su valor v₀ y un puntero de memoria   que redirige la lista al siguiente nodo   El siguiente nodo   contendrá su valor y un puntero   al siguiente nodo, y así sucesivamente. P(n₁) n₁. n₁ P(n₂)  El nodo final, por supuesto, no tendrá nada a lo que apuntar, por lo que el valor de su puntero será   . nulo  ¡Veamos el código para crear uno!   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true  El código es bastante simple: creamos dos estructuras, una para el nodo interno y otra para la lista enlazada.  El nodo, como acabamos de ver, tendrá dos propiedades, a saber, la propiedad   y la propiedad   , que contiene un tipo   como puntero al siguiente nodo. Value Next *Node  La lista enlazada, una estructura para “iniciar” la lista enlazada, que solo tendrá una propiedad, el   de la lista. Head  Después de eso, simplemente inicializamos la lista en la función principal y le damos a su cabeza un nodo con un valor aleatorio de 10.  La clave para entender la lista enlazada es que ahora       , dado que es de tipo         , que contendrá el siguiente nodo. Este último nodo tendrá su propiedad   para saltar al siguiente nodo, y así sucesivamente. el nodo Head Node , tendrá inherentemente una propiedad Next Next  Todo será más claro una vez que agreguemos algunos nodos a la lista, ¡así que hagámoslo! Tenemos dos opciones: o lo hacemos manualmente, un trabajo   tedioso, o escribimos un método para que la clase de lista enlazada agregue algunos nodos más. ¡Vamos a ver! realmente  Adición de nodos: lista mutable disfrazada  Incluso si tiene poca experiencia en programación, en casi todos los lenguajes de programación, uno de los primeros conceptos que debería haber escuchado es la diferencia entre listas   e   . mutables inmutables  Como sugieren sus nombres,   . Los inmutables, en cambio, tienen un   con nuevos elementos. Pero ¿por qué es así? las listas mutables son listas a las que puede manipular y agregar elementos tamaño fijo y no se pueden agregar  Las listas inmutables son   , lo que significa que sus elementos se   : para una lista de 3 elementos, si el primer elemento se almacena en 0x00, el segundo estará en 0x01 y el último en 0x02. contiguas en la memoria almacenan en la memoria secuencialmente  Es por eso que es tan rápido iterar sobre una matriz fija, una lista inmutable o una tupla en Python porque la CPU simplemente recupera los índices de memoria uno por uno.  Por otro lado, las listas mutables son contiguas en la memoria solo cuando se inicializan por primera vez: en ese punto, si se agregan elementos, ya no serán secuenciales. Entonces, ¿cómo podemos pasar por encima de ellos?    , lo que nos traerá el elemento to agregado, y así sucesivamente.  Bueno, porque el último elemento de la primera iniciación tendrá un puntero que el elemento agregó después Así que sí, ¡las listas mutables a menudo son listas enlazadas disfrazadas!  Ahora, veamos el código:   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true  Agregamos el método   a los métodos de nuestra lista enlazada. El proceso para agregar un nodo es así: AddNode  Primero, almacenamos el valor   en una variable llamada  Head current  A continuación, recorremos la lista enlazada actualizando la variable   con el siguiente nodo cada vez, hasta que el siguiente nodo sea nulo.  current Una vez que el nodo en el que estamos actualmente tiene un puntero nulo, sabemos que estamos en el último nodo de la lista.  Por último, actualizamos este último nodo con un nuevo nodo y un nuevo valor (el puntero   de este nuevo nodo se establecerá como nulo si lo dejamos en blanco) Next  Gráficamente, este proceso es algo así:   Podemos comprobar el correcto funcionamiento de este método en la función principal, imprimiendo los valores de los nodos en la lista enlazada.  Quitar el nodo  Ahora, para la parte final y la solución a nuestro problema: eliminar un nodo con el índice correcto. En primer lugar, ¿qué significa eliminar un nodo de una lista vinculada? Si lo pensamos bien,   , ¿no? un nodo en una lista enlazada solo existe si está conectado al anterior  Por ejemplo, si le damos a n-1ᵗʰ un valor   de nulo, podemos desconectar el valor nᵗʰ de la lista.  Next  ¿Qué pasa si el elemento que queremos eliminar no es el último? ¡Bien, podemos   !  desvincular el elemento conectando el anterior con el siguiente  Entonces, para eliminar el elemento kᵗʰ, debemos encontrar el elemento k-1ᵗʰ y vincularlo al nodo k+1ᵗʰ. Tendremos que almacenar el   . nodo anterior (k-1ᵗʰ)  Obviamente,   : probar algo como   simplemente generará un error. Sin embargo, dado esto, podemos considerar el encabezado de la lista como el índice 0, y su siguiente nodo como el índice 1, y así sucesivamente, y también podemos recorrer los nodos, como lo hemos hecho antes. no podemos indexar directamente la lista linkedlist[n]  ¡Lo que podemos hacer entonces es implementar un   para realizar un seguimiento del nodo en el que estamos! contador  Vamos a codificarlo entonces.   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true  Veamos la función   que acepta un atributo   . Después de eso, inicializamos tres variables: RemoveNode index    , que contendrá el nodo anterior previousNode    , que contendrá el nodo en el que estamos durante el bucle current    , inicialmente igual a 0, que mantendrá nuestra posición en la lista counter  Omitamos el primer bloque if por el momento y concentrémonos en el bucle for. Comenzamos a hacer un bucle hasta que nuestra variable   sea estrictamente más pequeña que nuestro   : cada bucle  counter index actualizará el nodo anterior con el actual y pasará a actualizar el nodo actual y el contador.    significa que            Cuando el ciclo se rompe, estamos justo en el nodo anterior a nuestro índice deseado: solo necesitamos actualizar el puntero del nodo anterior, prev.Next , con el siguiente nodo en la lista desde este en el que estamos, que será current.Next . Finalmente, devolvemos la cabeza de la lista enlazada.  Ahora, ¿qué sucede si el índice a eliminar es la cabeza, que tiene un índice de 0? El ciclo nunca comenzaría porque comenzará con   e   , y la condición sería instantáneamente falsa. Podemos gestionar este primer caso con el bloque if en la parte superior. counter = 0 index = 0  Básicamente, si el índice es 0, podemos actualizar directamente el encabezado de la lista enlazada con el nodo al lado y devolverlo. Me gustaría señalar su atención, particularmente a la línea 31: Go, como en muchos otros idiomas,   , lo que significa que la función retiene una   del objeto pasado,   . pasa los atributos a las funciones por valor copia no el objeto real que está pasando.  Este concepto se ve claramente en este ejemplo:   package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.  Creamos una función para imprimir la dirección de memoria del valor pasado como atributo. Luego, en la función principal, creamos una variable a e imprimimos su dirección de memoria. Luego pasamos la misma variable a la función e imprimimos su dirección de memoria.  Como puede ver, si lo intenta, los resultados serán diferentes: eso se debe a que los atributos se pasan a las funciones como valor, lo que significa que se crea una copia de   solo con el propósito de pasarlo a la función. a  Volviendo a nuestra lista enlazada, debemos usar punteros para obtener la cabeza real del mismo problema anterior.     "real"          Entonces, para llegar al ll.Node , debemos recuperar su puntero, *ll.Node y moverlo más lejos con *ll.Node = *ll.Node.Next .  En la función principal, agregamos las llamadas al método, por ejemplo, llamando a   y   , y podemos verificar el resultado donde faltarán el nodo 0 y el nodo 2. ll.RemoveNode(0) ll.RemoveNode(2)  Conclusión  ¡Hemos llegado hasta el final!  Si has leído hasta este punto, te doy toda mi gratitud. Si está dispuesto a dejar uno o dos Me gusta y compartir el artículo, ¡me alegrará el día y me ayudará a continuar escribiendo estos artículos!  Nos vemos en el próximo artículo y, como siempre, gracias por leer.   Nicolás

Read My Stories

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Make resilience your competitive advantage

Problema de codificación diaria: elimine el k-ésimo índice de la lista vinculada en un solo paso

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Una breve introducción a la teoría del cerebro de Boltzmann

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

La guía completa para una migración exitosa a la nube: estrategias y mejores prácticas

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Una breve introducción a la teoría del cerebro de Boltzmann

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps