Un repaso a listas, pilas y colas con implementación

<J&Q>
25 de Octubre del 2005
Para manejar listas, pilas y colas hay que comprender primero la idea intuitiva de la que se habla.
Estos tres conceptos son muy parecidos entre ellos, asique hablaré solo de las listas, y de manera análoga vosotros podreis sacar una idea de las pilas y las colas.

Una lista esta formada por elementos de cualquier tipo en un orden determinado.
Por ejemplo, podemos hacer una lista de enteros: Sea L la lista de enteros L={2,6,4,8,9}. en la que cada entero es un elemento de la lista. Además de eso, cada elemento esta referenciando al siguiente, de manera que cada uno de ellos "sabe" que orden relativo ocupa en ella.
De esta forma, si pudiesemos hablar con ellos, y le preguntasemos a "2" que quién le sigue, éste nos contestaría con un "6".

Declaro a continuacion una clase que me sirve para construir un elemento o NODO de la lista.

Para la práctica que vamos a ver, nuestros elementos serán numeros enteros, como también lo podrían haber sido caracteres, Strings, y cualquier tipo de objeto que queramos.

class Nodo implements Cloneable{
int Info; /*Nuestro nodo tiene esta información: un numero entero*/
Nodo Siguiente; /*Y almacena también la identidad del Nodo que va después de el. Referenciaremos al nodo siguiente de esta forma:*/


/*Constructor de nodos, le pasamos por los argumentos el valor a guardar y la referencia al nodo siguiente*/
public Nodo(int e, Nodo n)
{
Info = e;
Siguiente = n;
}

/*El único método que implementaremos en esta clase será clone(), que nos permitirá duplicar el nodo*/
public Object clone()
/*Dejo al lector su implementación, que se detalla perfectamente en cualquier manual de referencia*/

/* Una vez sabemos la forma en la cual nuestros elementos serán representados, podemos pasar a declarar la clase Lista_Dinamica, que definirá una lista normal con el ultimo de sus nodos referenciando a null, es decir, que no es enlazada:*/

/*Ejemplo de como sería una lista:

9 -> 2 -> 4 -> 1 -> 6 -> null

Las flechitas indican qué numero es el siguiente, y es lo que hemos visto en la clase Nodo.*/

//Esta sería nuestra clase Lista_Dinamica:

class Lista_Dinamica implements Cloneable {
private int Longitud;
//*En este atributo guardamos un entero con la longitud de la lista, nótese que es private*/

private Nodo NodoCabeza;
//Este atributo es un objeto de tipo Nodo que ya hemos visto y servirá para saber en todo momento, cual es el nodo en cabeza, pues nos basaremos en el y solo en el para trabajar con la lista.

/*Y definiremos también los siguientes métodos para hacer funcional la creación y el manejo de las listas:*/

/*Constructor: Este constructor genera una lista vacia, en la cual, en nodo en cabeza no tiene ningun valor ni referencia a ningun nodo siguiente.*/

public Lista_Dinamica()
{
longitud = 0;
NodoCabeza = null;
}

/*EsVacia() ... si la longitud de la lista es cero,
este método devuelve true*/
public boolean EsVacia(){
return (longitud == 0)
}

/*Añade(Nodo x) esta función irá añadiendo elementos a la lista. para ello, irá generando nuevas cabezas y poniendolas delante de los elementos que ya hayan entrado en la lista*/
public void Añade(int x){
Nodo NuevaCabeza;
longitud++; //Aumenta la longitud una unidad

NuevaCabeza = new Nodo(x,NodoCabeza);
/*hemos construido un nuevo nodo a partir del valor que pasa por el argumento y le hemos dado este al Nodo NuevaCabeza que hemos declarado. (ver clase Nodo más arriba)*/
/*Solo nos queda hacer que esta NuevaCabeza sea realmente la nueva cabeza, que en la clase lista se representa como NodoCabeza (ver atributos de esta clase)*/

NodoCabeza = NuevaCabeza;
}

/*El metodo que viene a continuación es puramente informativo y devuelve el valor del elemento en cabeza*/
public int Cabeza(){
if(longitud == 0) return null;
else return NodoCabeza.Info; /*Devolvemos el atributo Info de la clase Nodo, que almacena un entero (ver clase Nodo)*/
}

/*El siguiente método quita la cabeza de la lista, y devuelve otra lista sin ella. Por ejemplo, si la lista es 5,6,8,9 la lista que devolverá será: 6,8,9*/
public Lista_Dinamica Cola(){
if(longitud == 0) return null;
else{
longitud--;
NodoCabeza = NodoCabeza.Siguiente;
/*Simplemente hacemos que nuestro NodoCabeza pase a ser el siguiente al que referencia de manera que nos "saltamos" a la actual cabeza*/
return this; /*La palabra this es propia de Java y devuelve un objeto que representa el estado actual de ESTA clase, en este caso, sirve para devolver una Lista_Dinamica*/
}//else
}


/*Esté método indica si el elemento que buscamos está o no en la lista*/
public boolean EstaContenido(int x){
Nodo actual = NodoCabeza;
while(actual != null){
/*recordemos que el último elemento de cualquier lista referencia a null, entonces, mientras no lleguemos al último elemento de la lista no pararemos de iterar */
if(x == actual.Info) return true;
/*actual.Info es de tipo entero (ver clase Nodo) Aquí habremos encontrado el elemento y la orden return parará la iteración*/
else{ /*Si aún no lo hemos encontrado, seguiremos buscando quitando la cabeza de la lista como en la función anterior*/
actual = actual.Siguiente;
}//else
return false; /*si hemos llegado aquí quiere decir que el nodo no esta en la lista*/
}//fin
}//FIN DE LA CLASE LISTA_DINAMICA

Está claro que esta clase es muy básica y se me ocurren ahora mismo muchos métodos que podría llevar y que le resultarían útiles, pero voy a parar aquí pues ya hemos visto las operaciones básicas que le podemos hacer a un TAD (tipo abstracto de datos) cualquiera: añadirle elementos, extraer elementos y consultar su estado (vacia o llena) y también un método que determina si un determinado elemento está dentro de la lista, y reitero que la implementación de las colas y pilas es muy similar.
Quiero hacer hincapié en que el lector se fije en como está hecho el ultimo método que hemos visto: EstaContenido, pues sirve para RECORRER UNA LISTA, lo cual se hará muy a menudo:

Forma general de recorrer listas:

Nodo actual;
while ( elementoDeLaLista != null)
actual = actual.Siguiente;

Forma general de crear nodos:

Nodo nuevo; //declarar el nodo
nuevo = new Nodo(elementoQueMetemos, nuevo)
/*hacer que este nodo referencie al nodo en cabeza que vamos a sustituir*/
el elemento introducido debe ser del tipo de elementos que usemos.
recordemos la forma del constructor de Nodos:
public Nodo(int, nuevo) donde int lo podemos cambiar por cualquier tipo de objeto;