ESTRUCTURAS DINÁMICAS LINEALES DE DATOS: LISTAS

[pic 1]

UNIVERSIDAD DE ORIENTE

VICERRECTORADO ACADÉMICO

COORDINACIÓN DE POSTGRADO

MAESTRÍA EN INFORMÁTICA GERENCIAL

SEMINARIO DE ALGORITMOS Y COMPUTACIÓN AVANZADA

MATURIN/MONAGAS/VENEZUELA

ESTRUCTURAS DINÁMICAS LINEALES DE  DATOS: LISTAS

FACILITADOR:                                        AUTORES:

Dr. Juan Oliveira                                        22.725.662 Dubraska, Gamardo

                                                        24.864.573 Contreras, Marianny

                                                        25.273.011 Millán, Raúl

                                                        25.930.113 Martínez, Zuleydis

MATURÍN, AGOSTO DE 2020

INDICE

INTRODUCCIÓN        4

ESTRUCTURAS DINÁMICAS DE DATOS        6

DEFINICIÓN DE ESTRUCTURA DINÁMICA DE DATOS        6

CLASIFICACIÓN DE LAS ESTRUCTURAS DINÁMICAS DE DATOS        7

ESTRUCTURAS DINÁMICAS LINEALES DE DATOS: LISTAS        8

DEFINICIÓN DE LISTA LINEAL CONTIGUA.        8

DEFINICIÓN DE LISTA ENLAZADA.        10

CLASIFICACIÓN DE LISTAS ENLAZADAS.        12

LISTA SIMPLEMENTE ENLAZADA        13

Definición        13

Características        14

Operaciones básicas en listas simplemente enlazadas.        15

LISTA DOBLEMENTE ENLAZADA        21

Definición        21

Características        23

Operaciones básicas en listas doblemente enlazadas.        24

LISTAS CIRCULARES SIMPLEMENTE ENLAZADA        29

Definición        29

Características        31

Operaciones básicas en listas circulares simplemente enlazadas.        32

LISTAS CIRCULARES DOBLEMENTE ENLAZADAS        35

Definición        35

Características        36

Operaciones básicas en listas circulares doblemente enlazadas.        37

CONCLUSIONES        38

REFERENCIAS BIBLIOGRÁFICAS        40

INDICE DE ILUSTRACIONES

Ilustración 1. Representación simple de una lista enlazada        11

Ilustración 2. Lista simplemente enlazada.        13

Ilustración 3. Estructura genérica de un nodo perteneciente a una lista doblemente enlazada.        21

Ilustración 4. Representación simple de una lista doblemente enlazada.        22

Ilustración 5. Lista circular simplemente enlazada.        29

Ilustración 6. Lista circular vacía.        29

Ilustración 7. Lista circular doblemente enlazada.        35

INTRODUCCIÓN

La importancia de las computadoras radica esencialmente en su capacidad para procesar información, esta particularidad les permite efectuar actividades que antes sólo realizaban los humanos. Con la finalidad de que la información sea procesada, es necesario que ésta se almacene en la memoria de la computadora, para que luego se pueda tener acceso a ella. Esta información no es más que un conjunto de datos, que pueden ser simples o estructurados.

En este sentido, las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos. Pueden ser estáticas, cuando ya se asigna su tamaño en memoria y dinámicas cuando no se conoce por adelantado cuánta memoria se requerirá durante un programa. De esta manera, las variables que se crean y están disponibles durante la ejecución de un programa se llaman variables dinámicas y están representadas con un tipo de datos conocido como puntero.

En base a lo planteado, el presente trabajo tuvo como objetivo principal, el estudio de las listas, que es un tipo de estructura lineal y dinámica de datos, siendo lineal porque a cada elemento le puede seguir solo otro único elemento, y dinámica porque se puede manejar la memoria de manera flexible sin necesidad de reservar espacio con antelación. Estas estructuras dinámicas lineales de datos conocidas como listas representan una colección de elementos, dispuestos uno a continuación de otro, cada uno de ellos conectado al siguiente por un “enlace” o “referencia”.

A su vez, con propósito de cumplir el objetivo principal del trabajo, se ampliará toda la información referente a listas, abarcando a detalle cada una de sus clasificaciones (Listas simplemente enlazadas, doblemente enlazadas, circulares simplemente enlazadas y circulares doblemente enlazadas) resaltando sus características y las operaciones básicas que pueden efectuarse sobre ellas, a fin de conocer su alcance e importancia en el desarrollo de algoritmos óptimos y eficientes.

ESTRUCTURAS DINÁMICAS DE DATOS

DEFINICIÓN DE ESTRUCTURA DINÁMICA DE DATOS

Se conoce como estructura de datos a la forma particular de organizar y manejar grandes cantidades de datos para que puedan ser utilizados de manera eficiente, siendo tratado como una unidad. A su vez, las estructuras de datos permiten modificaciones en el valor de sus elementos durante la ejecución de un programa, sin embargo, pueden diferenciarse entre estáticas y dinámicas dependiendo de la capacidad de modificar su estructura o tamaño durante el momento de ejecución. A propósito del presente trabajo se enfocará en las estructuras dinámicas de datos.

El autor Joyanes, L. (2008) define estructuras dinámicas de datos como:

Estructuras que «crecen a medida que se ejecuta un programa». Una estructura dinámica de datos es una colección de elementos —llamados nodos— que son normalmente registros. Al contrario que un array, que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa, basada en los registros de almacenamiento de datos del programa. (p. 430)

De este modo se puede señalar, que la característica distintiva de las estructuras dinámicas de datos reside en su capacidad de alterar su tamaño en medio de la ejecución del programa, ya sea para aumentarlo o disminuirlo de acuerdo a como lo amerite la situación, específicamente su característica se vincula con el ajuste de la cantidad de memoria destinada para la ejecución del programa, es decir, permitiendo que consuma memoria adicional de ser necesario o libere memoria para mejorar el rendimiento, esto sin la necesidad de reservar el espacio con antelación.

Dado a lo anteriormente descrito, este tipo de estructuras de datos son empleadas para almacenar datos del mundo real que estén en contante cambio, y por tanto, necesiten beneficios en el manejo de memoria.

CLASIFICACIÓN DE LAS ESTRUCTURAS DINÁMICAS DE DATOS

Las estructuras dinámicas de datos se pueden dividir en dos grandes grupos, según lo referencia Joyanes, L. (2008):

• Lineales: Se caracterizan por ser estructuras de representaciones contiguas o secuenciales, donde cada elemento predecesor tiene un único elemento sucesor. Entre ellas se encuentran: Las pilas, las colas y las listas.

• No Lineales: Estas estructuras también son denominadas como estructuras multienlazadas, se caracterizan por que cada elemento predecesor puede poseer diferentes elementos sucesores, dando a lugar a estructuras de bifurcación. Entre estas estructuras se encuentran: Los árboles y los grafos. 

Para términos del presente trabajo, se estudiará las estructuras dinámicas lineales de datos, exclusivamente en las estructuras dinámicas lineales de datos del tipo listas.

ESTRUCTURAS DINÁMICAS LINEALES DE DATOS: LISTAS

DEFINICIÓN DE LISTA LINEAL CONTIGUA.

Cuando se hace referencia al término lista se puede denotar como un conjunto finito de elementos que permiten representar una serie, entre los ejemplos de la vida cotidiana se puede encontrar: Listas de mercados, listas de cosas por hacer, listas de asistencia a un evento, entre muchos otros.

...