Listas Enlazadas

INTRODUCCIÓN

El principal beneficio de las listas enlazadas con respecto a los arreglos convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de lalista en tiempo constante, pero no permite un acceso aleatorio.














LISTA ENLAZADA
Una lista enlazada es una colección lineal de elementos donde el orden de los mismos se establece mediante punteros. La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puedeser fácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista.

Características
• Los elementos se distribuyen de forma dispersa por la memoria:
Los bloques de información no ocupan posiciones consecutivas en la memoria. El orden de la lista la establecen los enlaces entre bloques de información.
• Acceso a los elementos aleatorio:
Puedeextraerse información de cualquier elemento o insertar un bloque en cualquier posición.
• Acceso a los elementos no destructivo:
Al contrario que en colas y pilas, la extracción de un bloque no implica su eliminación.
• El tamaño de la lista puede modificarse de forma dinámica:
Al contrario que en colas y pilas, no hay un número máximo de elementos de la lista (salvo limitaciones de lacapacidad de almacenamiento de la máquina).

Ventajas
• Inserción y extracción de nodos con coste independiente del tamaño de la lista
• Concatenación y partición listas con coste independiente del tamaño de las listas
• No hay necesidad de grandes cantidades de memoria contigua
• El uso de memoria se adapta dinámicamente al número de datos almacenados en la lista en cada momento

Desventajas• Acceso a posiciones intermedias con coste dependiente del tamaño de la lista
• Necesidad de memoria adicional para almacenar los objetos Node con sus atributos

LISTAS DOBLEMENTE ENLAZADAS
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.

Características
• Recorridosecuencial en ambas direcciones
• Mayor ocupación: 2 referencias en cada nodo
• Inserción y borrado: Modificar más referencias
• Borrado más simple: Localizado el elemento a borrar se accede al anterior / siguiente


Ventajas
• Las implementaciones para la lista doble son la misma que para la lista simple con la diferencia de que la clase nodo de la clase lista doble tendrá un nodo adicional queviene a ser el nodo anterior. Otra diferencia es en la implementación del método insertar nodo porque hay que tomar en cuenta que ya no se maneja un solo enlace sino dos.
• Otra ventaja de las listas doblemente enlazadas es que podemos usar un puntero a la celda que contiene el i-ésimo elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunquelógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera. El único precio que pagamos por estas características es la presencia de un puntero adicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de listas
Desventajas
• El enlace extra incrementa el espacio requerido.
• Seduplica el costo de las inserciones y supresiones, ya que es necesario manejar el doble de punteros.
• El manejo es más complejo.

LISTA DOBLEMENTE ENLAZADAS CIRCULARES
La lista circular doble es una especie de lista enlazada “doblemente enlazada”, pero que posee una característica adicional para el desplazamiento dentro de la lista, “ésta no tiene fin” y tiene 2 apuntadores a sí misma....