Miércoles 13 de Octubre

Listas Enlazadas

Objetivos: Mostrar cómo se efectúan algunas operaciones básicas en una lista enlazada.

Temas:

Implementación de una cola

La clase Queue que ha sido usada en el curso puede encolar enteros, reales, valores booleanos, strings o incluso cualquier objeto. Ahora veremos una versión simplicada que sólo permite almacenar strings:

Ejemplo Significado Declaración
StringQueue q= new StringQueue(); Construye una cola de strings vacía StringQueue()
q.put("hola"); Agrega el string "hola" al final void put(String s)
String s= q.getString() extrae y entrega el primer elemento de la cola String getString()
int l= q.size() entrega la cantidad de elementos de la cola int size()

Se puede usar un arreglo para almacenar los elementos de la cola, pero se presentan las mismas deficiencias de la pila implementada con arreglos.

La estructura de datos más conveniente para implementar una cola es la lista enlazada, al igual que la pila. La siguiente figura muestra la estructura de una cola en la que se han encolado los strings "hola", "que" y "tal":

La estructura de los eslabones queda representada por medio de la siguiente clase:

    class EslabonCola {
      String s;
      EslabonCola prox;
      Eslabon(String s, EslabonCola prox) {
        this.s= s;
        this.prox= prox;
      }
    }
Y la estructura de una cola consiste en una referencia del primer eslabón de la cola:

    class StringQueue extends Program {
      EslabonCola primero;
      ... // Los métodos getString, put y size
    }
La variable de instancia primero referencia el eslabón que contiene el primer string de la cola.

Extracción del primer eslabón de una lista enlazada

Para implementar la operación getString es necesario obtener el string contenido en el primer eslabón y luego extraer de la lista enlazada ese eslabón:

    String getString() {
      String s= primero.s;
      primero= primero.prox;
      return s;
    }
La siguiente figura muestra la modificación que se hace en los enlaces para sacar el primer eslabón de la cadena:

Observe que si la cola tenía exactamente un eslabón, después de extraerlo de la cola, la lista enlazada queda sin eslabones.

Recorrer los eslabones de una lista enlazada

El tamaño de la cola está dado por la cantidad de eslabones de la cola. Por lo tanto hay que contar los eslabones:

    int size() {
      int cont= 0;
      EslabonCola e= primero;
      while (primero!=null) {
        e= e.prox;
        cont= cont+1;
      }
      return cont;
    }

Agregar un eslabón al final de una lista enlazada

Para implementar la operación put es necesario agregar un nuevo eslabón al final de la lista enlazada. En este eslabón se coloca el string que se agrega a la cola. Esto no es trivial porque la estructura de la cola no contiene ningún puntero hacia el final de la cola. Por lo tanto hay que recorrer la pila hasta encontrar el último eslabón:

    void put(String s) {
      if (primero==null)
        primero= new EslabonCola(s, null);
      else {
        EslabonCola e= primero;
        while (e.prox!=null)
          e= e.prox;
        e.prox= new EslabonCola(s, null);
      }
    }
Observe que el caso en que la cola está vacía es un caso de borde, porque en ese caso el eslabón debe ser referenciado por la variable de instancia primero. La figura muestra las modificaciones realizadas en las referencias:

Análisis del tiempo de ejecución de cada operación:

En la próxima clase se verán mejoras a la eficiencia de esta implementación.