estructdinamicasdatos

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 las necesidades
reales a las quesuelen 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á nuestro programa y además uno o máspunteros 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 decreciendo elemento a elemento según
lasnecesidades 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 no apunta a nada, es decir, el puntero del nodosiguiente 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 la lista está vacía.

2

Estructuras Dinámicas deDatos

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 entre nodos, podemos distinguir varios tipos
de estructurasdiná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 el primero en salir). Los elementos se "amontonan" o apilan, de modo quesó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 por el otro.
LISTAS CIRCULARES: También llamadas listas cerradas, sonparecidas 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, uno apunta al
siguiente elemento y el otro al elemento anterior. Al contrario que laslistas 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 apunta a
nada, es decir, el puntero del nodo siguiente vale NULL:

La anterior es una...