Estructura de Datos : Lista Enlazada Doble

Definiciones

• Es un tipo de lista enlazada que permite moverse hacia delante y hacia atras.
• Cada nodo de una lista doblemente enlazada tiene dos enlaces, ademas de los campos de datos. Un enlace, el derecho, se utiliza para navegar la lista hacia delante. El otro enlace, el isquierdo, se utiliza para navegar la lista hacia atras.
• Las Listas pueden navegarse hacia delante y hacia atras.
• Las Listas pueden crear, actualizar y eliminar elementos.
• En las Listas la posicion de los elementos es relevante.
• Las Listas admiten elementos duplicados.
• Las Listas tienen dos protocolos, uno secuencial y el otro directo.

Representaciones

Representación Enlazada

                     ...............            ...............            ...............
                     .             .            .             .            .             .
                     .             V            .             V            .             V
     +------------------+       +------------------+       +------------------+       +------------------+
     |  0  | ---- |  *  |       |  *  | ---- |  *  |       |  *  | ---- |  *  |       |  *  | ---- |  0  |          Nodos Datos
     +------------------+       +------------------+       +------------------+       +------------------+
                     A             .            A             .            A             .
                     .             .            .             .            .             .
                     ...............            ...............            ...............

     * Significa un enlace v lido a un nodo

     0 Significa el final de la lista o enlace nulo

Representacion Secuencial

                                +--------------+
                                |     next     |
                                |              |
                                |              |
     *--------*     *--------*  |  *--------*  |  *--------*     *--------*     *--------*     *--------*     *--------*     *--------*
     |        |     |        |  |  |        |  |  |        |     |        |     |        |     |        |     |        |     |        |
     |        |     |        |  X  |Elemento|  V  |        |     |        |     |        |     |        |     |        |     |        |
     |        |     |        |     |        |     |        |     |        |     |        |     |        |     |        |     |        |
     |        |     |        |  A  |Devuelto|  X  |        |     |        |     |        |     |        |     |        |     |        |
     |        |     |        |  |  |        |  |  |        |     |        |     |        |     |        |     |        |     |        |
     *--------*     *--------*  |  *--------*  |  *--------*     *--------*     *--------*     *--------*     *--------*     *--------*
                                |              |
                                |              |
                                |   previous   |
                                +--------------+

      Elemento       Elemento       Elemento       Elemento       Elemento       Elemento       Elemento       Elemento       Elemento

      Indice 0       Indice 1       Indice 2       Indice 3       Indice 4       Indice 5       Indice 6       Indice 7       Indice 8

Representacion Lineal

                 Elemento  1    Elemento  2    Elemento  3    Elemento  2    Elemento  4    Elemento  5    Elemento  6    Elemento  1
                   adicion        adicion        adicion      eliminacion      adicion        adicion        adicion      eliminacion

 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |Elemento  1|  |Elemento  1|  |Elemento  1|  |Elemento  1|  |Elemento  1|  |Elemento  1|  |Elemento  1|  |Elemento  3|
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |Elemento  2|  |Elemento  2|  |Elemento  3|  |Elemento  2|  |Elemento  2|  |Elemento  3|  |Elemento  4|
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |           |  |Elemento  3|  |           |  |Elemento  4|  |Elemento  4|  |Elemento  4|  |Elemento  5|
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |           |  |           |  |           |  |           |  |Elemento  5|  |Elemento  5|  |Elemento  6|
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |           |  |           |  |           |  |           |  |           |  |Elemento  6|  |           |
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |           |  |           |  |           |  |           |  |           |  |           |  |           |
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |           |  |           |  |           |  |           |  |           |  |           |  |           |
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*
 |           |  |           |  |           |  |           |  |           |  |           |  |           |  |           |  |           |
 *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*  *-----------*

   Tiempo t1      Tiempo t2      Tiempo t3      Tiempo t4      Tiempo t5      Tiempo t6      Tiempo t7      Tiempo t8      Tiempo t9

La escencia de las Lista Enlazada Doble

Asumamos a P ser un pointer, o sea, una variable que solo tiene referencias a nodos.

                     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

Eliminacion ( 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

Insercion ( 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

Interfases

Interfase Funcional

Funciones Primitivas

        int     create()
        void    begin(int l)
        void    beginAt(int l, int index)
        boolean hasNext(int l)
        Object  next(int l)
        int     nextIndex(int l)
        boolean hasPrevious(int l)
        Object  previous(int l)
        int     previousIndex(int l)
        void    add(int l, Object element)
        void    addAt(int l, int index, Object element)
        void    set(int l, Object element)
        Object  setAt(int l, int index, Object element)
        void    remove(int l)
        Object  removeAt(int l, int index)

El metodo create crea una Lista y devuelve su identificador.

El metodo begin permite la navegacion de la Lista a partir del primer elemento de la misma.

El metodo beginAt permite la navegacion de la Lista a partir de cualquier elemento de la misma.

El metodo next recupera el siguiente objeto de la lista. Invocando repetidamente este metodo se visitan todos los objetos de la lista, uno a uno.

El metodo hasNext retorna true si existen mas objetos en la lista y retorna false en caso contrario. Siempre, antes de invocar la recuperacion del siguiente objeto, debe consultarse si existen mas objetos en la lista en dicha direccion.

El metodo nextIndex devuelve el indice del elemento recuperado por el ultimo next.

El metodo previous recupera el objeto previo de la lista. Invocando repetidamente este metodo se visitan todos los objetos de la lista, uno a uno.

El metodo hasPrevious retorna true si existen mas objetos en la lista y retorna false en caso contrario. Siempre, antes de invocar la recuperacion del objeto previo, debe consultarse si existen mas objetos en la lista en dicha direccion.

El metodo previousIndex devuelve el indice del elemento recuperado por el ultimo previous.

El metodo add adiciona un elemento antes de la posicion corriente.

El metodo addAt adiciona el objeto a partir del elemento especificado.

El metodo set reemplaza el ultimo elemento visitado por next o previous por el nuevo elemento.

El metodo setAt reemplaza el objeto de la posicion especificada.

El metodo remove elimina de la lista el ultimo objeto recuperado.

El metodo removeAt elimina el objeto de la posicion especificada.

Funciones Secundarias

        int      size(int l)
        boolean  isEmpty(int l)
        boolean  contains(int l, Object obj)
        boolean  containsAll(int l, Collection c)
        boolean  equals(int l, Object other)
        boolean  addAll(int l, Collection from)
        boolean  remove(int l, Object obj)
        boolean  removeAll(int l, Collection c)
        void     clear(int l)
        boolean  retainAll(int l, Collection c)
        Object[] toArray(int l)

        void     addAllAt(int l, int index, Collection elements)
        int      indexOf(int l, Object element)
        int      lastIndexOf(int l, Object element)

El metodo size retorno el numero de elementos actualmente almacenados en la coleccion.

El metodo isEmpty retorna true si no existen elementos en la coleccion.

El metodo contains retorna true si la coleccion contiene un objeto igual a obj.

El metodo containsAll retorna true si la coleccion contiene todos los objeto de la coleccion other.

El metodo addAll retorna true si la coleccion ha cambiado por la adicion de todos los objetos de la coleccion other.

El metodo removeAll retorna true si la coleccion ha cambiado por la eliminacion de todos los objetos de la coleccion other.

El metodo clear elimina todos los objetos de la coleccion.

El metodo retainAll retorna true si la coleccion ha cambiado por la eliminacion de todos los objetos no iguales de la coleccion other.

El metodo toArray retorna un Arreglo formado por los objetos de la coleccion.

El metodo addAllAt adiciona todos los objetos de la coleccion c a partir del elemento especificado.

El metodo indexOf retorna el indice de la primera ocurrencia del Objeto especificado.

El metodo lastIndexOf retorna el indice de la ultima ocurrencia del Objeto especificado.