Listas en Java

Una lista es una secuencia de elementos dispuesto en un cierto orden, en la que cada elemento tiene como mucho un predecesor y un sucesor. El número de elementos de la lista no suele estar fijado, ni suele estar limitado por anticipado. Representaremos la estructura de datos de forma gráfica con cajas y flechas. Las cajas son los elementos y las flechas simbolizan el orden de los elementos.

La estructura de datos deberá permitirnos determinar cuál es el primer elemento y el último de la estructura, cuál es su predecesor y su sucesor (si existen de cualquier elemento dado). Cada uno de los elementos de información suele denominarse nodo.

La lista también puede representarse de forma simbólica escribiendo sus elementos separados por comas y encerrados entre corchetes. Por ejemplo:

["rojo","verde","azul","amarillo"]

Las listas admiten ciertas operaciones como son insertar un nodo adicional, borrar un nodo, etc. En función de la forma de insertar nuevos elementos y acceder a los existente tendremos distintos tipos de listas. Veamos ahora qué operaciones básicas se puedes realizar sobre las listas. Se tratarán aquí las operaciones que permiten insertar y borrar elementos únicamente al principio de la misma, por lo que las operaciones de acceso, inserción y supresión de elementos en cualquier posición de la lista no se consideran básicas pero podrán ser tratadas mediante recursión.

Las operaciones básicas sobre una lista son:

• EsVacia Averiguar si la lista esta vacía.
  
• Insertar Añade un elemento al principio de la lista.
  
• Primero Obtener el valor del primer elemento de la lista, también llamado cabeza.
  
• Resto Devuelve el trozo de lista resultado de eliminar el primer elemento de la lista.
  
• Borrar Borrar el primer elemento de la lista.
  

Las listas pueden ser circulares, con el último elemento apuntando al primero, o pueden tener un campo que contenga el número de nodos que hay en la lista.

Las listas se pueden definir de muchas formas. Podríamos definirlas a partir de un vector teniendo un acceso rápido aunque con un número de elementos limitado por la dimensión del vector.

Otra forma de definir una lista es de forma recursiva. Resulta menos eficiente que definirla a partir de un vector sin embargo no nos impone restricciones en cuanto a su longitud. Veamos como se define en Java cada uno de los elementos de la lista:

Observe como esta estructura se corresponde con las cajas que se habían visto en la representación de listas. Vemos que tiene dos atributos, el elemento que se almacena en cada nodo y el Nodo siguiente en el orden de la lista. A continuación se implementan los métodos de la clase para manipular los nodos:

Nodo.java

El constructor crea un nodo a partir de un objeto y el siguiente nodo al que va a estar enlazado. Las operaciones cambiarElemento y cambiarSiguiente cambian los valores de los campos del objeto. Por último Siguiente y Elemento devuelven el contenido del nodo.

A partir de esta clase implementaríamos las lista como una cadena de nodos:

ListaEnlazada.java

Fíjese como el constructor inicializa la lista a null. Este va a ser también el final de la lista. De forma que cuanto el principio y final de la lista coincidan la lista estará vacía.

Veremos a continuación algunas implementaciones distintas de listas. Se debe prestar especial interés a los mecanismos de implementación, pues las distintas operaciones pueden cambiar de una implementación a otra sin embargo la forma no.