LA mente

2010
UNAN – LEON
Departamento de Computación
Ing. En Sistemas Sabatino
Docente: Ing. Karina Esquivel A.
Asignatura:
Practicas Profesionales.

ESTRUCTURAS DINÁMICAS DE DATOS
(LISTAS)

Estructuras Dinámicas de Datos

TEMA 3: ESTRUCTURAS DINÁMICAS DE DATOS
(LISTAS)
3.1

INTRODUCCIÓN:

Las estructuras dinámicas nos permiten crear estructuras de datos que se adapten a lasnecesidades
reales a las que suelen enfrentarse nuestros programas. A través de estas podremos crear
estructuras de datos muy flexibles, en cuanto al orden, la estructura interna o las relaciones entre
los elementos que las componen.
Las estructuras de datos están compuestas de otras pequeñas estructuras a las que llamaremos
nodos o elementos, que agrupan los datos con los que trabajará nuestroprograma y además uno o más
punteros autoreferenciales, es decir, punteros a objetos del mismo tipo.
Dentro de los datos de este tipo de datos podemos hablar de:
Listas.
Pilas.
Colas.
Árboles.

3.2

LISTA LINEAL ENLAZADA:

Una lista lineal enlazada es un conjunto de elementos u objetos de cualquier tipo, originariamente
vacía que, durante la ejecución del programa va creciendo o decreciendoelemento a elemento según
las necesidades previstas. En una lista lineal cada elemento apunta al siguiente, es decir, cada
elemento tiene información de dónde esta el siguiente. Por este motivo también se le llama lista
enlazada.
La forma más simple de estructura dinámica es la lista enlazada. En esta forma los nodos se organizan
de modo que cada uno apunta al siguiente, y el último noapunta a nada, es decir, el puntero del nodo
siguiente vale NULL.
En las listas lineales existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un
puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese
único puntero podemos acceder a toda la lista.
Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que lalista está vacía.

2

Estructuras Dinámicas de Datos

El nodo típico para construir listas tiene esta forma:
struct nodo
{
int dato;
struct nodo *siguiente;
};
En el ejemplo, cada elemento de la lista sólo contiene un dato de tipo entero, pero en la práctica no
hay límite en cuanto a la complejidad de los datos a almacenar.
Dependiendo del número de punteros y de las relaciones entrenodos, podemos distinguir varios tipos
de estructuras dinámicas:
LISTAS SIMPLEMENTE ENLAZADA (o abiertas): Cada elemento (nodo) sólo dispone de un
puntero, que apuntará al siguiente elemento de la lista o valdrá NULL si es el último elemento. Sólo se
pueden recorrer hacia delante.
PILAS: Son un tipo especial de lista, conocidas como listas LIFO (Last In, First Out): el
último en entrar es elprimero en salir). Los elementos se "amontonan" o apilan, de modo que sólo el
elemento que está encima de la pila puede ser leído, y sólo pueden añadirse elementos encima de la
pila.
COLAS: Otro tipo de listas, conocidas como listas FIFO (First In, First Out: El primero en
entrar es el primero en salir). Los elementos se almacenan en fila, pero sólo pueden añadirse por un
extremo y leerse porel otro.
LISTAS CIRCULARES: También llamadas listas cerradas, son parecidas a las listas
enlazadas, pero el último elemento apunta al primero. De hecho, en las listas circulares no puede
hablarse de "primero" ni de "último". Cualquier nodo puede ser el nodo de entrada y salida. Se
recorren siempre en el mismo sentido.
LISTAS DOBLEMENTE ENLAZADAS: Cada elemento dispone de dos punteros, unoapunta al
siguiente elemento y el otro al elemento anterior. Al contrario que las listas abiertas anteriores,
estas listas pueden recorrerse en los dos sentidos.

3.2.1

LISTAS SIMPLEMENTE ENLAZADAS:

La forma más simple de estructura dinámica es la lista simplemente enlazada o lista abierta. En
esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no...