Trabajo de algoritmo

Qué son las listas doblemente enlazadas.

Las listas doblemente enlazadas es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor (ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.
Son básicamente estructuras de datos semejantes alas listas enlazadas simples. La asignación de memoria es hecha al momento de la ejecución.
En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente).
Existen dos tipos de listas doblemente enlazadas:
• Listas dobles lineales. En este tipo delista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL o NULL.
• Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.
Importancia:
Nos permite almacenar datos de una forma organizada, Además es unaestructura TDA dinámica. Donde cada nodo de la lista doblemente enlazada contiene dos punteros, de forma que uno apunta al siguiente nodo y el otro al predecesor. (Permite que se pueda recorrer la lista en ambos sentidos)
Estructura
typedef struct s_nodo
{
ELEM info;
struct s_nodo *ant, *sig;
} NODO;

Como se puede ver en la figura n°1


El puntero anterior del primer elemento debe apuntarhacia 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 elementoanterior.
Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al último elemento y/o del último al primer elemento.

Características:
Añadir elemento en una lista doblemente enlazada 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á conque:
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:
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.

Insertar un elemento en la última posición de la lista:
partiremos de una lista no vacía, y de nuevo para simplificar, que Lista está apuntando al último elemento de la lista 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.Insertar un elemento a continuación de un nodo cualquiera de una lista:
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:
Hacemos que nodo->siguiente apunte a lista->siguiente.
Hacemos que Lista->siguiente apunte a nodo.
Hacemos que nodo->anterior apunte a lista.
Hacemos que nodo->siguiente->anterior apunte a nodo.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,...