Actividad 2
Listas Doblemente Ligadas
1. Definir que son listas simplemente ligadas y para que se utilizan
2. Definir que son listas doblemente ligadas y para que se utilizan
3. Diferencias y similitudes entre las Listas Simplemente Ligadas y Listas Doblemente Ligadas
¿Que son listas simplemente ligadas? :
son estructuras de datos lineales y dinámicas compuestas por nodos, donde cada nodo contiene un dato y un enlace (puntero) al siguiente nodo, permitiendo el recorrido en una sola dirección. Se utilizan para gestionar conjuntos de datos de tamaño impredecible, facilitando inserciones y eliminaciones rápidas sin necesidad de reordenar la memoria, a diferencia de los arrays.Características Principales:
- Estructura: Compuesta por nodos (nodo = dato + puntero al siguiente).
- Dinámicas: Su tamaño puede aumentar o disminuir en tiempo de ejecución.
- Recorrido: Solo se pueden recorrer en una dirección, desde el "head" (inicio) hasta el final.
- Memoria: Los nodos no necesitan estar contiguos en la memoria física
- ¿para que se utilizan ?:
- Gestión de Memoria: Implementar estructuras de datos que requieren crecimiento dinámico, como pilas (stacks) y colas (queues).
- Listas de Tareas: Aplicaciones donde se añaden y procesan tareas continuamente.
- Representación de Datos: Crear estructuras más complejas como listas de adyacencia para grafos.
- Eficiencia en Inserción/Borrado: Cuando la aplicación requiere insertar o eliminar elementos frecuentemente, especialmente al inicio o en el medio, lo que en un array sería muy costoso.
¿Que son listas doblemente ligadas? :
son estructuras de datos lineales donde cada nodo contiene tres campos: datos y dos punteros/referencias, uno al nodo anterior y otro al siguiente. Esto permite navegar la lista en ambas direcciones (hacia adelante y hacia atrás), facilitando inserciones y eliminaciones eficientes, incluso en los extremos
Características Principales
- Navegación bidireccional: Pueden recorrerse hacia adelante y atrás.
- Estructura de Nodo: Contiene un puntero anterior, los datos, y un puntero siguiente.
- Flexibilidad: Son más flexibles que las listas simples al permitir eliminar nodos o insertar elementos en cualquier posición de forma más eficiente.
- Finales: El puntero anterior del primer nodo y el siguiente del último apuntan a null (o actúan de forma circular)
- ¿para que se utilizan ?:
- Historial de navegadores: Para implementar los botones de "atrás" y "adelante".
- Reproductores multimedia: Listas de reproducción de música que permiten ir a la canción anterior o siguiente.
- Funcionalidades "Deshacer/Rehacer" (Undo/Redo): En editores de texto.
- Estructuras de datos complejas: Implementación de colas doblemente terminadas (Deqeue), montículos o caché LRU (Least Recently Used).
- Aplicaciones de gestión: Donde es necesario insertar/eliminar nodos rápidamente sin reorganizar toda la lista.
Se utilizan cuando se requiere navegación eficiente en ambas direcciones o manipulación constante de elementos:
Diferencias y similitudes entre las Listas Simplemente Ligadas y Listas Doblemente Ligadas:
Las listas simplemente y doblemente ligadas son estructuras de datos dinámicas que organizadas por nodos. La principal diferencia es que las simplemente ligadas usan un puntero al nodo siguiente (unidireccionales), ahorrando espacio, mientras que las doblemente ligadas usan dos punteros (anterior y siguiente), permitiendo recorrido bidireccional y eliminaciones más eficientes
Diferencias Clave:
- Punteros: Las simples tienen un puntero (siguiente), las dobles tienen dos (siguiente y anterior).
- Dirección de Recorrido: Las simples solo avanzan; las dobles avanzan y retroceden.
- Memoria: Las dobles consumen más memoria por nodo al almacenar un puntero extra.
- Eliminación: Las dobles permiten eliminar un nodo conocido en sin buscar al anterior, algo que las simples no pueden. Reddit +3
Similitudes:
- Estructura: Ambas son estructuras lineales de datos.
- Nodos: Ambas utilizan nodos compuestos por datos y punteros.
- Dinámicas: Ambas crecen o reducen su tamaño en tiempo de ejecución, no requieren memoria contigua.
- Acceso: Ambas tienen acceso secuencial, no aleatorio ().
¿Cuándo usar cuál?
- Simplemente ligadas: Cuando el espacio es crítico y solo se requiere recorrido hacia adelante.
- Doblemente ligadas: Cuando se necesita eliminar nodos frecuentemente o navegar hacia atrás
Javier Ospina Moreno. (2021, 3 septiembre). Clase Sincrónica Estructura de Datos 2021 [Vídeo]. YouTube. https://www.youtube.com/watch?v=XtCFz4YCQfI