4.3 Operaciones básicas con listas circulares

A todos los efectos, las listas circulares son como las listas abiertas en cuanto a las operaciones que se pueden realizar sobre ellas:

  • Añadir o insertar elementos.
  • Buscar o localizar elementos.
  • Borrar elementos.
  • Moverse a través de la lista, siguiente.

Cada una de éstas operaciones podrá tener varios casos especiales, por ejemplo, tendremos que tener en cuenta cuando se inserte un nodo en una lista vacía, o cuando se elimina el único nodo de una lista.

4.4 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ñadir elemento en una lista circular vacía

Lista vacía
Lista vacía
Nodo insertado
Nodo insertado

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:

Lista no vacía
Lista no vacía

El proceso sigue siendo muy sencillo:

  1. Hacemos que nodo->siguiente apunte a lista->siguiente.
  2. Después que lista->siguiente apunte a nodo.
Nodo insertado
Nodo insertado

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ía hacemos 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.

4.5 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 poder detectar 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.

4.6 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 por lista, 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 elemento

Consideraremos los dos primeros casos como uno sólo.

Lista con más de un elemento
Lista con más de un elemento
  1. El primer paso es conseguir que lista apunte al nodo anterior al que queremos eliminar. Esto se consigue haciendo que lista valga lista->siguiente mientras lista->siguiente sea distinto de nodo.
  2. Hacemos que lista->siguiente apunte a nodo->siguiente.
  3. Eliminamos el nodo.
Nodo eliminado
Nodo eliminado

Eliminar el único nodo en una lista circular

Este caso es mucho más sencillo. Si lista es el único nodo de una lista circular:

  1. Borramos el nodo apuntado por lista.
  2. Hacemos que lista valga NULL.

Otro algoritmo para borrar nodos

Existe un modo alternativo de eliminar un nodo en una lista circular con más de un nodo.

Supongamos que queremos eliminar un nodo apuntado por nodo:

Lista no vacía
Lista no vacía
  1. Copiamos el contenido del nodo->siguiente sobre el contenido de nodo.
  2. Hhacemos que nodo->siguiente apunte a nodo->siguiente->siguiente.
  3. Eliminamos nodo->siguiente.
  4. Si lista es el nodo->siguiente, hacemos lista = nodo.
Nodo eliminado
Nodo eliminado

Este método también funciona con listas circulares de un sólo elemento, salvo que el nodo a borrar es el único nodo que existe, y hay que hacer que lista apunte a NULL.

Comentarios de los usuarios (1)

Luis De La O
2012-02-29 21:00:13

Hay un error en el procedimiento para eliminar en listas circulares, precisamente en el que dice "otro algoritmo para borrar nodos"... si hacemos que nodo->siguiente apunte a nodo->siguiente->siguiente antes de borrar el nodo deseado, lo que hecemos es eliminar el nodo->siguiente->siguiente