Listas doblemente enlazadas

Lista Doblemente Enlazada
Existen dos tipos de listas doblemente ligadas:
* Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL o NULL.
* Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del últimonodo apunta al primer nodo de la lista.
Importancia:
* Nos permite almacenar datos de una forma organizada
* Es una estructura tipo de dato abstracto ( TDA) dinámica
* Cada nodo de la lista doblemente enlazada contiene dos punteros, de forma que uno apunta al siguiente nodo y el otro al predecesor.( permite que se pueda recorrer la lista en ambos sentidos)

Lista DoblementeEnlazada lineal
Las listas de enlace simple restringen el movimiento por los nodos a una sóla dirección: no puede atravesar una lista de enlace simple en dirección opuesta a menos que primero utilice el algoritmo de inversión para invertir los enlaces de los nodos, lo que lleva tiempo. Después de atraversarlos en dirección opuesta, problamente necesitará repetir la inversión para restaurar elorden original, lo que lleva aún más tiempo. Un segundo problema implica el borrado de nodos: no puede borrar un nodo arbitrario sin acceder al predecesor del nodo. Estos problemas desaperecen cuando se utiliza una lista doblemente enlazada.
Una lista doblemente enlazada es una lista enlazada de nodos, donde cada nodo tiene un par de campos de enlace. Un campo de enlace permite atravesar la listahacia adelante, mientras que el otro permite atravesar la lista hacia atrás. Para la dirección hacia adelante, una variable de referencia contiene una referencia al primer nodo. Cada nodo se enlaza con el siguiente mediante el campo de enlace next, excepto el último nodo, cuyo campo de enlace next contiene null para indicar el final de la lista (en dirección hacia adelante). De forma similar,para la dirección contraria, una variable de referencia contiene una referencia al último nodo de la dirección normal (hacia adelante), lo que se interpreta como el primer nodo. Cada nodo se enlaza con el anterior mediante el campo de enlace previous, y el primer nodo de la dirección hacia adelante, contiene null en su campo previous para indicar el fin de la lista. La siguiente figura representauna lista doblemente enlazada de tres nodos, donde topForward referencia el primer nodo en la dirección hacia adelante, y topBackward referencia el primero nodo la dirección inversa.



La inserción y borrado de nodos en una lista doblemente enlazada son operaciones comunes. Estas operaciones se realizan mediante algoritmos que se basan en los algoritmos de inserción y borrado de laslistas de enlace simple (porque las listas doblemente enlazadas sólo son una pareja de listas de enlace simple que interconectan los mismos nodos).
El siguiente listado muestra la inserción de nodos para crear la lista de la figura anterior, el borrado de nodos ya que elimina el nodo B de la lista, y el movimiento por la lista en ambas direcciones:
class DLLDemo {static class Node {
String name;
Node next;
Node prev;
}

public static void main (String [] args) {
// Build a doubly linked list

Node topForward = new Node ();
topForward.name ="A";

Node temp = new Node ();
temp.name = "B";

Node topBackward = new Node ();
topBackward.name = "C";

topForward.next = temp;
temp.next = topBackward;
topBackward.next = null;...