5.3 Operaciones básicas con listas doblemente enlazadas

De nuevo tenemos el mismo repertorio de operaciones sobre este tipo listas:

  • Añadir o insertar elementos.
  • Buscar o localizar elementos.
  • Borrar elementos.
  • Moverse a través de la lista, siguiente y anterior.

5.4 Añadir un elemento

Nos encontramos ahora ante un tipo de estructura algo diferente de las que hemos estado viendo, así que entraremos en más detalles.

Vamos a intentar ver todos los casos posibles de inserción de elementos en listas doblemente enlazadas.

Añadir elemento en una lista doblemente enlazada vacía

Lista vacía Lista de un elemento
Inserción en lista vacía

Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero que define la lista, que valdrá NULL:

El proceso es muy simple, bastará con que:

  1. lista apunta a nodo.
  2. lista->siguiente y lista->anterior apunten a null.

Insertar un elemento en la primera posición de la lista

Partimos de una lista no vacía. Para simplificar, consideraremos que lista apunta al primer elemento de la lista doblemente enlazada:

Insertar al comienzo
Insertar en primera posición

El proceso es el siguiente:

  1. nodo->siguiente debe apuntar a Lista.
  2. nodo->anterior apuntará a Lista->anterior.
  3. Lista->anterior debe apuntar a nodo.
Insertado al comienzo
Nodo insertado en primera posición

Recuerda que Lista no tiene por qué apuntar a ningún miembro concreto de una lista doblemente enlazada, cualquier miembro es igualmente válido como referencia.

Insertar un elemento en la última posición de la lista

Igual que en el caso anterior, partiremos de una lista no vacía, y de nuevo para simplificar, que Lista está apuntando al último elemento de la lista:

Insertar al final
Insertar nodo al final

El proceso es el siguiente:

  1. nodo->siguiente debe apuntar a Lista->siguiente (NULL).
  2. Lista->siguiente debe apuntar a nodo.
  3. nodo->anterior apuntará a Lista.
Insertado al final
Nodo insertado en última posición

Insertar un elemento a continuación de un nodo cualquiera de una lista

Bien, este caso es más genérico, ahora partimos de una lista no vacía, e insertaremos un nodo a continuación de uno nodo cualquiera que no sea el último de la lista:

Insertar
Insertar a continuación de un nodo

El proceso sigue siendo muy sencillo:

  1. Hacemos que nodo->siguiente apunte a lista->siguiente.
  2. Hacemos que Lista->siguiente apunte a nodo.
  3. Hacemos que nodo->anterior apunte a lista.
  4. Hacemos que nodo->siguiente->anterior apunte a nodo.
Insertado
Nodo insertado después de un nodo dado

Lo que hemos hecho es trabajar como si tuviéramos dos listas enlazadas, los dos primeros pasos equivalen a lo que hacíamos para insertar elementos en una lista abierta corriente.

Los dos siguientes pasos hacen lo mismo con la lista que enlaza los nodos en sentido contrario.

El paso 4 es el más oscuro, quizás requiera alguna explicación.

Supongamos que disponemos de un puntero auxiliar, "p" y que antes de empezar a insertar nodo, hacemos que apunte al nodo que quedará a continuación de nodo después de insertarlo, es decir p = Lista->siguiente.

Ahora empezamos el proceso de inserción, ejecutamos los pasos 1, 2 y 3. El cuarto sería sólo hacer que p->anterior apunte a nodo. Pero nodo->siguiente ya apunta a p, así que en realidad no necesitamos el puntero auxiliar, bastará con hacer que nodo->siguiente->anterior apunte a nodo.

Añadir elemento en una lista doblemente enlazada, caso general

Para generalizar todos los casos anteriores, sólo necesitamos añadir una operación:

  1. Si lista está vacía hacemos que Lista apunte a nodo. Y nodo->anterior y nodo->siguiente a NULL.
  2. Si lista no está vacía, hacemos que nodo->siguiente apunte a Lista->siguiente.
  3. Después que Lista->siguiente apunte a nodo.
  4. Hacemos que nodo->anterior apunte a Lista.
  5. Si nodo->siguiente no es NULL, entonces hacemos que nodo->siguiente->anterior apunte a nodo.

El paso 1 es equivalente a insertar un nodo en una lista vacía.

Los pasos 2 y 3 equivalen a la inserción en una lista enlazada corriente.

Los pasos 4, 5 equivalen a insertar en una lista que recorre los nodos en sentido contrario.

Existen más casos, las listas doblemente enlazadas son mucho más versátiles, pero todos los casos pueden reducirse a uno de los que hemos explicado aquí.