Lista doblemente enlazada en Estructuras de Datos y Algoritmos
Lista doblemente enlazada en EDA
El concepto de lista enlazada se utiliza con bastante frecuencia en el mundo real. Cuando usamos Spotify para reproducir la siguiente canción en la cola, entra en acción el concepto de una lista enlazada simple que aprendimos. Pero, ¿qué se puede hacer exactamente para reproducir la canción anterior en la cola?
En este blog, entenderemos otro concepto asociado a las estructuras de datos, que es una lista enlazada doble. También discutiremos su implementación utilizando C y aplicaciones en tiempo real.
¿Qué es una lista enlazada doble?
Una lista enlazada es un tipo de estructura de datos lineal que incluye nodos conectados de manera secuencial. El nodo contiene tres campos: los datos almacenados en esa dirección de referencia y los dos punteros que apuntan a los nodos consecuentes tanto a la izquierda como a la derecha del nodo de referencia.
El puntero del nodo izquierdo almacena la dirección de memoria del nodo anterior en la secuencia, mientras que el puntero del nodo derecho almacena la dirección de memoria del siguiente nodo. Aquí usamos la asignación de memoria dinámica en lugar de matrices para que el tamaño de la memoria se pueda asignar o desasignar en tiempo de ejecución según las operaciones realizadas.
En este ejemplo, el encabezado apunta al primer nodo. El puntero izquierdo del nodo de referencia almacena NULL, y lo mismo ocurre en el caso del puntero derecho del último nodo.
- Un enfoque de aprendizaje automático para predecir el estado de met...
- Desbloquee el poder de la IA – Un lanzamiento especial de VoA...
- Elegante versión de la prompt y configuración del modelo LLM con sp...
Para realizar operaciones en este ejemplo, podemos cambiarlo aún más según sea necesario.
Implementación de la lista enlazada doble
1. Insertar un nodo al principio
Para cumplir con la operación anterior, primero creamos un nodo y asignamos memoria utilizando la asignación de memoria dinámica. Apuntamos el encabezado al nuevo nodo y almacenamos valores NULL tanto en los nodos izquierdo como derecho.
2. Eliminar el nodo del principio
Para eliminar el nodo del principio, tenemos que almacenar el valor del nodo derecho de la dirección de referencia en el encabezado y liberar el primer nodo.
3. Insertar un nodo al final
Para agregar el nodo al final, debemos recorrer hasta el final y apuntar el último nodo al nuevo nodo de referencia y viceversa.
4. Eliminar un nodo al final
Para eliminar un nodo al final, debemos recorrer la lista y llegar al final. Usaremos un puntero que apunte al penúltimo nodo. Luego liberamos el último nodo.
Ahora que hemos comprendido las operaciones básicas, ahora veremos la implementación de una lista enlazada doble utilizando C.
Este código te dará la salida deseada de:
¿Alguna vez te has preguntado cómo se desarrollan estos juegos multijugador en los que los jugadores obtienen oportunidades en bucles repetidos? Esto significa que el último jugador está enlazado nuevamente al primer jugador para formar un bucle.
Para hacer esto posible, recurrimos a otro concepto relacionado con las listas enlazadas. Una lista enlazada circular es útil en estos casos.
Lista enlazada circular
En la lista enlazada circular simple, el último nodo de la lista contiene un puntero al primer nodo de la lista. Tanto las listas enlazadas dobles como las simples pueden usar este concepto.
La única diferencia que tiene esta lista con las otras dos es que el puntero derecho del último nodo apunta al primer nodo, y el nodo de encabezado siempre apunta al primer nodo en sí mismo.
Conclusión
En mi opinión, el concepto de lista enlazada es muy importante y útil para resolver problemas complejos. Las listas enlazadas dobles y las listas enlazadas circulares simples van de la mano al enfrentarse a diversos escenarios. Espero que hayas disfrutado leyendo este blog. Por favor, dale me gusta y comenta tus opiniones sobre el tema de hoy. ¡Feliz aprendizaje!
Revisa mis blogs anteriores sobre estructuras de datos, integración de sistemas mediante APIs:
- Pila en estructuras de datos
- Cola en estructuras de datos y algoritmos
- Lista enlazada en estructura de datos y algoritmos
- Construcción de especificaciones de API basadas en RAML utilizando la plataforma MuleSoft
- Publicación de API en Anypoint Exchange utilizando la plataforma MuleSoft
