Estructuras Dinámicas
Una estructura de datos dinámica es aquella en la que el tamaño ocupado en
memoria puede modificarse durante la ejecución del programa. Las variables
que se crean y están disponibles durante la ejecución del programa se llaman
variables continuas.
De esta manera se pueden adquirir posiciones adicionales de memoria a
medida que se necesiten durante la ejecución del programa y liberarlas cuando
no se necesiten.
Las variables que se crean y están disponibles durante la ejecución del
programa se llaman variables continuas.
Las estructuras de datos dinámicas se clasifican en lineales (listas, pilas y
colas) y no lineales (árboles y grafos).
Listas
Una lista es una colección de elementos organizados en secuencia que
puede crecer y decrecer libremente y a cuyos elementos individuales se puede
acceder, insertar y eliminar en cualquier posición.
Las listas enlazadas son usadas como módulos para otras muchas
estructuras de datos, tales como pilas, colas y sus variaciones.
Las listas se clasifican en contiguas, enlazadas, circulares y doblemente
enlazadas.
Listas Contiguas: los elementos de la lista se almacenan normalmente
en posiciones consecutivas de memoria, es decir, almacenamiento
secuencial, donde se define la constante longitud máxima, que
determina el tamaño de la mayor lista que se puede tener. Se
implementan a través de arreglos, donde la inserción o eliminación de un
elemento excepto en la cabecera o al final de la lista necesitará una
traslación de los elementos de la lista.
Ejemplo:
Elemento
1 2 3 4 5 6
Lista
Como se puede apreciar en el ejemplo, se trata de una lista contigua de
elementos de tipo entero representados en un arreglo unidimensional de 6
campos, de tal manera que no es posible insertar un nuevo elemento por que
la lista está completa, esta es una de las desventajas de este tipo de lista.
Listas enlazadas: es una colección o secuencia de elementos del
mismo tipo dispuestos uno detrás de otro, en el que cada elemento se
liga al siguiente elemento por un enlace que no es más que un puntero
previamente definido dentro de los miembros de la estructura. Consta de
un numero determinados de nodos con dos componentes, también
conocido como campos, un enlace (puntero) al siguiente nodo de la lista,
y un valor (que puede ser de cualquier tipo).
Ejemplo:
Puntero siguiente valor
A1 A2 A3 An
Nodo
Lista
Una lista enlazada es una estructura de datos dinámica porque se
decide cual es el número de elementos que va a poseer.
Listas doblemente enlazadas: en este tipo de lista ya no existe solo un
puntero, si no que dos, uno a su nodo siguiente y otro a su nodo
anterior. Es decir, se puede ir hacia delante o hacia atrás porque se
tiene los dos punteros.
Ejemplo:
Puntero siguiente valor
A1 A2 A3 An
Nodo Puntero anterior
Lista
Lista circular simplemente enlazada: una lista circular es una lista
lineal en la que el último nodo a punta al primero. Por otra parte, también
evitan excepciones en las operaciones que se realicen sobre ellas.
Ejemplo:
Puntero siguiente valor
A1 A2 A3 An
Nodo
Es una lista enlazada con la única diferencia que l cola de la lista o el
último elemento de la lista apunta hacia el inicio (o primer elemento de
la lista).
Lista circular doblemente enlazadas: en una lista enlazada
doblemente circular, cada nodo tiene dos enlaces, similares a los de la
lista doblemente enlazada, excepto que el enlace anterior del primer
nodo apunta al último y el enlace siguiente del último nodo, apunta al
primero.
Ejemplo:
Puntero siguiente valor
A1 A2 A3 An
Nodo Puntero anterior
Pilas: es una lista ordenada o estructura de datos que permite almacenar y
recuperar datos, siendo el modo de acceso a sus elementos de tipo LIFO (del
inglés Last In, First Out, «último en entrar, primero en salir») . Para el manejo
de los datos cuenta con dos operaciones básicas: apilar (push), que coloca un
objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el
último elemento apilado.
Ejemplo:
Apilar Desapilar
En cada momento solamente se tiene acceso a la parte superior de la
pila, es decir, al último objeto apilado. La operación retirar permite la
obtención de este elemento, que es retirado de la pila permitiendo el
acceso al anterior (apilado con anterioridad), que pasa a ser el último, el
nuevo TOS.
Colas: una estructura fifo (First In First Out), el primero que entra será el
primero en salir.
Ejemplo:
Final Principio
Encolar Desencolar
La particularidad de una estructura de datos de cola es el hecho
de que solo podemos acceder al primer y al último elemento de la
estructura. Así mismo, los elementos solo se pueden eliminar por
el principio y solo se pueden añadir por el final de la cola.
Ejemplos de colas en la vida real serían: personas comprando en
un supermercado, esperando para entrar a ver un partido de
béisbol, esperando en el cine para ver una película, una pequeña
peluquería, etc. La idea esencial es que son todos líneas de
espera.
