domingo, 17 de febrero de 2013

Como se puede ver de la imagen anterior una lista está compuesto de nodos. Cada nodo tendrá tres campos:

- información o dato
- anterior
- siguiente

Ahora sí, podemos representar un nodo mediante una clase en Java. A esta clase la llamaremos Nodo. A continuación el código de la clase Nodo.

public class Nodo {
    //Campos del nodo
    int informacion;
    Nodo anterior;
    Nodo siguiente;

    //constructor que inicializa un Nodo con cierta informacion o dato
    public Nodo(int dato) {
        informacion = dato;
        anterior = null;
        siguiente = null;
    }
}


Ahora que tenemos la implementación del nodo podemos pasar a implementar la LDE. Para implementar una LDE vamos a nombrar al primer nodo cabeza haciendolo un nodo con nombre propio (esta es sólo una opción pues otras personas prefieren usar una referencia al primer nodo en lugar de hacer especial el primer nodo). Además, nombraremos al último nodo fin. Por lo tanto tenemos los siguientes casos:

- Si la lista está vacía (no hay ningún elemento) no existirán los nodos cabeza ni fin y por lo tanto seránnull.
- Si solamente hay un nodo en la lista esta será cabeza y fin a la misma vez. Por ejemplo, la siguiente imagen es una lista en donde hay un solo dato (15), el nodo cabeza tiene como dato 15 y comosiguiente y anterior igual a null y el nodo fin también.



A continuación se muestra el código que esquematizará a una LDE

public class ListaDoblementeEnlazada {
    Nodo cabeza;
    Nodo fin;

    //constructor que crea una LDE vacia.
    public ListaDoblementeEnlazada() {
        cabeza = null;
        fin = null;
    }
}


Ahora debemos implementar las operaciones que se han de realizar en la LDE (esto va a ocupar muuuchas líneas). Algunas de estas operaciones son

Insertar al frente: Inserta un nodo delante del actual nodo cabeza (en este caso, 'cabeza' se actualiza con el nuevo nodo).

Insertar al final: Inserta un nodo al final de la lista, es decir, insertar detrás del nodo 'fin' actualizándolo con el nuevo nodo.

Eliminar del frente: Elimina el nodo del frente ( 'cabeza' ) y actualiza 'cabeza' con el nodo que le sigue en la lista.

Eliminar del final: Elimina el nodo final ( 'fin' ) y lo actualiza con el nodo que lo antecedía.

Buscar: Busca un dato en la lista y si lo encuentra devuelve una referencia al nodo buscado, si no lo encuentra devuelve null.

Existen otras operaciones dependiendo de la necesidad que se tenga. Por ejemplo, se puede eliminar un elemento dentro de la lista como el quinto elemento. 

Antes de implementar estas operaciones vamos a crear un método de la lista que nos indique si la lista está vacía o no.

Para saber si una lista está vacía o no es averiguando si el nodo cabeza es null o no. Si el nodo cabeza es null la lista estará vacía. A continuación el código de este método dentro de la claseListaDoblementeEnlazada (en color rojo).

public class ListaDoblementeEnlazada {
    Nodo cabeza;
    Nodo fin;

    //constructor que crea una LDE vacia.
    public ListaDoblementeEnlazada() {
        cabeza = null;
        fin = null;
    }

    //indica si la lista está vacia
    private boolean estaVacia() {
        boolean vacia = false;
        if ( cabeza == null ) {
            vacia = true;
        }
        return vacia;
    }

}


Ahora sí, vamos a las operaciones mencionadas.

Insertar al frente

Tenemos dos casos: La lista está o no vacía. Esto se puede saber mediante el método estaVacia()implementado arriba.

a) Si la lista está vacía simplemente nombramos el nuevo nodo como 'cabeza' y 'fin'. Esto se puede hacer con:
cabeza = nuevo;
fin = nuevo;


b) Si la lista no está vacía entonces seguimos los siguientes pasos:

paso 1. Hacemos que el nuevo nodo apunte a 'cabeza' como su siguiente nodo. Esto se puede hacer con:
nuevo.siguiente = cabeza;

paso 2. Hacemos que el nodo 'cabeza' apunte al nuevo nodo como su anterior nodo. Esto se puede hacer con:
cabeza.anterior = nuevo;

Al final nombramos al nuevo nodo como 'cabeza'. Esto se puede hacer con:
cabeza = nuevo;

La siguiente imagen muestra los pasos descritos

No hay comentarios:

Publicar un comentario