Bombeo mecanico

Listas Circulares

La lista circulares es una especie de listas enlazadas simples o doblemente enlazadas, pero que posee una característica adicional para el desplazamiento dentro de la lista, “esta no tiene fin”. Para que la lista sea sin fin, el puntero siguiente del último elemento apuntara hacia el primer elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso delistas enlazadas simples o doblemente enlazadas. En las listas circulares, nunca se llega a una posición en la que ya no sea posible desplazarse. Cuando se llega al último elemento, el desplazamiento volverá a comenzar desde el primer elemento.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listasenlazadas 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.


[pic]
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 soloeficientemente 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 nodotiene 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 notiene 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.
[pic]
• A pesar de que las listas circulares simplifiquen las operaciones sobre ellas, también introducen algunas complicaciones. Por ejemplo, en un proceso de búsqueda, no es tan sencillo darpor terminada la búsqueda cuando el elemento buscado no existe.
• Por ese motivo se suele resaltar un nodo en particular, que no tiene por qué ser siempre el mismo. Cualquier nodo puede cumplir ese propósito, y puede variar durante la ejecución del programa.
Otra alternativa que se usa a menudo, y que simplifica en cierto modo el uso de ilistas circulares es crear un nodo especial de hará lafunción de nodo cabecera. De este modo, la lista nunca estará vacía, y se eliminan casi todos los casos especiales

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. Enparticular, 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

Métodos de las Listas Circulares Doblemente Enlazadas

Insertar Al Inicio
Partiremos de que ya tenemos el nodo a...