Estructura de Datos : Lista Enlazada Doble Encabezada

Definiciones

• En la literatura inglesa, la Lista Enlazada Doble Encabezada se conoce como Headed Doubly Linked List.
• Los nodos de la Lista Enlazada Doble Encabezada tienen por lo menos 3 campos, DATA, LLINK ( Left Link ) y RLINK ( Right Link ).

Representaciones

Representación Gráfica ( Graphic Representation )

               +---+
             L |   |......
               +---+     .
                         .       LLINK  DATA  RLINK
                         ......>+------------------+
                           .....|..*  | ---- |  *..|....                                 Nodo Cabeza                                     Lista Vacia
                           .    +------------------+   .
                           .       A            A      .
                           .       .            .      .
                           .........            ........


               +---+
             L |   |......
               +---+     .
                         .       LLINK  DATA  RLINK
                         ......>+------------------+
 ..............................>|  *  | ---- |  *  |<..............................      Nodo Cabeza                                     Lista Vacia
 .                              +------------------+                              .
 .                                 .            .                                 .
 .                                 .            .                                 .
 .                                 .            .                                 .
 .                                 ..................................             .
 .             ..................................                   .             .
 .             .                                                    .             .
 .             .                                                    .             .
 .             .     ...............            ...............     .             .
 .             .     .             .            .             .     .             .
 .             v     .             V            .             V     V             .
 .   +------------------+       +------------------+       +------------------+   .
 ....|..*  | ---- |  *  |       |  *  | ---- |  *  |       |  *  | ---- |  *..|....      Nodos Datos
     +------------------+       +------------------+       +------------------+
                     A             .            A             .
                     .             .            .             .
                     ...............            ...............

La escencia de las Listas Enlazadas Dobles Encabezadas

                     RLINK(LLINK(P)) = P    P = LLINK(RLINK(P))

                     ...............            ...............
                     .             .            .             .
                     .             V            .             V
     +------------------+       +------------------+       +------------------+
 ....|..*  | ---- |  *  |       |  *  | ---- |  *  |       |  *  | ---- |  *..|....      Nodos Datos
     +------------------+       +------------------+       +------------------+
                     A             .   Nodo P   A             .
                     .             .            .             .
                     ...............            ...............

                     Voy hacia atras           Voy hacia delante
                         y vuelvo                   y vuelvo

Funciones

Eliminación ( Delete )

Elimina el nodo Y de la lista L, ambas variables de entrada.

• procedure DDELETE(Y,L)
  • if Y = L
    • then
      • call NO_MORE_NODES
    • else
      • RLINK(LLINK(Y)) <---- RLINK(Y)
      • LLINK(RLINK(Y)) <---- LLINK(Y)
      • call RETNODE(Y)
• end DDELETE

Inserción ( Insert )

Inserta el nodo Y en la lista L, luego del nodo X, todas variables de entrada.

• procedure DINSERT(X,Y,L)
  • LLINK(Y) <---- X
  • RLINK(Y) <---- RLINK(X)
  • LLINK(RLINK(X)) <---- Y
  • RLINK(X) <---- Y
• end DINSERT