Java

ESTRUCTURAS DE DATOS

LISTAS 93

TEMA 3

Listas.
3.1. CONCEPTOS GENERALES.
Una lista es una estructura de datos lineal que se puede representar simbólicamente
como un conjunto de nodos enlazados entre sí.
Las listas permiten modelar diversas entidades del mundo real como por ejemplo, los
datos de los alumnos de un grupo académico, los datos del personal de una empresa, los
programasinformáticos almacenados en un disco magnético, etc.
La figura 3.1 muestra un ejemplo de lista correspondiente a los nombres y apellidos
de un conjunto de alumnos con su código de matrícula.
Arias González, Felipe

aa1253
García Sacedón, Manuel

ax0074

López Medina, Margarita

Ramírez Heredia, Jorge

Yuste Peláez, Juan

lp1523

gb1305

Figura 3.1. Ejemplo de Lista

mj772694 LISTAS

ESTRUCTURAS DE DATOS

Tal vez resulte conveniente identificar a los diferentes elementos de la lista (que
normalmente estarán configurados como una estructura de registro) mediante uno de sus
campos (clave) y en su caso, se almacenará la lista respetando un criterio de ordenación
(ascendente o descendente) respecto al campo clave.
Una definición formal de lista es la siguiente:“Una lista es una secuencia de elementos del mismo tipo, de cada uno de los cuales
se puede decir cuál es su siguiente (en caso de existir).”
Existen dos criterios generales de calificación de listas:
Por la forma de acceder a sus elementos.
o Listas densas. Cuando la estructura que contiene la lista es la que determina la
posición del siguiente elemento. La localización de un elemento dela lista es la
siguiente:
 Está en la posición 1 si no existe elemento anterior.
 Está en la posición N si la localización del elemento anterior es (N-1).
o Listas enlazadas: La localización de un elemento es:
 Estará en la dirección k, si es el primer elemento, siendo k conocido.
 Si no es el primer elemento de la lista, estará en una dirección, j, que está
contenida en el elementoanterior.
Por la información utilizada para acceder a sus elementos:
o Listas ordinales. La posición de los elementos en la estructura la determina su orden
de llegada.
o Listas calificadas. Se accede a un elemento por un valor que coincide con el de un
determinado campo, conocido como clave. Este tipo de listas se pueden clasificar a
su vez en ordenadas o no ordenadas por el campo clave.ESTRUCTURAS DE DATOS

LISTAS 95

3.2. IMPLEMENTACIÓN DE LISTAS.
El concepto de lista puede implementarse en soportes informáticos de diferentes
maneras.
Mediante estructuras estáticas. Con toda seguridad resulta el mecanismo más intuitivo.
Una simple matriz resuelve la idea (figura 3.2).
0
1
2
3
4

Arias González, Felipe
García Sacedón, Manuel
López Medina, Margarita
RamírezHeredia, Jorge
Yuste Peláez, Juan

aa1253
ax0074
mj7726
lp1523
gb1305

Figura 3.2. Implementación de una lista densa mediante una estructura estática
(matriz).
El problema de esta alternativa es el derivado de las operaciones de inserción y
modificación.
En efecto, la declaración de una lista mediante una matriz implica conocer de
antemano el número (o al menos el orden de magnitud) deelementos que va a
almacenar, pudiendo darse las circunstancias de que si se declara pequeño podría
desbordarse su capacidad o, en caso contrario, declararlo desproporcionadamente
elevado provocaría un decremento de eficiencia.
Otro problema asociado es el tratamiento de los elementos eliminados. Dado que
en el caso de no informar, de alguna manera, de la inexistencia de dicho elemento el
nodopreviamente ocupado (y ahora no válido) quedaría como no disponible.
Adicionalmente, si se desea trabajar con listas ordenadas el algorit mo de
inserción debería alojar a los nuevos elementos en la posición o con la referencia
adecuada.
Algunas soluciones, más o menos ingeniosas, permiten tratar estas
circunstancias. La figura 3.3 muestra un ejemplo basado en una matriz de registros.
01...