Las estructuras dinámicas lineales son estructuras cuyo crecimiento depende directamente de las instrucciones del programa. A diferencia de los arreglos, que son fijos, su almacenamiento se realiza en bloque contiguos de memoria y están constituidos por nodos que se amplían o reducen dependiendo de la ejecución del programa.

Las estructuras dinámicas lineales que se estudiaran en esta unidad son: pilas, colas, listas enlazadas simples y listas enlazadas dobles.

Objetivo general

Elaborar algoritmos de estructuras dinámicas lineales para el desarrollo de software.

Objetivos específicos

• Identificar los diferentes de algoritmos de estructuras dinámicas lineales para resolver problemas en desarrollo de software.
• Interpretar los diferentes de algoritmos de estructuras dinámicas lineales para resolver problemas en desarrollo de software.
• Analizar los diferentes de algoritmos de estructuras dinámicas lineales para resolver problemas en desarrollo de software.
• Emplear los diferentes de algoritmos de estructuras dinámicas lineales para resolver problemas en desarrollo de software.

Ante todo se debe tener claro que una lista es una colección o secuencia de elementos, uno detrás del otro, en donde cada elemento se conecta al otro por medio de un enlace o referencia. La lista se compone de dos partes: la información y la referencia o enlace.

También resulta necesario determinar que el nodo es un elemento tipo de dato abstracto que consta de dos partes: datos y referencia.

Clasificación de las listas

Las listas se clasifican en:

• Lista de enlace simple: cada nodo contiene una sola parte de enlace.
• Lista de enlace doble: cada nodo contiene dos partes de enlace al siguiente nodo y al anterior nodo.
• Lista de enlace circular simple: cada nodo contiene una parte de enlace al siguiente nodo, pero su diferencia esta que el último nodo se enlaza con el primer nodo de la lista.
• Lista de enlace circular doble: cada nodo contiene dos partes de enlace al siguiente nodo y al anterior nodo, pero su diferencia esta que el último nodo se enlaza con el primer nodo de la lista y el primer nodo de la lista se enlaza con el último nodo de la lista.
• Pilas: es una lista de enlace simple que solo puede ser accedida por el extremo superior de la pila y se puede añadir o quitar nodos. Las entradas de la pila deben ser eliminadas en el orden inverso al que se le situaron.
• Colas: es una lista de enlace simple que solo puede ser accedida por el extremo superior de la cola, se puede añadir o quitar nodos, las entradas de la cola deben ser eliminadas en el orden al que se le situaron.

A manera de contextualización, se sugiere ver el video Listas Enlazadas Genéricas en Java.

Material de apoyo

La lista de enlace simple es una estructura dinámica donde el número de nodos puede variar rápidamente dependiendo de los requerimientos del proceso: los nodos aumentan por inserciones a la lista o disminuyen por eliminación.

La lista de enlace simple se caracteriza por tener únicamente un enlace al siguiente nodo. Esta lista cuenta con un nodo cabeza y un nodo al final de la lista.

Se accede a la lista mediante el primer nodo de esta llamado “cabeza” o “cabecera” y el último nodo llamado “cola”, cada enlace del nodo apuntará al siguiente, el último nodo apuntará a nulo. Se debe contar con un apuntador que se encarga de referenciar al primer nodo de la lista y otro apuntador al nodo final de la lista.

Garbage Collection es un proceso de la JVM que revisa constantemente qué objetos pueden ser borrados y cuáles no. Cuando un nodo se queda sin apuntador alguno, éste es candidato para ser borrado.

Es una estructura dinámica, donde el número de nodos puede variar dependiendo de las necesidades del proceso: agregando nodos por inserciones o disminuyendo nodos por eliminación.

La lista de enlace doble está caracterizada por tener únicamente dos enlaces: uno al siguiente nodo y otro al anterior nodo. Cuenta con un nodo cabeza y un nodo al final de la lista.

Se accede a la lista mediante el primer nodo de la lista llamado “cabeza” o “cabecera” y el último nodo llamado “cola”, cada enlace del nodo apuntará al siguiente y al anterior nodo.

Se debe contar con un apuntador que se encargar de referenciar al primer nodo de la lista y otro apuntador al nodo final de la lista.

Material de apoyo

La lista circular de enlace simple es una estructura dinámica donde el número de nodos puede variar rápidamente dependiendo de los requerimientos del proceso: aumentando los nodos por inserciones a la lista o disminuyendo nodos por eliminación.

La lista circular de enlace simple se caracteriza por tener únicamente un enlace al siguiente nodo, pero que el enlace del último nodo apunta al primer nodo de la lista. Cuenta con un nodo cabeza y un nodo al final de la lista.

Se accede a la lista mediante el primer nodo llamado “cabeza” o “cabecera” y el último nodo llamado “cola”. Cada enlace del nodo apuntará al siguiente y el último nodo apuntará al primer nodo.

Se debe contar con un apuntador que se encargar de referenciar al primer nodo de la lista y otro apuntador al nodo final de la lista. Esta lista cuenta con unos métodos y operaciones propios.

Se sugiere leer el libro de Programación en C, C++, JAVA Y UML, de los autores Ignacio Zahonero y Luis Joyanes Aguilar (2009), capítulo 36, donde se exponen los temas vistos hasta ahora en esta unidad.

Es una estructura dinámica donde el número de nodos puede variar rápidamente dependiendo de los requerimientos del proceso: aumentando los nodos por inserciones a la lista o disminuyendo nodos por eliminación.

La lista circular de enlace doble se caracteriza por tener dos enlaces al siguiente nodo o predecesor y otro al anterior nodo de la lista o antecesor, pero que el enlace del último nodo apunta al primer nodo de la lista y el primer nodo (cabeza), apunta al último nodo de la lista (cola). Cuenta con un nodo cabeza y un nodo al final de la lista.

Se accede a la lista mediante el primer nodo de la lista llamado “cabeza” o “cabecera” y el último nodo llamado “cola”, cada enlace del nodo apuntará al siguiente, el último nodo apuntará al primer nodo y este a su vez, apuntará al último nodo.

Se debe contar con un apuntador que se encarga de referenciar al primer nodo de la lista y otro apuntador al nodo final de la lista. Al igual que las anteriores listas, la circular de enlace doble tiene los mismos métodos comunes de inserción de un nodo, y las mismas operaciones.

Las listas ordenadas son una variación de las listas y se caracteriza por de que sus datos, al entrar, se ordenan de forma automática; ésta debe garantizar las operaciones de inserción, edición y borrado de nodos dentro de la lista ordenada que a su vez cuenta con un nodo cabeza y un nodo al final de la lista

Se accede a la lista mediante el primer nodo de la lista llamado “cabeza” o “cabecera” y el último nodo llamado “cola”.

Se debe contar con un apuntador que se encargar de referenciar al primer nodo de la lista y otro apuntador al nodo final de la lista.

Las posibilidades de insertar un nodo en la lista ordenada son:

• Que sea el primer nodo de lista ordenada.
• Que sea el nodo mayor al último y este se convierta en el último nodo de la lista.
• Que el nodo se inserte en medio de dos nodos.

Una pila es una variante de la listas que consiste en la técnica últimos en entrar, primeros en salir, del inglés Last Input, First Output (LIFO). Un ejemplo cotidiano es lo que se ve en un restaurante donde se apilan bandejas; los clientes siempre cogerán la que está encima de la pila de bandejas.

Este tipo de estructura tendrá un apuntador cabeza y un apuntador cola, los nodos siempre entran por la cabeza y se sacan por la cabeza de la lista. La pila solo tiene dos operaciones: PUSH, ingresa nuevo nodos a la lista y POP saca nodos de la lista.

Si un nodo pierde el apuntador a la referencia del nodo, el “Garbage Collector” eliminará el nodo y liberará la memoria ocupada.

La aplicación de las pilas se puede evidenciar en el juego matemático de las Torres de Hanoi.

A manera de contextualización, se sugiere consultar la siguiente lectura sobre las Torres de Hanoi.

Una cola es una variante de la listas que consiste en la técnica primero en entrar, primero en salir, del inglés: First Input, First Output (FIFO), un ejemplo cotidiano es el de una entidad bancaria, en el que el cajero atenderá a los clientes de acuerdo con el orden de llegada¹.

Este tipo de estructura tendrá un apuntador cabeza y un apuntador al último nodo, los nodos siempre entran por el apuntador que apunta al último nodo y se sacan por la cabeza de la lista.

Las operaciones básicas sobre una estructura de tipo cola son:

• Encolar: que consiste en insertar un nodo al final de lista.
• Desencolar: que elimina de la lista y devuelve el valor del nodo eliminado.

Material de apoyo

En un principio la programación de estructuras se empleaba para realizar simples arreglos, pero con el transcurrir del tiempo los procesos se volvieron más complejos.

El avance y crecimiento de la programación de estructuras permitió conocer aspectos como el tiempo de ejecución y los que en las estructuras dinámicas permiten el crecimiento de éstos utilizando técnicas algorítmicas para resolver problemas por medio de la programación como son: listas de simples, dobles, circulares, pilas y colas.

En esta unidad se abordó la implementación de listas, pilas y colas que facilitan desarrollar algoritmos de estructuras dinámicas lineales para la implementación de software.

Material de apoyo