Actividad #2 - Listas Doblemente Ligadas
1. Definir que son listas simplemente ligadas (enlazadas) y para que se utilizan
2. Definir que son listas doblemente ligadas (enlazadas) y para que se utilizan
3. Diferencias y similitudes entre las Listas Simplemente Ligadas (enlazadas)
y Listas Doblemente Ligadas (enlazadas).
SOLUCIÓN
1. Definir que son listas simplemente ligadas y para que se utilizan
En esta sección se presentará la representación de secuencias por medio de listas ligadas. Podemos pensar en una lista ligada como si fuera una cadena, donde cada eslabón almacena un elemento y también tiene una referencia al siguiente eslabón. Una lista ligada está compuesta de nodos que almacenan algún elemento de interés, que podrían ser números enteros, caracteres, estructuras u objetos. Para efectos prácticos en este capítulo, utilizaremos listas ligadas compuestas de nodos que almacenan números enteros.
Las listas ligadas pueden clasificarse en listas ligadas simples y listas doblemente ligadas, las cuales estudiaremos más adelante. Otra variante de las listas ligadas son las listas circulares. Una posible definición de lista ligada es la siguiente:
Lista ligada: Secuencia finita y ordenada de datos conocidos como elementos o nodos, ordenada en el sentido de que cada elemento tiene una posición (índice) en la lista. Notación: <a₀, a₁, · · ·, aₙ₋₁> para los n elementos de la lista A.
Las siguientes definiciones nos ayudarán a tener una representación clara de listas ligadas:
- Lista vacía: Cuando no tiene elementos.
- Longitud o length: Se refiere al número de elementos en la lista.
- Head: Se refiere al primer elemento de la lista.
- Tail: Se refiere al último elemento de la lista.
Puede o no haber relación entre el valor de un elemento y su posición en la lista (listas ordenadas o no ordenadas). Para indicar la posición actual en la que nos encontramos dentro de la lista, podemos utilizar el operador | (indicador de posición). Por ejemplo:
Sea la lista: <20, 23|12, 15>
La posición en la cual estamos trabajando es entre el par de nodos 2 y 3, que almacenan los valores 23 y 12 respectivamente. No hay que confundir los nodos con los elementos (valores) que almacenan. Los accesos a los datos de la lista se realizan con base en la posición de |. El símbolo | divide a la lista en una partición derecha y una izquierda. La longitud de la partición izquierda crece conforme el indicador se mueve hacia la derecha.
Aporte Personal
Una lista enlazada es la estructura de datos fundamentales y puede ser usada para implementarse en otras estructuras de datos. Son secuencias de nodos, los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. Las listas tienen varios beneficios, pero el beneficio principal de las listas enlazadas puede ser diferente al orden de almacenamiento en la memoria o el disco, esto le permite que el orden de recorrido sea diferente al de almacenamiento.
Listas simplemente enlazadas (Linked List). (n.d.). https://analisisyprogramacionoop.blogspot.com/2017/07/lista-simplemente-enlazada-C-sharp.html
Resumen del video:
Las listas enlazadas son estructuras de datos lineales que, a diferencia de los arreglos, no almacenan elementos en ubicaciones de memoria contiguas. Cada nodo de la lista contiene un valor y un apuntador al siguiente nodo, lo que permite una gestión dinámica del tamaño y facilita operaciones como inserciones y eliminaciones. Sin embargo, no tienen índices, lo que complica el acceso aleatorio a elementos y las hace más costosas en términos de memoria y complejidad en ciertas operaciones. Las listas enlazadas pueden ser simples, dobles o circulares, cada una con sus propias ventajas y desventajas según el contexto de uso.
2. Definir que son listas doblemente ligadas y para que se utilizan
Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples.
La asignación de memoria es hecha al momento de la ejecución.
En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente).
El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:
- comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.
- comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.
Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al último elemento y/o del último al primer elemento.
Listas doblemente enlazadas. (n.d.). https://cidecame.uaeh.edu.mx/lcc/mapa/PROYECTO/libro9/listas_doblemente_enlazadas.html
Aporte Personal
Las listas doblemente enlazadas permiten un recorrido bidireccional, lo que facilita operaciones como inserción y eliminación en cualquier posición de la lista. Aunque ofrecen mayor flexibilidad en comparación con las listas enlazadas simples, su implementación requiere más memoria y una gestión cuidadosa de los punteros para evitar errores. Esta estructura es ideal para situaciones donde se necesita un acceso eficiente desde ambos extremos de la lista.
LISTAS DOBLEMENTE-ENLAZADAS. (n.d.). https://ccia.ugr.es/~jfv/ed1/tedi/cdrom/docs/ldoble.html
Resumen del video:
En este video se explica el funcionamiento de las listas doblemente enlazadas, destacando sus diferencias con las listas simplemente enlazadas. Se muestra cómo cada nodo en la lista doblemente enlazada tiene referencias tanto al nodo anterior como al siguiente, lo que permite navegar en ambas direcciones. Se ilustra un ejemplo práctico donde el usuario ingresa un dato, y el programa cuenta cuántos nodos hay a la izquierda y a la derecha del nodo con ese dato.
3. Diferencias y similitudes entre las Listas Simplemente Ligadas y Listas Doblemente Ligadas.
Admin. (2023, March 31). Difference between Singly Linked List and Doubly Linked List. BYJUS. https://byjus.com/gate/difference-between-singly-linked-list-doubly-linked-list/
Trabajo en clase sobre las listas doblemente ligadas 20/08/2024