Estructuras Dinamicas

Estructuras dinámicas: Listas

Una lista es un conjunto de nodos, cada uno de los cuales tiene dos campos: uno de información y un apuntador al siguiente nodo de la lista. Además un apuntador externo señala el primer nodo de la lista.

Representación gráfica de un nodo:

La información puede ser cualquier tipo de dato simple, estructura de datos o inclusive uno o más objetos.

La dirección al siguiente nodo es un puntero.

Representación gráfica de una lista:

Como decíamos, una lista es una secuencia de nodos (en este caso cuatro nodos). La información de los nodos en este caso es un entero y siempre contiene un puntero que guarda la dirección del siguiente nodo.

Raíz es otro puntero externo a la lista que contiene la dirección del primer nodo.

El estado de una lista varía durante la ejecución del programa:

De esta forma representamos gráficamente una lista vacía.

Si insertamos un nodo en la lista quedaría luego:

Listas Enlazadas

Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo.

El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.

El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.

La lista enlazada se muestra en la siguiente figura:

Las operaciones que normalmente se ejecutan con listas incluyen:

1. Recuperar información de un nodo específico.

2. Encontrar el nodo que contiene una información específica.

3. Insertar un nuevo nodo en un lugar específico.

4. Insertar un nuevo nodo en relación a una información particular.

5. Borrar un nodo existente.

Listas Doblemente Enlazadas

Hasta ahora se han manejado listas que se recorren en un asola dirección. En algunas aplicaciones es práctico o hasta indispensable poder recorrer una lista en ambas direcciones. Para estos casos se tienen la lista doblemente enlazadas. Esta propiedad implica que cada nodo debe tener dos apuntadores, uno al nodo predecesor y otro al nodo sucesor.

Listas Circulares

Una lista circular es una lista en la cual el último nodo es enlazado al primer elemento de la lista. La ventaja de este tipo de estructura es que siempre se puede llegar a cualquier nodo siguiendo los enlaces. La desventaja es que si no se tiene cuidado una búsqueda puede resultar en un bucle infinito. Esto se puede evitar al determinar a un nodo como nodo-cabeza o nodo inicial.

Pilas

Una pila es un tipo especial de lista lineal

...