Lunes 18 de Octubre

Listas Enlazadas (continuación)

Objetivos: Mostrar algunas técnicas que se pueden usar con las listas enlazadas para hacerlas más simples y más eficientes .

Temas:

Implementación eficiente de una cola con listas enlazadas

La eficiencia se logra colocando en la estructura de la cola una referencia del último eslabón de la lista enlazada:

    class StringQueue extends Program {
      EslabonCola primero;
      EslabonCola ultimo;
      ... // Los métodos getString, put y size
    }
Con esta referencia es posible llegar directamente al último eslabón sin tener que visitar todos los eslabones de la lista enlazada:

    void put(String s) {
      EslabonCola e= new EslabonCola(s, null);
      if (primero==null)
        primero= ultimo= e;
      else {
        ultimo.prox= e;
        ultimo= e;
      }
    }
Análisis del tiempo de ejecución de cada operación:

Con esta implementación encolar un string en la cola es igual de eficiente que extraer el primer elemento.

Eliminación del caso de borde en que la lista esta vacía

El truco consiste en hacer que la lista nunca esté vacía. Para ello se crea un primer eslabón falso. Este eslabón no contiene nigún string de la cola. Sólo esta ahí para evitar que la lista enlazada quede sin eslabones:

    class StringQueue extends Program {
      EslabonCola primero;
      EslabonCola ultimo;
      StringQueue() {
        primero= ultimo= new EslabonCola(null, null); // eslabón falso
      }
      String getString() {
        if (primero.prox==null) {
          println("Cola vacia");
          exit();
        }
        String s= primero.prox.s;
        primero.prox= primero.prox.prox;
        return s;
      }
      int size() {
        int cont= 0;
        EslabonCola e= primero.e;
        while (e!=null) {
          e= e.prox;
          cont= cont+1;
        }
        return cont;
      }
      void put(String s) {
        ultimo.prox= new EslabonCola(s, null);
        ultimo= ultimo.prox;
      }
    }
Observe que esto no significa que la cola no pueda estar vacía. La cola está vacía cuando la lista enlazada contiene exactamente un eslabón (el eslabón falso).

Colas de objetos

Basta cambiar los datos contenidos en los eslabones. En vez de colocar una referencia de un String, se coloca una referencia de un objeto:

    class EslabonCola {
      Object o;
      EslabonCola prox;
      EslabonCola(Objecto o, EslabonCola prox) {
        this.o= o;
        this.prox= prox;
      }
    }
La implementación es la misma sólo que cambia el tipo del dato que se manipula:

    class Queue extends Program {
      EslabonCola primero;
      EslabonCola ultimo;
      ...
      Object get() {
        Object o= primero.prox.o;
        primero.prox= primero.prox.prox;
        return o;
      }
      void put(Object o) {
        ultimo.prox= new EslabonCola(o, null);
        ultimo= ultimo.prox;
      }
    }

Colas con objetos y strings

En la cola anterior se pueden colocar string porque en Java los strings son objetos. El problema es que al sacarlos de la cola se obtienen como objetos y no como strings:

    Queue q= new Queue();
    q.put("hola"); // Proyección
    q.put("que");
    String s= q.get(); // Error durante la compilación
El error se produce porque get entrega un objeto, y un objeto es más general que un string y por lo tanto no se puede almacenar en una variable de tipo String. Observe que put recibe un objeto como parámetro y se le pasa un string como argumento. Esto sí se puede hacer porque un string es una forma más restringida de objeto, pero es un objeto finalmente.

La última instrucción se puede escribir de la siguiente forma para que no de error:

    Object s= q.get(); // Correcto en compilación y ejecución
    ... substring(s, 1, 2) ... // Error en tiempo de compilación
Ahora no es posible operar con el objeto como un string. Para poder almacenarlo en una variable de tipo String y así poder aplicarle las operaciones que acepta un string se debe usar un cast:

    String s= (String)q.get(); // Correcto en compilación y ejecución
    ... substring(s, 1, 2) ... // Correcto

Colas con objetos y tipos primitivos

En la cola anterior no se pueden colocar tipos de datos primitivos como los enteros, reales y valores de verdad. Estos tipos de datos no son objetos y por lo tanto al colocarlos como argumentos de la operación se produce un error de tipos durante la compilación:

    q.put(1); // Error de tipos en tiempo de compilación
Esto significa que los enteros no pueden ser considerados como una subclase de Object. Para solucionar este problema Java ofrece la clase Integer que sí es una subclase de Object. La operaciones que acepta esta clase son las siguientes:

Ejemplo Significado Declaración
Integer objent= new Integer(1); Construye un objeto Integer que almacena el 1 Integer(int i)
int i= objent.intValue() Entrega el valor entero almacenado en objent int intValue()

El objeto objent es un objeto y por lo tanto puede ser colocado en una cola:

    q.put(objent); // Correcto
Sin embargo, al ser un objeto pierde sus operaciones como entero y no se puede operar como tal:

    objent= objent+1; // Error de tipos en tiempo de compilación
Con la clase Integer ahora es posible almacenar cualquier entero en una cola. Supongamos que necesitamos agregar el entero e en una cola y posteriormente extraerlo. Entonces el siguiente código es una receta para lograr esto:

    q.put(new Integer(e));  // Coloca el entero e en la cola
    ...
    int f= ((Integer)q.get()).intValue(); // Recupera el valor e de la cola
Java también ofrece las clases estándares Double y Boolean para trabajar con los reales y los valores de verdad como objetos. Observe que se diferencian únicamente de los tipos de datos primitivos double y boolean porque Double y Boolean comienzan con una letra mayúscula y porque Double y Boolean son subclases de Object.

Implementación de la clase Integer

    class Integer {
      private int e; // No es accesible desde fuera de la clase
      Integer(int e) {
        this.e= e;
      }
      int intValue() {
        return e;
      }
    }