Sistemas





INDICE
INDICE………………………………………………………………………………………………………………...1
DEFINICION……….…………………………………………………………………………………………………2
OPERACIONES BASICAS………………………………………………..................................................................3
AÑADIR UN ELEMENTO DE UNA LISTA DOBLEMENTE ENLAZADAS VACIA…………………………3
INSERTAR UN ELEMENTO EN LA PRIMERA POSICION DE LA LISTA…………………………………..4
INSERTAR UN ELEMENTO ENLA ULTIMA POSICION DE LA LISTA…………………………………….5
ELIMINAR UN ELEMENTO DE UNA LISTA DOBLEMENTE ENLAZADA…………………………………6
ELIMINAR EL ÚNICO NODO EN UNA LISTA DOBLEMENTE ENLAZADA……………………………….6
ELIMINAR EL PRIMER NODO DE UNA LISTA DOBLEMENTE ENLAZADA……………………………..7
ELIMINAR EL ÚLTIMO NODO DE UNA LISTA DOBLEMENTE ENLAZADA…………………………….7
ELIMINAR UN NODO INTERMEDIO DE UNA LISTA DOBLEMENTEENLAZADA……………………...8
EJEMPLO DE LISTA………………………………………………………………………………………………...9








DEFINICIÓN
Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.
Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquiernodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos.
El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior:

struct nodo {
int dato;
struct nodo *siguiente;
struct nodo *anterior;
};

Para C y basándonos en la declaración de nodo que hemos visto más arriba,trabajare
mos con los siguientes tipos:
typedef struct _nodo {
int dato;
struct _nodo *siguiente;
struct _nodo *anterior;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo.
Lista es el tipo para declarar listas abiertas doblemente enlazadas. Tambiénes posible, y potencialmente útil, crear listas doblemente enlazadas y circulares.





El movimiento a través de listas doblemente enlazadas es más sencillo, y como veremos las operaciones de búsqueda, inserción y borrado, también tienen más ventajas.




OPERACIONES BÁSICAS CON LISTAS DOBLEMENTE ENLAZADAS


Es similar al de listas:
1. Añadir o insertar elementos.
2. Borrarelementos.
3. Moverse a través de la lista, siguiente y anterior.



AÑADIR UN ELEMENTO

La estructura s diferente a las vistas anteriormente por lo que se analizaran todos los casos posibles de inserción.


AÑADIR ELEMENTO EN UNA LISTA DOBLEMENTE ENLAZADA VACÍA

también se parte que se dispone del nodo a inserta y el puntero que define la lista, que valdrá NULO:




El proceso esmuy simple:
lista apunta a nodo.
Lista^.siguiente y lista^.anterior apunten a NULO



INSERTAR UN ELEMENTO EN LA PRIMERA POSICIÓN DE LA LISTA

Se parte de una lista no vacía y lista apunta al primer elemento de la lista doblemente enlazada:













El proceso es el siguiente: Nodo^.siguiente debe apuntar a Lista. Nodo^.anterior apuntará a Lista^.anterior.Lista^.anterior debe apuntar a nodo.














La 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, se parte 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 (NULO).
2. Lista^.siguiente debe apuntar a nodo.
3. Nodo^.anterior apuntará a Lista.




ELIMINAR UN ELEMENTO DE UNA LISTA DOBLEMENTE ENLAZADA

Se Analizan cuatro casos diferentes:
1. Eliminar el único nodo de una lista...