Lista Doblemente Enlazada

Lista Doblemente Enlazada

Las listas de enlace simple restringen el movimiento por lo 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 el orden 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 lista hacia adelante, mientras que el otro permite atravesar la lista haca 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 nextcontiene null para indicar el final de la lista (en direccion 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 direccion hacia adelante, contiene null en su campo previous para indicar el fin de la lista. La siguiente figura representa una lista doblemente enlazada de tres nodos, donde topForward referencia el primer nodo en la direccion hacia adelante, y topBackward referencia el primero nodo la dirección inversa.

Truco:

Piense en una lista doblemente enlazada como una pareja de listas de enlace simple que interconectan los mismos nodos.

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 las listas de enlace simple (porque las listas doblemente enlazadas sólo son una pareja de listas de enlace simple que interconectan los mismos nodos).

...