Lista Doblemente Enlazada

Listas doblemente enlazadas o doblemente ligadas

Una lista doblemente enlazada es simplemente un conjunto de elementos o datos que aparecen uno detrás de otro (al igual que en una lista simplemente ligada o enlazada). En la siguiente imagen se observa una lista doblemente enlazada (LDE a partir de ahora) con tres datos numéricos simples (números enteros): 12, 57 y 95.

Como se puede ver dela imagen anterior una lista está compuesta 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 queinicializa 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 haciéndolo un nodo con nombre propio (esta es sólo una opción pues otras personas prefieren usar una referencia al primernodo 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án null.
- 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 como siguiente 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 sehan 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 elnodo 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. Porejemplo, 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 lasoperaciones 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...