listas

11. LISTAS
Conceptos: Lista, lista dinámica simple, lista circular, lista doblemente enlazada, pila, cola
Resumen: Este capítulo se centra en la estructura lineal de tipo dinámico más general,
estudiándose tanto su descripción (que se basará en el concepto de puntero)
como las principales a realizar sobre ella. Se define una lista como una colección
de elementos del mismo tipo entre los queexiste una relación de orden
determinada por la posición de dicho elemento. Cada uno de estos elementos
consta de un campo que almacena la información contenida en el nodo.
Dependiendo del tipo de lista que se trate, cada elemento tendrá, además uno o
dos campos de tipo puntero que apuntarán a otros elementos de la lista. Así, en el
caso de las listas dinámicas simplemente enlazadas existe unúnico puntero que
apunta al siguiente elemento de la lista. En las listas doblemente enlazadas existe
otro puntero adicional que apunta al elemento anterior de la lista. Las listas
circulares tienen la propiedad de que su último enlaza con el primero de forma
que se facilita el acceso a todos los elementos de la lista desde cualquiera de
ellos. Los algoritmos considerados para cada una deestas estructuras de datos
son los de creación de una lista vacía, recorrido, búsqueda de información e
inserción y borrado de elementos, que se apoyarán en los recursos básicos de
reserva y liberación dinámica de memoria.
Objetivos específicos. Al finalizar el tema, el alumno deberá ser capaz de:
a) Definir el concepto de lista (Conocimiento)
b) Escribir la declaración de tipos puntero y devariables de variables necesarios para poder
trabajar una estructura de tipo lista dinámica (Comprensión)
c) Interpretar el código fuente de un programa que trabaje con una estructura de datos de
tipo lista (Comprensión)
d) Codificar una tarea sencilla convenientemente especificada, utilizando una estructura de
datos de tipo lista (Aplicación)
Fundamentos de programación - A. García-Beltrán,R. Martínez y J.A. Jaén 142
11.1. INTRODUCCIÓN
Matemáticamente, una lista es una sucesión finita de cero, uno o más elementos del
mismo tipo. Desde el punto de vista de las estructuras de datos, una lista es un conjunto finito de
elementos, en el que para acceder a uno de ellos hay que pasar por todos los situados antes que
él. Una lista es, por lo tanto, una estructura de datos secuencial.Ejemplos de listas utilizadas
cotidianamente pueden ser: la lista de personas en la cola para visitar a un médico, la secuencia
de pasos de una receta de cocina, la lista de jugadores de un equipo de fútbol,...
Para Aho, las listas son estructuras de datos particularmente flexibles ya que pueden ir
creciendo o decreciendo según se necesite y pueden accederse, insertarse o eliminarse elementosen cualquier posición dentro de la lista.
En un programa se puede trabajar con una lista de datos a través de una variable de tipo
array, es decir, una estructura de datos estática, pero es preferible implementar la lista
mediante una estructura de datos dinámica para aprovechar y emplear de una forma más flexible
y óptima la memoria.
Como ya se adelantó en el capítulo anterior, para llevaresto a cabo hay que utilizar
variables de tipo apuntador o puntero. En este capítulo se tratará el tema de las listas no a nivel
teórico, sino fundamentalmente, desde el punto de vista de su implementación como una
estructura de datos dinámica dentro de un programa.
11.2. GENERACIÓN DE UNA LISTA DINÁMICA
Para construir una lista dinámica de datos se han de definir los elementos de la listacomo datos de tipo record con dos clases de campos: una serie de campos que almacenan
información y otra serie de campos de tipo apuntador o puntero. Al menos se necesita uno de
estos campos para que almacene la posición de memoria del siguiente elemento de la lista. Por
lo tanto, los campos puntero de los elementos de las listas utilizados en general en los programas
almacenarán direcciones...