Listas Doblemente Enlazadas

Ahora escribiré un poco sobre las listas doblemente enlazadas, las cuales son similares a las simplemente enlazadas, con la diferencia en que el enlace entre los elementos se hace gracias a dos punteros, uno que apunta al anterior y otro que apunta al elemento siguiente.

El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista).
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: Comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento. Comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.

A continuación algunas acciones que se pueden llevar a cabo con las listas, junto con un ejemplo en C.

I. Inserción en una lista vacía

1. Asignación de memoria para el nuevo elemento
2. Rellenar el campo de datos del nuevo elemento
3. El puntero anterior del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía utilizamos la dirección del puntero inicio que vale NULL)
4. El puntero siguiente del nuevo elemento apuntará hacia NULL (ya que la inserción es hecha en una lista vacía se utiliza la dirección del puntero fin que vale NULL)
5. Los punteros inicio y fin apuntaran hacia el nuevo elemento
6. El tamaño es actualizado

Ejemplo gráfico:

Código en C:

int insercion_en_lista_vacia (dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->anterior = lista->inicio;
  nuevo_elemento->siguiente = lista->fin;
  lista->inicio = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

II. Inserción al inicio de la lista:

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. El puntero anterior del nuevo elemento apunta hacia NULL
   
4. El puntero siguiente del nuevo elemento apunta hacia el 1er elemento
   
5. El puntero anterior del 1er elemento apunta hacia el nuevo elemento
   
6. El puntero inicio apunta hacia el nuevo elemento
   
7. El puntero fin no cambia
   
8. El tamaño es incrementado

Ejemplo gráfico:

Código en C:

int ins_inicio_lista(dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->anterior = NULL;
  nuevo_elemento->siguiente = lista->inicio;
  lista->inicio->anterior = nuevo_elemento;
  lista->inicio = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

III. Inserción al final de la lista

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. El puntero siguiente del nuevo elemento apunta hacia NULL
   
4. El puntero anterior del nuevo elemento apunta hacia el ultimo elemento (es el puntero fin que contiene por ahora su dirección)
   
5. El puntero siguiente del ultimo elemento apuntará hacia el nuevo elemento
   
6. El puntero fin apunta hacia el nuevo elemento
   
7. El puntero inicio no cambia
   
8. El tamaño es incrementado

Ejemplo gráfico:

Código en C:

int ins_fin_lista(dl_Lista * lista, char *dato){
  dl_Elemento *nuevo_elemento;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  nuevo_elemento->siguiente = NULL;
  nuevo_elemento->anterior = lista->fin;
  lista->fin->siguiente = nuevo_elemento;
  lista->fin = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

IV. Inserción antes de un elemento de la lista.

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. Elegir una posición en la lista (la inserción se hará después de la posición elegida)
   
4. El puntero siguiente del nuevo elemento apunta hacia el elemento actual.
   
5. El puntero anterior del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero anterior del elemento actual.
   
6. El puntero siguiente del elemento que precede al elemento actual apuntará hacia el nuevo elemento
   
7. El puntero anterior del elemento actual apunta hacia el nuevo elemento
   
8. El puntero fin no cambia
   
9. El puntero inicio cambia si la posición elegida es la posición 1
   
10. El tamaño se incrementa en una unidad

Ejemplo gráfico:

La función

int ins_antes (dl_Lista * lista, char *dato, int pos){
  int i;
  dl_Elemento *nuevo_elemento, *actual;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  nuevo_elemento->siguiente = actual;
  nuevo_elemento-> anterior = actual->anterior;
  if(actual->anterior == NULL)
    lista->inicio = nuevo_elemento;
  else
    actual->anterior->siguiente = nuevo_elemento;
  actual->anterior = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

V. Inserción después de un elemento

1. Asignación de memoria al nuevo elemento
   
2. Rellenar el campo de datos del nuevo elemento
   
3. Elegir una posición en la lista (la inserción se hará después de la posición elegida)
   
4. El puntero siguiente del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero siguiente del elemento actual.
   
5. El puntero anterior del nuevo elemento apunta hacia el elemento actual.
   
6. El puntero anterior del elemento que va después del elemento actual apuntará hacia el nuevo elemento.
   
7. El puntero siguiente del elemento actual apunta hacia el nuevo elemento
   
8. El puntero inicio no cambia
   
9. El puntero fin cambia si la posición elegida es la posición del ultimo elemento (el tamaño de la lista)
   
10. El tamaño se incrementa en una unidad

Ejemplo gráfico:

Código en C:

int ins_después (dl_Lista * lista, char *dato, int pos){
  int i;
  dl_Elemento *nuevo_elemento, *actual;
  if ((nuevo_elemento = alloc (nuevo_elemento)) == NULL)
    return -1;
  strcpy (nuevo_elemento->dato, dato);
  actual = lista->inicio;
  for (i = 1; i < pos; ++i)
    actual = actual->siguiente;
  nuevo_elemento->siguiente = actual->siguiente;
  nuevo_elemento->anterior = actual;
  if(actual->siguiente == NULL)
    lista->fin = nuevo_elemento;
  else
    actual->siguiente->anterior = nuevo_elemento;
  actual->siguiente = nuevo_elemento;
  lista->tamaño++;
  return 0;
}

VI. Eliminación en la lista:

Para esta función podemos tener diferentes situaciones:

• Eliminación en la posición 1 en una lista con un solo elemento
  
• Eliminación en la posición 1 en una lista con varios elementos
  
• Eliminación en la ultima posición (el ultimo elemento)
  
• Eliminación en otra parte de la lista en cierta posición

 

• La posición elegida es 1 (el caso de eliminación del 1er elemento de la lista)




1. El puntero sup_elemento contendrá la dirección del 1er elemento
   
2. El puntero inicio contendrá la dirección contenida por el puntero siguiente del 1er elemento que deseamos eliminar (si este puntero vale NULL entonces actualizamos el puntero fin ya que estamos en el caso de una lista con un solo elemento, si no hacemos apuntar el puntero anterior del 2do elemento hacia NULL)

• la posición elegida es igual al numero de elementos de la lista




1. El puntero sup_elemento contendrá la dirección del ultimo elemento
   
2. Hacemos apuntar al puntero siguiente del penúltimo elemento (es el elemento hacia el que apunta el puntero <anterior> del ultimo elemento), hacia NULL
   
3. Actualizamos el puntero fin

• la posición elegida es aleatoria en la lista




1. El puntero sup_elemento contendrá la dirección del elemento a eliminar
   
2. El puntero siguiente del elemento que antecede al elemento a eliminar apunta hacia la dirección contenida en el puntero siguiente del elemento a eliminar
   
3. El puntero anterior del elemento que va después del elemento a eliminar apunta hacia la dirección contenida en el puntero anterior del elemento a eliminar.
   
4. El tamaño de la lista será disminuida en 1 elemento

Código en C:

int supp(dl_Lista *lista, int pos){
  int i;
  dl_Elemento *sup_elemento,*actual;

  if(lista->tamaño == 0)
    return -1;

  if(pos == 1){ /* eliminación del 1er elemento */
    sup_elemento = lista->inicio;
    lista->inicio = lista->inicio->siguiente;
    if(lista->inicio == NULL)
      lista->fin = NULL;
    else
      lista->inicio->anterior == NULL;
  }else if(pos == lista->tamaño){ /* eliminación del último elemento */
    sup_elemento = lista->fin;
    lista->fin->anterior->siguiente = NULL;
    lista->fin = lista->fin->anterior;
  }else { /* eliminación en otra parte */
    actual = lista->inicio;
      for(i=1;i<pos;++i)
        actual = actual->siguiente;
    sup_elemento = actual;
    actual->anterior->siguiente = actual->siguiente;
    actual->siguiente->anterior = actual->anterior;
  }
  free(sup_elemento->dato);
  free(sup_elemento);
  lista->tamaño--;
  return 0;
}

VII. Visualización de la lista:

Para mostrar la lista entera podemos posicionarnos al inicio o al final de la lista.
Luego utilizando el puntero siguiente o anterior de cada elemento, la lista es recorrida del 1er al ultimo elemento o del ultimo al 1er elemento.
La condición para detener es dada por el puntero siguiente del ultimo elemento que vale NULL en el caso de la lectura del inicio hacia el fin de la lista, o por el puntero anterior del 1er elemento que vale NULL, en el caso de una lectura del final hacia el inicio de la lista.

Código en C:

void affiche(dl_Lista *lista){ /* visualización hacia adelante */
  dl_Elemento *actual;
  actual = lista->inicio; /* punto de inicio el 1er elemento */
  printf("[ ");
  while(actual != NULL){
    printf("%s ",actual->dato);
    actual = actual->siguiente;
  }
  printf("]\n");
}

void mustra_inv(dl_Lista *lista){ /* visualización hacia atrás */
  dl_Elemento *actual;
  actual = lista->fin; /* punto de inicio el ultimo elemento */
  printf("[ ");
  while(actual != NULL){
    printf("%s : ",actual->dato);
    actual = actual->anterior;
  }
  printf("]\n");
}

Como en la entrada anterior, dejo un archivo con todo el código en C del ejemplo de las listas doblemente enlazadas.

http://www.mediafire.com/?b26u6uf887xcdjn

Referencias:

• http://es.kioskea.net/faq/2872-listas-doblemente-enlazadas


• http://c.conclase.net/edd/?cap=005