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

...