sistemas operativos

Listas circulares.
• En las listas lineales simples o dobles siempre hay
un primer nodo y un último nodo que tiene el
campo de enlace a nulo. Esto, porque se delimita
el comienzo y el término de la misma. Una lista
circular, por su naturaleza cíclica, no tiene ni
principio ni fin. No obstante, es útil y
recomendable establecer un nodo de referencia a
partir del cual se acceda a la lista yasí poder
conocer la posición inicial y acceder a sus
operaciones insertar, borrar etc.

Listas circulares.
Listas enlazadas circulares
• En una lista enlazada circular, los nodos último y
primero están unidos por un enlace (no apuntan a
NULL). Esto es posible tanto para listas enlazadas
simples como para las doblemente enlazadas. Para
recorrer un lista enlazada circular se puedecomenzar
por cualquier nodo y seguir la lista en cualquier
dirección hasta que se regrese hasta el nodo original.
• Las listas enlazadas circulares pueden ser vistas como
listas sin comienzo ni fin si no hay un punto que lo
indique.
• 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.

Listascirculares.

Listas circulares.
Listas enlazadas circulares simples
• Cada nodo tiene un enlace, análogo al de las listas
enlazadas simples, la diferencia está en 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 (recordemos que
aquí no hay inicio nifin).
• Lo usual es 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 circulares.
Lista Doblemente Enlazada Circular
• En una lista circular doblemente enlazada, cada nodo
tiene dos enlaces, análogamente a lalista doblemente
enlazada lineal, el cambio radica en 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 contiguo.
• Aunque estructuralmente una lista circular doblemente
enlazada no tiene niprincipio ni fin, un puntero de acceso
externo (centinela) puede establecer el nodo apuntado
que está en la cabeza o al nodo final, y así mantener el
orden como en una lista doblemente enlazada.

Listas circulares.
Nodos Centinelas o cabecera (header nodes)
• La búsqueda y los algoritmos de ordenación se simplifican si se usan los
llamados Nodos Centinelas o cabecera, donde cada elementoapunta a
otro elemento y nunca a nulo. El Nodo Centinela o Puntero Cabeza
contiene, como otro, un puntero siguiente que apunta al que se
considera como primer elemento de la lista . También contiene un
puntero previo que hace lo mismo con el último elemento.
• El Nodo Centinela es definido como otro nodo en una lista doblemente
enlazada. Si los punteros anterior y siguiente apuntan al NodoCentinela la lista se considera vacía. En otro caso, si a la lista se le
añaden elementos ambos puntero apuntarán a otros nodos. Estos
Nodos Centinelas simplifican muchos las operaciones pero hay que
asegurarse de que los punteros anterior y siguiente existen en cada
momento.
• Como ventaja eliminan la necesidad de guardar la referencia al puntero
del principio de la lista y la posibilidad deasignaciones accidentales. Por
el contrario, usan demasiado almacenamiento extra y resultan
complicados en algunas operaciones.

Listas circulares.
Inserción de un elemento en una lista circular
El algoritmo empleado para añadir o insertar un elemento en una lista
circular varia dependiendo de la posición en que se desea insertar el

elemento que inserta el nodo en la lista circular....