listas circulares y doblemente enlazadas

Tema: Listas doblemente enlazadas y listas circulares
Códigos: 5611-5901-5526

Listas Doblemente enlazadas
Es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.
Operaciones básicas con listas doblemente enlazadas De nuevo tenemos el mismorepertorio 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.
Añadir un elemento
Añadir elemento en una lista doblemente enlazada vacía
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
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
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
1. Hacemosque 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.
Añadir elemento en una lista doblemente enlazada, caso general
Para generalizar todos los casos anteriores, sólo necesitamos añadir una operación:
Si lista está vacía hacemos que Lista apunte anodo. Y nodo->anterior y nodo->siguiente a NULL.
Si lista no está vacía, hacemos que nodo->siguiente apunte a Lista->siguiente.
Después que Lista->siguiente apunte a nodo.
Hacemos que nodo->anterior apunte a Lista.
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 equivalena 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.
Buscar o localizar un elemento de una lista doblemente enlazada
1. Retrocedemos hasta el comienzo de la lista, asignamos a lista el valor de lista->anterior mientras lista->anterior no sea NULL.
2. Abriremos un bucle que al menos debe tener unacondición, que el índice no sea NULL.
3. Dentro del bucle asignaremos a lista el valor del nodo siguiente al actual.
Eliminar un elemento de una lista doblemente enlazada
1. Eliminar el único nodo de una lista doblemente enlazada.
2. Eliminar el primer nodo.
3. Eliminar el último nodo.
4. Eliminar un nodo intermedio.
Eliminar el único nodo en una lista doblemente enlazada
1. Eliminamos el nodo.
2.Hacemos que Lista apunte a NULL.

Eliminar el primer nodo de una lista doblemente enlazada
Si nodo apunta a Lista, hacemos que Lista apunte a Lista->siguiente.
1. Hacemos que nodo->siguiente->anterior apunte a NULL
2. Borramos el nodo apuntado por nodo.
El paso 2 depara el nodo a borrar del resto de la lista, independientemente del nodo al que apunte Lista.
Eliminar el último nodo de unalista doblemente enlazada
1. Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior.
2. Hacemos que nodo->anterior->siguiente apunte a NULL
3. Borramos el nodo apuntado por nodo.
Eliminar un nodo intermedio de una lista doblemente enlazada
1. Si nodo apunta a Lista, hacemos que Lista apunte a Lista->anterior (o Lista->siguiente).
2. Hacemos que nodo->anterior->siguiente apunte anodo->siguiente.
3. Hacemos que nodo->siguiente->anterior apunte a nodo->anterior.
4. Borramos el nodo apuntado por nodo.
Eliminar un nodo de una lista doblemente enlazada, caso general
1. De nuevo tenemos los dos casos posibles, que el nodo a borrar esté apuntado por Lista o que no. Si lo está, simplemente hacemos que Lista sea Lista->anterior, si no es NULL o Lista->siguiente en caso...