programacion listas circulares

UNIDAD II
LISTAS CIRCULARES
LISTAS DOBLEMENTE ENLAZADAS

Ing. Otalvora Emiliano

Listas circulares
Una lista circular es una variedad de lista abierta en la que el último nodo a punta al primero
en lugar de apuntar a NULL.

En estas listas el concepto de “nodo primero” es una convención, porque en realidad no
existe: todos los nodos son anteriores a otro y siguientes de otro. No hayprincipio ni fin de la lista,
aunque debemos mantener un puntero a al menos uno de los nodos para poder iniciar desde él las
operaciones sobre la lista.
Fíjese en que el puntero a un nodo de la lista lo hemos llamado “lista” en lugar de
“primero”. Esto se debe a que, como hemos dicho, en una lista circular no hay “primero” ni “último”.
Recuerde que para construir una lista con otros datos queno sean de tipo entero, bastaría con
cambiar la definición del campo “dato” en la estructura s_nodo.

Los tipos de datos que se emplean son los mismos que en el caso de las listas abiertas.
Así, para construir una lista de números enteros necesitaremos una estructura de este tipo:

struct s_nodo
{
int dato;
struct s_nodo *siguiente;
};
typedef struct s_nodo t_nodo;
t_nodo* lista;Operaciones básicas con listas circulares

De nuevo tenemos el mismo repertorio de operaciones sobre este tipo listas:
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través de la lista, siguiente y anterior.

Añadir un elemento

El único caso especial a la hora de insertar nodos en listas circulares es cuando
la lista esté vacía.

Añadirelemento en una lista circular vacía

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que
apunte a él, además el puntero que define la lista, que valdrá NULL:

El proceso es muy simple, bastará con hacer que:

1.- lista apunte a nodo.

2.- y lista->siguiente apunte a nodo

Añadir elemento en una lista circular no vacía
De nuevo partiremos de un nodo a insertar,con un puntero que apunte a él, y de una lista,
en este caso, el puntero no será nulo:

El proceso sigue siendo muy sencillo:
1.- Hacemos que nodo->siguiente apunte a lista->siguiente.
2.- Después que lista->siguiente apunte a nodo.

Añadir elemento en una lista circular, caso
general
Para generalizar los dos casos anteriores, sólo necesitamos añadir una operación:
1.- Si lista está vacíahacemos que lista apunte a nodo.
2.- Si lista no está vacía, hacemos que nodo->siguiente apunte a lista>siguiente.
3.-Después que lista->siguiente apunte a nodo.

Buscar o localizar un elemento de una lista circular
A la hora de buscar elementos en una lista circular sólo hay que tener una precaución,
es necesario almacenar el puntero del nodo en que se empezó la búsqueda, para poderdetectar el
caso en que no exista el valor que se busca. Por lo demás, la búsqueda es igual que en el caso de
las listas abiertas, salvo que podemos empezar en cualquier punto de la lista.

Eliminar un elemento de una lista circular

Para ésta operación podemos encontrar tres casos diferentes:
1.- Eliminar un nodo cualquiera, que no sea el apuntado por lista.
2.- Eliminar el nodo apuntado porlista, y que no sea el único nodo.
3.- Eliminar el único nodo de la lista.
En el primer caso necesitamos localizar el nodo anterior al que queremos borrar. Como el
principio de la lista puede ser cualquier nodo, haremos que sea precisamente lista quien apunte al
nodo anterior al que queremos eliminar.
Esto elimina la excepción del segundo caso, ya que lista nunca será el nodo a eliminar,salvo que sea el único nodo de la lista.
Una vez localizado el nodo anterior y apuntado por lista, hacemos que lista->siguiente
apunte a nodo->siguiente. Y a continuación borramos nodo.
En el caso de que sólo exista un nodo, será imposible localizar el nodo anterior, así que
simplemente eliminaremos el nodo, y haremos que lista valga NULL.

Eliminar un nodo en una lista circular con más de un...