Actividad 2 - Listas Doblemente Ligadas

1. Definir que son listas simplemente ligadas y para que se utilizan

Una lista simplemente ligada es una estructura de datos que consta de una serie de nodos, donde cada nodo contiene dos elementos:

• Un valor o dato.
• Un puntero(liga) o referencia al siguiente nodo en la lista.

El último nodo en la lista tiene un puntero que apunta a null o vacío, indicando el final de la lista.

Uso: Las listas simplemente ligadas se utilizan cuando se necesitan operaciones eficientes de inserción o eliminación en cualquier parte de la lista (particularmente en el inicio) sin necesidad de mover otros elementos. Son útiles en algoritmos donde las operaciones de recorrido secuencial o almacenamiento dinámico son necesarias, como en pilas y colas.

2. Definir que son listas doblemente ligadas y para que se utilizan

Una lista doblemente ligada es una estructura de datos similar a la lista simplemente ligada, pero con la diferencia de que cada nodo tiene dos punteros:

• Un puntero(liga) al siguiente nodo (igual que en las listas simplemente ligadas).
• Un puntero(liga) al nodo anterior (que apunta al nodo anterior en la lista).

Esto permite recorrer la lista en ambas direcciones, hacia adelante y hacia atrás.

Uso: Las listas doblemente ligadas se utilizan cuando se necesitan operaciones eficientes de inserción o eliminación en ambas direcciones (inicio y final), ya que permiten un acceso directo tanto al nodo anterior como al siguiente. Son útiles en aplicaciones como la implementación de la funcionalidad de retroceso/avance en navegadores web, editores de texto o estructuras de datos más complejas como el manejo de bases de datos.

3. Diferencias y similitudes entre las Listas Simplemente Ligadas y Listas Doblemente Ligadas

Similitudes:

• Ambas son estructuras de datos dinámicas, es decir, no requieren un tamaño fijo y pueden crecer o reducirse dinámicamente.
• Ambas están formadas por nodos que contienen datos y punteros.
• Ambas permiten operaciones como inserción, eliminación y recorrido de nodos, aunque con diferencias en eficiencia.

Diferencias:

• Punteros(ligas): En las listas simplemente ligadas, cada nodo tiene un solo puntero que apunta al siguiente nodo. En las listas doblemente ligadas, cada nodo tiene dos punteros: uno al siguiente nodo y otro al nodo anterior.
• Recorrido: En las listas simplemente ligadas, solo se puede recorrer la lista en una dirección (hacia adelante). En las listas doblemente ligadas, se puede recorrer en ambas direcciones (hacia adelante y hacia atrás).
• Complejidad: Las listas doblemente ligadas requieren más memoria debido a que cada nodo necesita almacenar un puntero adicional. Esto las hace un poco más costosas en términos de espacio. Además, las operaciones de inserción y eliminación son un poco más eficientes en listas doblemente ligadas, ya que no es necesario recorrer la lista para encontrar el nodo anterior (ya que el nodo tiene un puntero a su nodo anterior).