Listas Ligadas Y Doblemente Ligadas

Listas ligadas.

Una lista ligada es un grupo de datos organizados secuencialmente, pero a diferencia de los arreglos, la organización no esta dada implícitamente por su posición en el arreglo.

En una lista ligada cada elemento es un nodo que contiene el dato y además una liga al siguiente dato.

Estas ligas son simplemente variables que contienen la(s) dirección(es) de los datos contiguos o relacionados

Para manejar una lista es necesario contar con un apuntador al primer elemento de la lista denominado "cabeza".

En una lista ligada se pueden realizar básicamente 4 operaciones:

 Recorrer: Moverse sobre los elementos de la lista, partiendo del inicio y llegando al final.

 Insertar: Añadir elementos a la lista.

 Eliminar: Quitar elementos de la lista.

 Buscar: Verificar la existencia de un elemento dado dentro de la lista.

Listas doblemente ligadas.

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 cualquier nodo, 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;

};

Operaciones básicas con listas doblemente enlazadas

• Añadir o insertar elementos.

• Buscar o localizar elementos.

• Borrar elementos.

• Moverse a través de la lista, siguiente y anterior.

...