Estructuras Enlazadas

Programación y

Algoritmia

Un enfoque práctico y didáctico

para el diseño de algoritmos

4 Estructuras Enlazadas

Lic. Oscar Ricardo Bruno, MDU

Contenido

Estructuras Enlazadas__________________________________________________ 3

Introducción _______________________________________________________ 3

Estructuras enlazadas vs. estructuras indexadas _________________________ 3

Estructuras enlazadas con asignación dinámica en memoria _______________ 3

El tipo de dato Puntero_______________________________________________ 5

Acceso a datos mediante apuntadores __________________________________ 7

Tipos de datos autorreferenciados o recursivos___________________________ 8

Estructuras de datos dinámicas lineales_________________________________ 9

El tipo pila _________________________________________________________ 9

Insertar elemento en una pila:________________________________________ 11

Desapilar: leer y eliminar un elemento ________________________________ 11

El tipo cola________________________________________________________ 12

Añadir un elemento Encolar: ________________________________________ 12

Leer un elemento de una cola Eliminar primero: ________________________ 13

El tipo lista________________________________________________________ 13

Listas simplemente enlazadas ________________________________________ 13

Eliminar elementos en una lista ______________________________________ 14

Algoritmo de inserción______________________________________________ 16

Listas circulares ___________________________________________________ 18

Operaciones básicas con listas circulares _______________________________ 19

Añadir un elemento ________________________________________________ 19

Eliminar un elemento de una lista circular _____________________________ 20

Listas doblemente enlazadas _________________________________________ 24

Operaciones básicas con listas doblemente enlazadas ____________________ 24

Añadir un elemento ________________________________________________ 24

Eliminar un elemento de una lista doblemente enlazada __________________ 27

A modo de síntesis con estructuras enlazadas ___________________________ 30

Estructuras Enlazadas

Objetivos de aprendizaje

Dominando los temas del presente capitulo Usted podrá.

1. Manejar estructuras complejas.

2. Introducirse a la semántica de direcciones

3. Comprender como se asigna memoria dinámicamente en tiempo de ejecución.

4. Conocer estructuras enlazadas lineales

5. Diferenciar entre estructuras indexadas y estructuras enlazadas

Introducción:

En el presente trabajo se incorpora el concepto de asignación dinámica en memoria.

Esto permite romper con la limitación de tamaño fijo que proporcionan las tablas

cuando es necesario trabajar con colección de datos el mismo tipo en memoria.

Para esto se incorporan los conceptos de estructuras enlazadas, punteros y asignación

dinámica en memoria.

Estructuras enlazadas vs. estructuras indexadas

Como vimos una tabla es una secuencia de datos del mismo tipo donde a cada elemento

se puede acceder a través de un índice. En esta estructura las posiciones de memoria son

contiguas y se las puede ir recorriendo con solo incrementar el índice. En estas

estructuras el primer elemento lógico coincide con el primero físico, es decir se

comienza desde la primera posición, y el siguiente lógico coincide con el siguiente

físico, es decir al próximo elemento se accede incrementando en uno el índice. Estas

estructuras, con esta organización son estructuras indexadas. Las estructuras pueden

organizarse de forma diferente. El primer elemento lógico puede no coincidir con el

primero físico, en ese caso, para conocer donde comienza lógicamente se debe saber la

posición de ese primero. El siguiente elemento lógico no necesariamente debe estar en

la posición contigua, para saber donde esta será necesario tener algo que referencie la

posición del siguiente elemento. Una estructura con esta organización es una estructura

enlazada. Las estructuras enlazadas tienen la particularidad que se necesita conocer la

posición del primer elemento y en cada posición se tiene un registro, llamado nodo, con

al menos dos campos, uno que contenga la información y otro que indique o referencie

donde se encuentra el siguiente que no necesariamente debe ser el contiguo.

Por otro lado vimos que si se quiere definir en memoria una colección de datos del

mismo tipo mediante una tabla esta requiere establecer una capacidad máxima. Estas

son estructuras con tamaño fijo, el mismo no puede ser modificado en tiempo de

ejecución. Existe entonces riesgo que la cantidad de posiciones definidas en tiempo de

declaración no alcancen, o, que se utilicen muy pocas de las posiciones definidas

haciendo un uso poco eficiente de los recursos.

Estructuras enlazadas con asignación dinámica en memoria

Una estructura con asignación dinámica es un conjunto de elementos de tipo

homogéneo donde los mismos no ocupan posiciones contiguas de memoria, pueden

aparecer físicamente dispersos manteniendo un orden lógico y son instanciados y/o

liberados en tiempo de ejecución.

Operaciones con listas

1. Crear una estructura

2. Recorrerla, parcial o totalmente

3. Agregar o insertar nuevos elementos o nodos en distintos lugres y con criterio

variado.

4. Localizar un elemento en particular en la estructura

5. Borrar un elemento de posicion particular o previamente desconocida

La mayor facilidad de las listas es el “enlace dinámico” a través de punteros que

permiten intercalar o eliminar valores sin un movimiento masivo de memoria, con solo

pedir memoria o liberarla y hacer simplemente los enlaces de los nodos involucraos.

Punteros

Es posible definir estructuras de datos complejas cuyo tamaño puede cambiar en tiempo

de ejecución, por lo que son denominadas estructuras de datos dinámicas. Se instancias

a través de punteros.

Mediante la utilización de tablas se puede definir una secuencia de valores como:

TipoSecuencia = TIPO Tabla [1, LongitudMaxima] de elemento;

Con esta definición se reserva espacio en tiempo de ejecución para una cantidad fija de

elementos. Esta cantidad esta

...