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

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 aquí . ¡Compruébalo y trata de resolver tus desafíos también!

• 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

Dada una lista enlazada y un entero k , elimine el k-ésimo nodo del final de la lista y devuelva el encabezado de la lista.

k está garantizado que es más pequeño que la longitud de la lista.

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 k para eliminar de la lista. Después de eso, deberíamos devolver el encabezado de la lista enlazada.

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 k está contenido en la lista, por lo que no tenemos que verificar que vaya más allá de la longitud real de la lista.

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 nodos ), y cada nodo debe tener al menos dos propiedades: un valor (algo que realmente contiene el nodo) y un enlace al siguiente nodo.

Por lo general, se utiliza un puntero como enlace para saltar de un nodo a otro.

Además, el primer nodo de la lista suele llamarse encabezado de la lista, que también es el nodo que el problema nos pide que devuelva.

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 P(n₁) que redirige la lista al siguiente nodo n₁. El siguiente nodo n₁ contendrá su valor y un puntero P(n₂) al siguiente nodo, y así sucesivamente.

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!

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 Value y la propiedad Next , que contiene un tipo *Node como puntero al siguiente nodo.

• La lista enlazada, una estructura para “iniciar” la lista enlazada, que solo tendrá una propiedad, el Head de la lista.

  
  

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 el nodo Head , dado que es de tipo Node , tendrá inherentemente una propiedad Next , que contendrá el siguiente nodo. Este último nodo tendrá su propiedad Next para saltar al siguiente nodo, y así sucesivamente.

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 realmente tedioso, o escribimos un método para que la clase de lista enlazada agregue algunos nodos más. ¡Vamos a ver!

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 mutables e inmutables .

Como sugieren sus nombres, las listas mutables son listas a las que puede manipular y agregar elementos . Los inmutables, en cambio, tienen un tamaño fijo y no se pueden agregar con nuevos elementos. Pero ¿por qué es así?

Las listas inmutables son contiguas en la memoria , lo que significa que sus elementos se almacenan en la memoria secuencialmente : para una lista de 3 elementos, si el primer elemento se almacena en 0x00, el segundo estará en 0x01 y el último en 0x02.

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?

Bueno, porque el último elemento de la primera iniciación tendrá un puntero que el elemento agregó después , lo que nos traerá el elemento to agregado, y así sucesivamente. Así que sí, ¡las listas mutables a menudo son listas enlazadas disfrazadas!

Ahora, veamos el código:

Agregamos el método AddNode a los métodos de nuestra lista enlazada. El proceso para agregar un nodo es así:

• Primero, almacenamos el valor Head en una variable llamada current

• A continuación, recorremos la lista enlazada actualizando la variable current con el siguiente nodo cada vez, hasta que el siguiente nodo sea nulo. 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 Next de este nuevo nodo se establecerá como nulo si lo dejamos en blanco)

  
  

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, un nodo en una lista enlazada solo existe si está conectado al anterior , ¿no?

Por ejemplo, si le damos a n-1ᵗʰ un valor Next de nulo, podemos desconectar el valor nᵗʰ de la lista.

¿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, no podemos indexar directamente la lista : probar algo como linkedlist[n] 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.

¡Lo que podemos hacer entonces es implementar un contador para realizar un seguimiento del nodo en el que estamos!

Vamos a codificarlo entonces.

Veamos la función RemoveNode que acepta un atributo index . Después de eso, inicializamos tres variables:

• previousNode , que contendrá el nodo anterior

• current , que contendrá el nodo en el que estamos durante el bucle

• counter , inicialmente igual a 0, que mantendrá nuestra posición en la lista

  
  

Omitamos el primer bloque if por el momento y concentrémonos en el bucle for. Comenzamos a hacer un bucle hasta que nuestra variable counter sea estrictamente más pequeña que nuestro index : cada bucle actualizará el nodo anterior con el actual y pasará a actualizar el nodo actual y el contador.

Cuando el ciclo se rompe, significa que 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 counter = 0 e index = 0 , y la condición sería instantáneamente falsa. Podemos gestionar este primer caso con el bloque if en la parte superior.

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, pasa los atributos a las funciones por valor , lo que significa que la función retiene una copia del objeto pasado, 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 a solo con el propósito de pasarlo a la función.

Volviendo a nuestra lista enlazada, debemos usar punteros para obtener la cabeza real del mismo problema anterior. Entonces, para llegar al ll.Node "real" , 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 ll.RemoveNode(0) y ll.RemoveNode(2) , y podemos verificar el resultado donde faltarán el nodo 0 y el nodo 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