I. Introducción
El objetivo de este artículo es la comprensión de las listas doblemente enlazadas.
Las listas doblemente enlazadas pueden ser utilizadas cuando son necesarias varias operaciones de inserción o eliminación de elementos.
II. Definición
Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples.
La asignación de memoria es hecha al momento de la ejecución.
En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente).
El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:
- comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.
- comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.
Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al ultimo elemento y/o del ultimo al primer elemento.
III. La construcción del modelo de un elemento de la lista
Para definir un elemento de la lista será utilizado el tipo struct.
El elemento de la lista contendrá: un campo dato, un puntero anterior y un puntero siguiente.
Los punteros anterior y siguiente deben ser del mismo tipo que el elemento, en caso contrario no podrán apuntar hacia un elemento de la lista.
El puntero anterior permitirá el acceso hacia el elemento anterior mientras que el puntero siguiente permitirá el acceso hacia el próximo elemento.
Para tener el control de la lista es preferible conservar algunos elementos: el primer elemento, el último elemento, el número de elementos.
El puntero inicio contendrá la dirección del primer elemento de la lista.
El puntero fin contendrá la dirección del último elemento de la lista.
La variable tamaño contiene el número de elementos.
Cualquiera que sea la posición en la lista, los punteros inicio y fin apuntan siempre al primer y último elemento.
El campo tamaño contendrá el numero de elementos de la lista cualquiera que sea la operación efectuada sobre la lista.
IV. Operaciones sobre la lista doblemente enlazadas
Para la inserción y la eliminación, una solo función bastará si está bien concebida en función de las necesidades.
Sin embargo, debo recordar que este artículo es puramente didáctico.
Por esta razón he escrito una función para cada operación de inserción y eliminación.
A. Inicialización
Modelo de la función:
package listaDobleEnlace;
public class Nodo
{
int dato;
Nodo adelante;
Nodo atras;
public Nodo(int entrada)
{
int dato;
Nodo adelante;
Nodo atras;
public Nodo(int entrada)
{
dato = entrada;
adelante = atras = null;
}
public int getDato()
{
return dato;
}public Nodo getEnlace()
{
return adelante;
}public void setEnlace(Nodo adelante)
{
this.adelante = adelante;
}
package listaDobleEnlace;
B. Inserción antes de un elemento de la lista
public class ListaDoble
{
Nodo cabeza;
public ListaDoble()
{
Nodo cabeza;
public ListaDoble()
{
cabeza = null;
}public ListaDoble insertarCabezaLista(int entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = cabeza;
if (cabeza != null )
nuevo.adelante = cabeza;
if (cabeza != null )
cabeza.atras = nuevo;
cabeza = nuevo;
return this;
}cabeza = nuevo;
return this;
C. Inserción despues de elemento en la lista
public ListaDoble insertaDespues(Nodo anterior, int entrada)
{
Nodo nuevo;
nuevo = new Nodo(entrada);
nuevo.adelante = anterior.adelante;
if (anterior.adelante !=null)
nuevo.adelante = anterior.adelante;
if (anterior.adelante !=null)
anterior.adelante.atras = nuevo;
anterior.adelante = nuevo;
nuevo.atras = anterior;
return this;
}nuevo.atras = anterior;
return this;
D. Eliminacion de elemento en la lista
public void eliminar (int entrada)
Nodo actual;
boolean encontrado = false;
actual = cabeza;
// Bucle de búsqueda
while ((actual != null) && (!encontrado))
{
while ((actual != null) && (!encontrado))
{
/* la comparación se realiza con el método equals()...,
depende del tipo Elemento */
encontrado = (actual.dato == entrada);
if (!encontrado)
actual = actual.adelante;
if (!encontrado)
actual = actual.adelante;
}// Enlace de nodo anterior con el siguiente
if (actual != null)
{
//distingue entre nodo cabecera o resto de la lista
if (actual == cabeza)
{
//distingue entre nodo cabecera o resto de la lista
if (actual == cabeza)
{
cabeza = actual.adelante;
if (actual.adelante != null)
actual.adelante.atras = null;
}else if (actual.adelante != null)
// No es el último nodo
{
actual.atras.adelante = actual.adelante;
actual.adelante.atras = actual.atras;
actual.atras.adelante = actual.adelante;
actual.adelante.atras = actual.atras;
}else
// último nodo
actual.atras.adelante = null;
actual = null;
}
}
E. Visualizar elemento en la lista
public void visualizar()
Nodo n;
int k = 0;
n = cabeza;
while (n != null)
{
System.out.print(n.dato + " ");
n = n.adelante;
k++;
System.out.print( (((k%10 != 0)&& (n!= null)) ? " " : "\n"));
System.out.print(n.dato + " ");
n = n.adelante;
k++;
System.out.print( (((k%10 != 0)&& (n!= null)) ? " " : "\n"));
}
}
}
