LISTAS DOBLEMENTE ENLAZADAS
Una lista doblemente enlazada es una variedad de lista en la que cada nodo tiene dos enlaces: uno al nodo siguiente y otro al anterior.
Las listas doblemente enlazadas pueden recorrerse en ambos sentidos (de atrás hacia delante y al revés) a partir de cualquier nodo. Necesitaremos, como en las otras listas, de, como mínimo, un puntero a alguno de los nodos de la lista, para a partir de él poder acceder al resto. Es habitual, sin embargo, mantener dos punteros: uno al primer elemento y otro al último.
El tipo de dato básico para construir los nodos de la lista es diferente al de las listas, ya que ahora necesitamos dos punteros en cada nodo. Así, para construir, por ejemplo, una lista doblemente enlazada de números enteros necesitaremos esta estructura:
{
int dato;
struct nodo *siguiente;
struct nodo *anterior;
};
typedef struct s_nodo t_nodo;
t_nodo *primero, *ultimo;
El repertorio de operaciones básicas es el mismo que en las listas
- Insertar elementos.
- Buscar elementos.
- Borrar elementos.
LISTAS CIRCULARES
Una lista circular es una variedad de lista en la que el último nodo a punta al primero en lugar de apuntar a NULL.
En estas listas el concepto de “nodo primero” es una convención, porque en realidad no existe: todos los nodos son anteriores a otro y siguientes de otro. No hay principio ni fin de la lista, aunque debemos mantener un puntero a al menos uno de los nodos para poder iniciar desde él las operaciones sobre la lista.
En las listas circulares, por lo tanto, no hay casos especiales, salvo que la lista este vacía.
Los tipos de datos que se emplean son los mismos que en el caso de las listas. Así, para construir una lista de números enteros necesitaremos una estructura de este tipo:
{
int dato;
struct s_nodo *siguiente;
};
typedef struct s_nodo t_nodo;
t_nodo* nodo;
Fíjese en que el puntero a un nodo de la lista lo hemos llamado “nodo” en lugar de “primero”. Esto se debe a que, como hemos dicho, en una lista circular no hay “primero” ni “último”. Recuerde que para construir una lista con otros datos que no sean de tipo entero, bastaría con cambiar la definición del campo “dato” en la estructura s_nodo.
En cuanto a las operaciones básicas que se pueden realizar con listas circulares, son las mismas que con listas, es decir:
- Insertar elementos.
- Buscar elementos.
- Borrar elementos.
