Lista Circular

Lista Circular

Una lista circular es una lista donde el último elemento apunta hacia la primera posición. Existen varias variantes de de este tipo de lista:

La Circular Simplemente Enlazada está compuesta por elementos llamados nodos, donde cada nodo  almacena  un dato y  la referencia a el  elemento siguientes. El último nodo tiene referencia al primer nodo. Teóricamente en lo único que se diferencia a la lista Simplemente enlazada es en esta última posición ya que no contienen en esta posición referencia nula.  

 

La Circular Doblemente  Enlazada está compuesta por elementos llamados nodos, donde cada nodo  almacena  un dato,  la referencia al elemento siguiente y al elemento anterior. El último nodo tiene referencia al primer nodo y el primer nodo tiene de referencia como nodo anterior al último nodo. Teóricamente este tipo de lista  se diferencia a la lista Doblemente Enlazada en la  última posición ya que no contienen referencia nula al  siguiente nodo y en la primera posición que no contiene referencia anterior nula.  

Operaciones Básicas de la Lista.

Al  igual que los otros tipos de listas, la lista circular implementa los métodos básicos: adicionar, insertar, eliminar, obtener, etc.  

Lista Circular Simplemente Enlazada.

A continuación, se muestra la declaración de la clase ListaSECircular (Escrita en lenguaje Java):

 

 

public class ListaSECircular<T> implements ILista<T>                 {                     private NodoSE<T> primero;                       // Constructor ......                    public ListaSECircular() {                    }                    // Metodos ......                }

 

 

Esta clase al igual que la lista simplemente enlazada tiene un atributo llamado primero que es un nodo simplemete enlazado el cual contiene un dato y la referecia a otros nodo. A continuacion veremos la representación e implementación del mismo:

Representación:

 

Implementación (Escrita en lenguaje Java):

 

1       public class NodoSE<T> {  2     3          private T dato;  4           private NodoSE<T> siquiente;  5  6          public NodoSE(T dat, NodoSE<T> sig) {  7                dato = dat;  8                siquiente = sig;  9         }              10          public NodoSE(T dat) {   11              dato = dat;  12      }  13  14       public T getDato() {  15             return dato;  16      }  17  18       public void setDato(T dato) {  19             this.dato = dato;  20        }  21  22        public NodoSE<T> getSiquiente() {  23            return siquiente;  24        }  25  26       public void setSiquiente(NodoSE<T> siquiente) {  27            this.siquiente = siquiente;  28       }

 

¿Cómo recorrer la  Lista Circular Simplemente  Enlazada?

Para llegar a un elemento en particular o al último nodo de la lista Circular Simplemente  Enlazada, es necesario recorrerla. Como los enlaces en la lista simplemente enlazada solo van hacia adelante hay que comenzar por la única referencia conocida: el primer nodo (atributo primero).

El gráfico siguiente muestra como llegar al último nodo de la Lista Circular Simplemente  Enlazada, a través de una referencia a los  Nodos llamado cursor:

 

 

El código  siguiente (Escrito en lenguaje Java) recorre  la lista hasta el final:

1            NodoSE<T> cursor = primero; // inicializacion de cursor 2               while (!cursor.getSiquiente().equals(primero)) // condicion de parada 3                 { 4                  cursor = cursor.getSiquiente();  // pasando al siguiente elemento 5                 }

 

Línea 1: Se inicializa un objeto de tipo NodoSE llamado cursor que apunta en el nodo primero.

Línea 2: Comienza un ciclo repetitivo con el objetivo de recorrer la lista a través del objeto cursor. La condición de que no se llegue al final no es más que la referencia al siguiente nodo sea el primero (definición de Lista Circular)

Línea 4: En esta línea se hace apuntar cursor al siguiente nodo.

 

Implementación del método:  Adicionar (Escrita en lenguaje Java).

 

1         public void Adicionar(T dato)   2        {   3             if (primero == null)      // caso 1 ......    4               {   5               primero = new NodoSE<T>(dato); // construir un nodo con el dato entrado   6               primero.setSiquiente(primero); // referencia al primer elemento   7               }        8            else                            // caso 2 ......    9              {   10              NodoSE<T> cursor = primero; // paso 1   11                 while (!cursor.getSiquiente().equals(primero)) // paso 1   12                  {   13                  cursor = cursor.getSiquiente();  // paso 1   14                  }   15   16             NodoSE<T> aux = new NodoSE<T>(dato, primero); // paso 2   17             cursor.setSiquiente(aux);         // paso 3   18             }   19       }

 

Cuando vamos a adicionar un nuevo elemento hay dos posibles estados en los que puede encontrarse la lista circular:

Caso 1: la lista está vacía. El primer elemento que no es mas que el atributo primero es nulo es decir: primero = null.

public void Adicionar(T dato)  {  // caso 1 ......                if (primero == null)      {      //......

 

 

 

En este caso:

Linea 5: Se construye un nuevo elemento y se coloca en la primera posición.

5               primero = new NodoSE<T>(dato); // construir un nodo con el dato entrado

 

 

Linea 5: Se le da como referencia siguiente al primer elemento que a la vez es el último la del él mismo.

6                       primero.setSiquiente(primero); // referencia al primer elemento

 

Posible error que se puede cometer en este caso 1:

Se podría pensar que se pueden hacer estos 2 pasos en uno solo:

                 

primero = new NodoSE<T>(dato,primero); // unico paso

 

Es decir pasar directo el dato y la referencia de primero al construir el nuevo nodo. Error garrafal ya que hasta que no se iguale primero con el nuevo nodo que se construye, este poseerá referencia nula, es decir que cuando pasamos por parámetro en el constructor de nodo a primero este todavía es nulo. Lo que resultaría si lo hacemos así es lo siguiente:

 

 

 

Caso 2: la lista contiene al menos 1 elemento. El  atributo primero no es  nulo.

1         public void Adicionar(T dato)   2        {   3             if (primero == null)      // caso 1 ......    4               {   5               primero = new NodoSE<T>(dato); // paso 1   6               primero.setSiquiente(primero); // paso 2   7               }        8            else                            // caso 2 ......    9              {

 

En este caso:

Línea 10: se inicializa una variable de tipo NodoSE en el nodo primero.

Línea 11: Comienza un ciclo repetitivo mientras no se llegue a la posición final. La condición de que no se llegue al final no es más que el siguiente nodo sea primero (definición de Lista Circular)

Línea 21: En esta línea se pasa a apuntar cursor al siguiente nodo.

 

 

En el paso 1: se busca el nodo que se encuentra en el final, esto se hace a través de un nodo temporal que recorrer la lista de nodos desde el primero  hasta que encuentra el último que apunta nuevamente al primero nodo.

8            else                            // caso 2 ......    9              {   10              NodoSE<T> cursor = primero; // paso 1   11                 while (!cursor.getSiquiente().equals(primero)) // paso 1   12                  {   13                  cursor = cursor.getSiquiente();  // paso 1   14                  }

 

 

 

En el paso 2: se construye el nuevo nodo a adicionar, pasándole el dato entrado por parámetro y como referencia siguiente el primer nodo.

16             NodoSE<T> aux = new NodoSE<T>(dato, primero); // paso 2

 

 

En el paso 3: el último nodo se le pasa por referencia siguiente el nuevo nodo creado en el paso 2. Este es el último paso, el código completo se ve a continuación:

17             cursor.setSiquiente(aux);         // paso 3

 

 

Implementación del método  Eliminar.

El método Eliminar, es capaz de eliminar el elemento de la listas en una posición deseada la cual debe ser válida.

1          public void Eliminar(int pos) throws  ListaVacia,  PosicionNoValida   2         {   3             if (primero == null) // caso 1 ......    4                                throw new ListaVacia();   5         // caso 2 ......………………………………………….   6           int longitud = Longitud();  // Paso 1   7           if (pos < 0 || pos > longitud) // Paso 1   8                    throw new PosicionNoValida();// Paso 1   9   10            if (pos == 0) // Paso 2   11                  {   12                           if (longitud == 1)  // paso 2.1   13                         {   14                         primero = null;   // paso 2.1   15                         }   16                       else       // paso 2.2   17                         {   18                           // buscando la última posición   19                             NodoSE<T> cursor = primero; //paso 2.2   20                     while (!cursor.getSiquiente().equals(primero))  //paso 2.2   21                          {   22                          cursor = cursor.getSiquiente();  //paso 2.2   23                         }   24                           primero = primero.getSiquiente();  //paso 2.2   25                           aux.setSiquiente(primero);  //paso 2.2   26                          }   27                  }   28                  else    // Paso 3   29                  {   30                              NodoSE<T> cursor = primero;  // Paso 3.1   31                              for (int i = 0; i < pos - 1; i++)       // Paso 3.1   32                              {   33                                          cursor = cursor.getSiquiente();  // Paso 3.1   34                              }   35   36                              cursor.setSiquiente(cursor.getSiquiente().getSiquiente());  // Paso 3.2   37                  }  38      }

 

Cuando vamos a eliminar un elemento hay dos posibles estados en los que puede encontrarse la lista circular:

Caso 1: El primer elemento es nulo, la lista está vacía,  es decir: primero = null. En este caso no se puede eliminar elemento alguno, y estaremos en presencia de un error que debe ser tratado.

 

1                  public void Eliminar(int pos)throws ListaVacia, PosicionNoValida   2                      {   3                    if (primero == null) // caso 1 ......    4                                throw new ListaVacia();   5                    // caso 2 ......  ………………………………………….

 

Caso 2: El primer elemento no es nulo, por lo tanto la lista contiene al menos 1 elemento.

 

 

 

En este caso:

En el paso 1: se verifica que la posición entrada por parámetro este en el rango de 0 a la longitud que posee la lista. En caso de no cumplirse esta premisa se lanza una excepción.

 

1          public void Eliminar(int pos) throws  ListaVacia,  PosicionNoValida   2         {   3             if (primero == null) // caso 1 ......    4                                throw new ListaVacia();   5         // caso 2 ......………………………………………….   6           int longitud = Longitud();  // Paso 1   7           if (pos < 0 || pos > longitud) // Paso 1   8                    throw new PosicionNoValida(); // Paso 1   9

 

 

En el paso 2: se pueden se verifica que la  posición a eliminar es 0:

10            if (pos == 0) // Paso 2

 

En el paso 2.1: se verifica que la longitud de la lista sea 1, en este caso se elimina el primer elemento y queda vacía la lista.

10            if (pos == 0) // Paso 2   11                  {   12                           if (longitud == 1) // paso 2.1   13                         {   14                         primero = null;   // paso 2.1   15                         }

 

 

En el paso 2.2: la longitud de la lista es mayor a 1, en este caso se elimina el primer elemento y se actualiza la referencia siguiente del último elemento.

16                       else       // paso 2.2   17                         {   18                           // buscando la última posición   19                             NodoSE<T> cursor = primero; //paso 2.2   20                       while (!cursor.getSiquiente().equals(primero))  //paso 2.2   21                               {   22                              cursor = cursor.getSiquiente();  //paso 2.2   23                               }   24                           primero = primero.getSiquiente();  //paso 2.2   25                           cursor.setSiquiente(primero);  //paso 2.2   26                          }   27                  }

 

De la línea 18 a la 23 a través de un nodo auxiliar se busca el nodo de la última posición de la lista.

En la línea 24 se hace a apuntar el primer nodo al siguiente, con el propósito de eliminar el primero.

En la línea 25 se hace a apuntar el último nodo al primero y con esto queda todo listo.

En el paso 3: la longitud de la lista es mayor a 1 y la posición del elemento a eliminar es mayor que 0.

 

 

En el paso 3.1: se hace apuntar a  un nodo auxiliar en la posición anterior a la que se desea eliminar.

 

28                  else    // Paso 3   29                  {   30                              NodoSE<T> cursor = primero;  // Paso 3.1   31                              for (int i = 0; i < pos - 1; i++)       // Paso 3.1   32                              {   33                                          cursor = cursor.getSiquiente();  // Paso 3.1   34                              }   35

 

 

En el paso 3.2: se cambia la referencia siguiente del nodo auxiliar, al elemento siguiente del que se desea eliminar. Con esto concluye el método eliminar:

 

35   36                              cursor.setSiquiente(cursor.getSiquiente().getSiquiente());  // Paso 3.2   37                  }  38      }

 

 

 

Implementación del método  Longitud.

El método Longitud, es capaz de consultar todos los nodos y hacer un conteo que permite saber la cantidad de elementos de la lista.

1           public int Longitud() 2           { 3                  // caso 1 ............  4                 if (primero==null) 5                         return 0; 6                  // caso 2 ............ 7                 NodoSE<T> cursor = primero; 8                 int cant = 1; 9                while(!cursor.getSiquiente().equals(primero)) 10              { 11              cursor = cursor.getSiquiente(); 12              cant++; 13              } 14         return cant; 15        }

 

 

 

Cuando vamos a consultar la longitud dos posibles estados en los que puede encontrarse la lista circular:

Caso 1: El primer elemento es nulo, la lista está vacía,  es decir: primero = null. En este caso la longitud es 0 por supuesto.

    

1           public int Longitud() 2           { 3                  // caso 1 ............  4                 if (primero==null) 5                         return 0;

 

 

Caso 2: El primer elemento no es nulo, la lista posee al menos un nodo. En este caso la para calcular la  longitud se  recorren todos los nodos a travez de un nodo temporal nombrado cursor.

1                  // caso 2 ............ 2                 NodoSE<T> cursor = primero; // Inicializacion de cursor 3                 int cant = 1; // contandor en valor 1 contando el primero 4                while(!cursor.getSiquiente().equals(primero))   // condicion de  recorrido 5                { 6                cursor = cursor.getSiquiente();  // pasando al siguiente nodo 7                cant++;   // contando los nodos 8                } 9           return cant;  // retornando el valor 10        }

 

 

 

En este caso:

Línea 17: se inicializa una variable de tipo NodoSE en el nodo primero.

Línea 18: Luego se inicializa un contador en 1 pues ya estaría contando que hay un elemento en la primera posición.

Línea 19: Comienza un ciclo repetitivo mientras no se llegue a la posición final. La condición de que no se llegue al final no es más que el siguiente nodo sea primero (definición de Lista Circular)

Línea 21: En esta línea se pasa a apuntar cursor al siguiente nodo.

Línea 22: Se va incrementando la cantidad de nodos.

Línea 24: Finalmente se retorna la cantidad.