Algoritmo y Estructura De Datos Listas

Algoritmo y Estructura de Datos II
MATERIAL DEL DOCENTE
(2010-II)

SEMANA 03 a SEMANA 06
LISTAS ENLAZADAS SIMPLES
Ing. Juan José Flores Cueto
Sr. Juan José Rodriguez Vila

LISTAS ENLAZADAS SIMPLES

INTRODUCCIÓN

Un algoritmo constituye una lista completa de pasos secuenciales y una descripción de datos necesarios para resolver un determinado problema. Dichos datos deben almacenarseen una estructura de datos.

Un arreglo permite almacenar varios valores a la vez todos del mismo tipo y constituyen las estructuras de datos más sencillas después de la variable. Cuando se utilizan múltiples arreglos en las soluciones podemos manejar los datos almacenados utilizando un algoritmo de búsqueda, clasificación, modificación y eliminación con la finalidad de mantener actualizados losdatos.

DEFINICIÓN

Una lista simple es una estructura de datos lineal dinámica que está compuesta por un conjunto de elementos que permiten almacenar diferentes tipos de datos.

REPRESENTACIÓN

La forma de representar cada elemento de una lista se puede reflejar a través de un rectángulo dividido en dos partes: la parte superior representa la zona donde se almacenan los datos y la parteinferior, la zona utilizada para enlazar al siguiente elemento de la lista.

Así, cada elemento de una lista puede ser representado de la siguiente manera:

Representación de un elemento o nodo de una lista

Zona de enlace:

Permite indicar cuál es el siguiente elemento de la lista.
Zona de datos:

Permite almacenar los datos de cada elemento de la lista.

Esto nos permite representaruna lista como un conjunto de elementos enlazados entre sí. Observe en el siguiente ejemplo la manera en la que se representa una lista con los nombres de los alumnos de un salón de clase:

Listado de nombres de alumnos de un salón de clase

Rodrigo
sig
Danae
sig
Carmen
sig
José
sig
Diego
sig

Nota: Esta lista almacena los nombres de 5 alumnos de un salón de clase.

Para podercodificar en un lenguaje de programación este tipo de estructura de datos, es importante especificar explícitamente cual de todos los elementos será el primero de la lista, cómo se determinará y cuál será el siguiente elemento. En el lenguaje de programación Java esto se logra utilizando “referencia de objetos”.

Una referencia de objetos se refiere a la dirección de memoria que se encuentradestinada al almacenamiento de un objeto, desde el punto de vista de programación, es la forma en que se pueden almacenar diversos tipos de datos en un conjunto de direcciones de memoria.

Siguiendo los criterios expuestos en el párrafo anterior, podemos extender la representación de una lista para poder facilitar su posterior codificación en el lenguaje de programación Java, tal y como se muestra acontinuación:

Listado de nombres de alumnos de un salón de clase

null
cab
Carmen
sig
Danae
sig
Rodrigo
sig
Diego
sig
José
sig

sig

Donde:
* cab (abreviatura de cabecera) es una “referencia de objetos” que nos indica el primer elemento de la lista.
* sig (abreviatura de siguiente) es una “referencia de objetos” que nos indica el siguiente elemento de la lista.* nombre es una variable de tipo TEXTO o CADENA que permite almacenar el nombre de un alumno.

Nota: Es importante mencionar que el elemento cuya referencia sig es “null”, es el último elemento en la lista.

IDENTIFICACIÓN DE CLASES

Teniendo como base la representación de una lista, podemos identificar las clases que serían necesarias para desarrollar soluciones en el lenguaje deprogramación Java que permitan implementar este tipo de estructura de datos. Para el ejemplo planteado anteriormente, las clases serían:

* Una clase que podríamos denominar Elemento que especificaría los datos comunes que tienen todos los elementos de la lista y a partir de la cual podríamos crear objetos de tipo elemento de lista. Los atributos de esta clase serían:
* Los datos de cada...