Algoritmos de Programación con Python

16.5. Otras listas enlazadas

Las listas presentadas hasta aquí son las listas simplemente enlazadas, que son sencillas y útiles cuando se quiere poder insertar o eliminar nodos de una lista en tiempo constante. Existen otros tipos de listas enlazadas, cada uno con sus ventajas y desventajas.

16.5.1. Listas doblemente 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.

16.5.2. Listas circulares

Las listas circulares, que ya fueron mencionadas al comienzo de esta unidad, son aquellas en las que el último nodo contiene una referencia al primero. Pueden ser tanto simplemente como doblemente enlazadas.

Se las utiliza para modelar situaciones en las cuales los elementos no tienen un primero o un último, sino que forman una cadena infinita, que se recorre una y otra vez.

Nota Un ejemplo de uso de las listas circulares es dentro del kernel Linux. La mayoría de las listas utilizadas por este kernel son circulares, ya que la mayoría de los datos a los que se quiere acceder son datos que no tienen un orden en particular.

Por ejemplo, la lista de tareas que se están ejecutando es una lista circular. El scheduler del kernel permite que cada tarea utilice el procesador durante una porción de tiempo y luego pasa a la siguiente; y al llegar a la última vuelve a la primera, ya que la ejecución de tareas no se termina.


Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.