Tecnicas De Programacion C++

Tipos de Listas Enlazadas

Listas enlazadas lineales

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo

Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior

En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta técnica no se suele utilizar.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Una lista enlazada circular que contiene tres valores enteros

Listas enlazadas circulares simples

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.

Lista Enlazada Doblemente Circular

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.

Nodos Centinelas

A veces las listas enlazadas tienen un nodo centinela (también llamado falso nodo o nodo ficticio) al principio o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.

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 practica 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 arrays 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 éstas 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 ésta serie de datos.

Ventajas

Como muchas opciones en programación y desarrollo, no existe un único método correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aquí una lista con algunas de las ventajas más comunes que implican las estructuras de tipo lista. En general, teniendo una colección dinámica donde los elementos están siendo añadidos y eliminados frecuentemente e importa la localización de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.

Listas Enlazadas vs. Vectores o Matrices

Array Lista Enlazada

Indexado O(1) O(n)

Inserción / Eliminación al final O(1) O(1) or O(n)2

Inserción / Eliminación en la mitad O(n) O(1)

Persistencia

No Simples sí

Localización Buena Mala

Las listas enlazadas poseen muchas ventajas sobre los arrays. Los elementos se pueden insertar en una lista indefinidamente mientras que un array tarde o temprano se llenará ó necesitará ser redimensionado, una costosa operación que incluso puede no ser posible si la memoria se encuentra fragmentada.En algunos casos se pueden lograr ahorros de memoria almacenando la misma ‘cola’ de elementos entre dos o más listas – es decir, la lista acaba en la misma secuencia de elementos. De este modo, uno puede añadir nuevos elementos al frente de la lista manteniendo una referencia tanto al nuevo como a los viejos elementos - un ejemplo simple de una estructura de datos persistente.

Por otra parte, los arrays permiten acceso aleatorio mientras que las listas enlazadas sólo permiten acceso secuencial a los elementos. Las listas enlazadas simples, de hecho, solo pueden ser recorridas en una dirección. Esto hace que las listas sean inadecuadas para aquellos casos en los que es útil buscar un elementos por su índice rápidamente, como el heapsort. El acceso secuencial en los arrays también es más rápido que en las listas enlazadas.

Otra desventaja de las listas enlazadas es el almacenamiento extra necesario para las referencias, que a menudos las hacen poco prácticas para listas de pequeños datos como caracteres o valores booleanos.

También puede resultar lento y abusivo el asignar memoria para cada nuevo elemento. Existe una variedad de listas enlazadas que contemplan los problemas anteriores para resolver los mismos. Un buen ejemplo que muestra los pros y contras del uso de arrays sobre listas enlazadas es la implementación de un programa que resuelva el problema de Josephus. Este problema consiste en un grupo de personas dispuestas en forma de círculo. Se empieza a partir de una persona predeterminadas y se cuenta n veces, la persona n-ésima se saca del círculo y se vuelve a cerrar el grupo. Este proceso se repite hasta que queda una sola persona, que es la que gana. Este ejemplo muestra las fuerzas y debilidades de las listas enlazadas frente a los arrays, ya que viendo a la gente como nodos conectados entre sí en una lista circular se observa como es más fácil suprimir estos nodos. Sin embargo, se ve como la lista perderá utilidad cuando haya que encontrar a la siguiente persona a borrar. Por otro lado, en un array el suprimir los nodos será costoso ya que no se puede quitar un elemento sin reorganizar el resto. Pero en la búsqueda de la n-ésima persona tan sólo basta con indicar el índice n para acceder a él resultando mucho más eficiente.

Doblemente Enlazadas vs. Simples 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.

Circulares Enlazadas vs. Lineales Enlazadas

Las listas circulares son más útiles para describir estructuras circulares y tienen la ventaja de poder recorrer la lista desde cualquier punto. También permiten el acceso rápido al primer y último elemento por medio de un puntero simple.

Nodos Centinelas (headernodes)

La búsqueda común y los algoritmos de ordenación son menos complicados si se usan los llamados Nodos Centinelas

...