Estructuras de Datos: Lista Enlazada

Si han revisado los posts anteriores, para realizar un ordenamiento de elementos nos valíamos de un arreglo para contener los elementos a ordenar. Los arreglos en Java tienen un tamaño fijo en memoria asignado al momento ser instanciado: Si nuestro arreglo fue instanciado con una longitud de 100 y sólo colocamos en él 30 elementos hay 70 espacios en memoria que están siendo desperdiciados. Por otro lado, si requerimos ordenar ahora 101 elementos el arreglo anterior no nos sirve y necesitamos instanciar uno más grande. Ahora, si queremos insertar un elemento en medio de un arreglo ya poblado tenemos que desplazar todos los elementos hasta encontrar el lugar apropiado para nuestro nuevo elemento. Si nuestro arreglo es demasiado grande tantos desplazamientos pueden hacer sufrir al CPU de la máquina donde estamos ejecutando el algoritmo.

Para evitarnos estos inconvenientes, podríamos dejar de usar los arreglos y usar una estructura de datos que no tenga un tamaño fijo y cuyo coste de inserción sea significativamente menor, como las Listas Enlazadas. De acuerdo a Data Structures and Algorithms in Java, las Listas Enlazadas se ven así:

Una Lista Enlazada está compuesta por una serie de Nodos (o Links), donde cada Nodo contiene la data almacenada y una referencia al siguiente Nodo de Lista; de este modo la Lista sólo necesita una referencia al primer Nodo para poder tener acceso a todos sus elementos. En la imagen se ve que para insertar un elemento en la primera posición de la Lista, sólo es necesario cambiar la referencia a este primer elemento para que apunte hacia el nuevo elemento; y el elemento nuevo debe apuntar hacia el ex-primer elemento como su elemento posterior.

Pero tanto palabrerío se comprende mejor en Java:

 package test;  
 public class SortedList {  
      private Link first;  
      public SortedList() {  
           first = null;  
      }  
      public boolean isEmpty() {  
           return (first == null);  
      }  
      public void insert(long key) {  
           Link newLink = new Link(key);  
           Link previous = null;  
           Link current = first;  
           while (current != null && key > current.dData) {  
                previous = current;  
                current = current.next;  
           }  
           if (previous == null) {  
                first = newLink;  
           } else {  
                previous.next = newLink;  
           }  
           newLink.next = current;  
      }  
      public Link remove() {  
           Link temp = first;  
           first = first.next;  
           return temp;  
      }  
      public void displayList() {  
           System.out.print("List (first-->last): ");  
           Link current = first;  
           while (current != null) {  
                current.displayLink();  
                current = current.next;  
           }  
           System.out.println("");  
      }  
 }  
 class Link {  
      public long dData;  
      public Link next;  
      public Link(long dd) {  
           dData = dd;  
      }  
      public void displayLink() {  
           System.out.print(dData + " ");  
      }  
 }  

Esta no es una Lista Enlazada cualquiera, tiene la peculiaridad que ingresa los nodos en orden. La clase Link representa cada Nodo de la Lista,  y cómo mencionaba tiene sólo dos atributos: la data que contiene y la referencia al siguiente Nodo de la Lista. Por otro lado, nuestra Lista Enlazada -representada en la clase SortedList- sólo tiene el atributo first, que hace referencia al primer elemento de la Lista.

En nuestra Lista los elementos son ingresados en orden mediente el método insert. Para eso hacemos lo siguiente:

1. Creamos una nueva instancia de Link (o sea, un nuevo Nodo) con el valor a insertar.
2. Declaramos dos variables locales: La variable current nos servirá para almacenar el Nodo sobre el que nos encontramos al recorrer la Lista mientras que previous será utilizada para almacenar el Nodo anterior al Nodo en el que nos encontramos.
3. Empezamos el recorrido de la lista desde el primer elemento, haciendo que current haga referencia a first.
4. Recorreremos el arreglo mientras tenga elementos (current != null) hasta que encontremos los nodos entre los que debemos insertar el nuevo elemento.
5. Cuando hemos salido del bucle ya tenemos la ubicación del elemento a insertar, sólo nos queda reasignar los atributos next del Nodo previous (para que apunte al nuevo Nodo) y del Nodo newLink (para que referencie al Nodo current)

Podríamos utilizar esta Lista para ordenar elementos y no tener que utilizar los algoritmos de posts pasados. Analizando la eficiencia de esta estructura, vemos que es costoso agregar elementos a la lista dado que -en el peor escenario- tendríamos que comparar al nuevo elemento con todos los elementos de la Lista. Por otro lado, el tiempo que nos toma extraer el menor elemento es mínimo, constante y no depende del tamaño de la Lista dado que este elemento siempre se encontrará en  el atributo first de nuestra Lista (y lo podemos obtener mediante el método remove). 

Código fuente e imágenes tomadas de Data Structures and Algorithms in Java.