Actividad 2

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

Trabajo en Grupo 

David Esteban Úsuga 

Juan David Rubio G

Ana Maria Villanueva

Listas Ligadas

¿Qué son las Listas Simplemente Ligadas?

Una lista enlazada es una colección lineal de elementos llamados nodos. El orden entre ellos se establece mediante punteros; direcciones o referencias a otros nodos 

Un nodo está constituido por dos partes: 

▪ Un campo INFORMACIÓN: Que será del tipo de los datos que se quiera almacenar en la lista. 

▪ Un campo LIGA de tipo puntero, que se utiliza para establecer la liga o el enlace con otro nodo de la lista. 

• Un programa accede a una lista enlazada mediante un apuntador al primer nodo en la lista.
•   Y se accede a cada nodo subsiguiente a través del miembro apuntador de enlace almacenado en el nodo anterior. 
•  El apuntador de enlace en el último nodo de una lista se establece en el valor nulo (0) para marcar el final de la lista.  

Los datos se almacenan en forma dinámica en una lista enlazada; se crea cada nodo según sea necesario. Un nodo puede contener datos de cualquier tipo, incluyendo objetos de otras clases. Son estructuras de datos lineales. 

Ventajas de las Listas Ligadas

Una lista enlazada es apropiada cuando el número de elementos de datos que se van a representar en un momento dado es impredecible.

 Las listas enlazadas son dinámicas, por lo que la longitud de una lista puede incrementarse o reducirse, según sea necesario. 

Las listas enlazadas se llenan sólo cuando el sistema no tiene suficiente memoria para satisfacer las peticiones de asignación dinámica de almacenamiento. 

Listas Simplemente Ligadas

Las listas simplemente ligadas son estructuras donde se maneja la información de forma dinámica, donde el espacio donde se la guarda la información es un nodo, donde este se subdivide en dos espacios un espacio para guardar la información y otro para guardar la dirección de memoria al siguiente nodo, con estas listas se pueden realizar las operaciones de insertar, ordenar, buscar, borrar y todo esto bajo el concepto de memoria dinámica. 

Listas Doblemente Ligadas

Las listas doblemente ligadas son estructuras que permiten manejar la información de forma dinámica, donde el espacio donde se guarda la información es un nodo, que es una dirección de memoria dividida en tres partes, una parte para guardar la información, otra para la dirección al siguiente nodo y la otra para apuntar al nodo anterior, con estas listas se pueden realizar las operaciones de insertar, borrar, buscar, ordenar y todo bajo el concepto de memoria dinámica.   

Un nodo doble es un registro que tiene dos campos de liga: uno que llamaremos Li (Liga izquierda) y otro que llamaremos Ld (Liga derecha). Un dibujo para representar dicho nodo es: 

Tipos de Listas enlazadas circulares

Listas enlazadas simples circulares

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.

Listas enlazadas doblemente circulares

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada. 

Aplicaciones de las listas enlazadas

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

A veces, las listas enlazadas son usadas para implementar vectores asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar estas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer esta serie de datos.

Doblemente enlazadas vs. simplemente enlazadas

Las listas doblemente enlazadas requieren más espacio por nodo y sus operaciones básicas resultan más costosas pero ofrecen una mayor facilidad para manipular ya que permiten el acceso secuencial a lista en ambas direcciones. En particular, uno puede insertar o borrar un nodo en un número fijo de operaciones dando únicamente la dirección de dicho nodo (Las listas simples requieren la dirección del nodo anterior para insertar o suprimir correctamente). Algunos algoritmos requieren el acceso en ambas direcciones para poder adquirir las listas enlazadas. 

Las listas doblemente enlazadas son aquellas en que los nodos cuentan no sólo con una referencia al siguiente, sino también con una referencia al anterior. Esto permite que la lista pueda ser recorrida en ambas direcciones.

En una lista doblemente enlazada, es posible, por ejemplo, eliminar un nodo, teniendo únicamente ese nodo, sin necesidad de saber también cuál es el anterior.

Entre las desventajas podemos mencionar que al tener que mantener dos referencias el código se vuelve más complejo, y también que ocupa más espacio en memoria.

Referencias

ESTRUCTURAS DE DATOS .Listas ligadas : 

https://www.uv.mx/personal/ermeneses/files/2021/08/Clase5-ListasEnlazadasFinal.pdf

Algoritmos_II_Uniremington. Listas Simple y Doblemente ligadas : https://imagenes.uniremington.edu.co/moodle/M%C3%B3dulos%20de%20aprendizaje/Algoritmos%20II/Algoritmos_II_modulo_listo_ok_2016.pdf

Listas Enlazadas : 

https://es.wikipedia.org/wiki/Lista_enlazada#Listas_simples_enlazadas