LISTAS CIRCULARES
Una lista circular es una
lista lineal en la que el último
nodo a punta al primero .
Las listas circulares evitan
excepciones en las operaciones
que se realicen sobre ellas . No
existen casos especiales , cada
nodo siempre tiene uno anterior
y uno siguiente .
Ventajas
No es preciso conocer la cantidad de elementos en
tiempo de compilación.
En las listas circulares, nunca se llega a
una posición en la que ya no sea posible
desplazarse.
Cuando se llegue al último elemento, el
desplazamiento volverá a comenzar desde el primer
elemento.
Desventajas
No permite el acceso directo a un elemento
arbitrario de la lista. Para acceder al i-ésimo
elemento, debemos recorrer la lista, comenzando por
el primer nodo, hasta llegar al elemento deseado.
Como funcionan ?
En una lista lineal:
Para insertar un elemento , el
apuntador final se mueve
hacia adelante. Frente
Final
Final Final Final Final
Frente
Al sacar un elemento ,el
apuntador principal(o el
frente) se mueve a la A B C D E
siguiente posicion 0 1 2 3 4
En una lista circular: Final
Final
Si se pueden llegar Frente Frente
Final
todas las posiciones 0 1
vacias ya que el nodo AG B
principal esta enlazado Final
con el primero 4
E
C Frente
Final
D 2
3
Operaciones sobre las listas
circulares
A. Inicialización
Esta operación debe ser hecha antes de
cualquier otra operación sobre la lista.
Inicializa el puntero inicio y el puntero fin con el
puntero NULL, y el tamaño con el valor 0.
La función:
void inicialización (Lista
*lista)
{
lista->inicio = NULL;
lista->fin = NULL;
tamaño = 0;
}
B . Inserción en una lista vacía
Modelo de la función:
int ins_lista_circ_vacia ( Lista *
lista , char * dato );
La función devuelve -1 en caso de error, si no devuelve 0.
Etapas:
• Asignación de memoria para el nuevo elemento.
• Rellenar el campo de datos del nuevo elemento.
• El puntero siguiente del nuevo elemento apuntará hacia si
mismo (es la etapa que vuelve a la lista circular )
• Los punteros inicio y fin apuntaran hacia el nuevo elemento
• El tamaño es actualizado
CODIGO :
/* insercion en una lista vacía */
int ins_lista_circ_vacia(Lista * lista, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof
(Elemento)))
== NULL)
return-1; // en caso de error
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return-1; // en caso de error
strcpy (nuevo_elemento->dato, dato);
nuevo_elemento->siguiente = nuevo_elemento;
lista->inicio = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
return 0;
}
C . Inserción en una lista NO vacía
Modelo de la función:
int ins_lista_circ ( Lista * lista , Elemento
* actual , char * dato );
La función devuelve -1 en caso de error, si no devuelve 0.
La inserción se efectuara al final de la lista.
Etapas:
Asignación de memoria para el nuevo elemento
Rellenar el campo de datos del nuevo elemento
El puntero siguiente del nuevo elemento apunta hacia la
dirección del primer elemento (conservar la lista circular)
El puntero inicio no cambia
El puntero fin apunta hacia el nuevo elemento
El tamaño se incrementa en una unidad
CODIGO :
/* inserción en una lista no vacía */
int ins_lista_circ(Lista * lista, Elemento *actual, char *dato){
Elemento *nuevo_elemento;
if ((nuevo_elemento = (Elemento *) malloc (sizeof (Elemento)))
== NULL)
return-1;
if ((nuevo_elemento->dato = (char *) malloc (50 * sizeof
(char)))
== NULL)
return -1;
strcpy (nuevo_elemento->dato, dato);
if(actual != lista->fin)
return -1;
nuevo_elemento->siguiente = actual->siguiente;
actual->siguiente = nuevo_elemento;
lista->fin = nuevo_elemento;
lista->tamaño++;
Return 0;
}
D . Eliminación al inicio de
la lista
Etapas:
• El puntero sup_elemento contendrá la dirección del 1er
elemento.
• El puntero inicio apuntara hacia el 2do elemento .
• El puntero siguiente del ultimo elemento apuntara hacia el
1er elemento (que era el 2do antes de la
eliminación )
• El tamaño de la lista disminuirá 1 elemento.
CODIGO :
/* eliminación al inicio de la lista */
int sup_lista_circ(Lista * lista)
{
if (lista->tamaño < 2)
return -1;
Elemento *sup_element;
sup_elemento = lista->inicio;
lista->inicio = lista->inicio->siguiente;
lista->fin->siguiente = lista->inicio;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño--;
return 0;
}
E . Eliminación en una lista con un solo
elemento
Etapas:
-El puntero sup_elemento contendrá la dirección del
elemento (la lista contiene un solo elemento)
-El puntero inicio apuntara hacia NULL
-El puntero fin apuntara hacia NULL
-El tamaño de la lista disminuirá un elemento .
CODIGO :
/* eliminación en una lista con un solo elemento*/
int sup_lista_circ_unica(Lista *lista){
if (lista->tamaño != 1)
return -1;
Elemento *sup_elemento;
sup_elemento = lista->inicio;
lista->inicio = NULL;
lista->fin = NULL;
free (sup_elemento->dato);
free (sup_elemento);
lista->tamaño--;
return 0;
}
Lista doblemente enlazada circular
El campo siguiente del último nodo apunte al primer
nodo de la lista y el campo anterior del primer nodo
apunte al último nodo de la lista.
