PDF de programación - Tema 3 - Listas

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
programas informá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

mj7726

Ramírez Heredia, Jorge

lp1523

Yuste Peláez, Juan

gb1305

Figura 3.1. Ejemplo de Lista

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 de la 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 elemento anterior.

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 Arias González, Felipe
aa1253
1 García Sacedón, Manuel ax0074
2

López Medina, Margarita mj7726

3 Ramírez Heredia, Jorge
4 Yuste Peláez, Juan

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) de elementos 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
nodo previamente ocupado (y ahora no válido) quedaría como no disponible.

Adicionalmente, si se desea trabajar con listas ordenadas el algoritmo 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.



0 1

2

3

4

5

6

7

8

1 10 77 12 26 21 11 13 18

2 3 4 7 6 0 8 5 0

Figura 3.3. Ejemplo de implementación de lista enlazada mediante una estructura

Otra posible representación de esta lista sería la siguiente:

estática (matriz).

96 LISTAS



ESTRUCTURAS DE DATOS

10

12

13

21

Figura 3.4. Lista enlazada correspondiente a la figura 3.3.

El tratamiento de las listas sobre matriz (tanto densas como enlazadas) se desarrollará

más adelante, en el apartado 3.8.

Mediante estructuras dinámicas.

Sin duda se trata de la mejor alternativa para la construcción de listas. Se trata de

hacer uso de la correspondiente tecnología que implica el uso de referencias.

La idea consiste en declarar una referencia a un nodo que será el primero de la lista.
Cada nodo de la lista (en la memoria dinámica) contendrá tanto la propia información del
mismo como una referencia al nodo siguiente. Se deberá establecer un convenio para
identificar el final de la lista1.

La figura 3.5 muestra un ejemplo de implementación dinámica de la lista de la figura

3.4.



Lista



Memoria estática

10

Memoria dinámica

21
1

*

12

13

Figura 3.5. Implementación de una lista mediante estructuras dinámicas.

Lo explicado hasta el momento consiste en la solución más sencilla: cada nodo de la
lista “apunta” al siguiente, con las excepciones del último elemento de la lista (su
“apuntador, o “referencia” es un valor especial, por ejemplo null, en java) y del primero,
que es “apuntado” por la referencia declarada en la memoria estática. Esta tecnología se
identifica como “Listas enlazadas o unidireccionales”. Existen otras posibilidades entre las
que cabe mencionar: listas bidireccionales o doblemente enlazadas, listas circulares, listas
con cabecera, listas con centinela o cualquier combinación de ellas.



1 En java la referencia final tomará el valor null.

ESTRUCTURAS DE DATOS



LISTAS 97

3.3. TRATAMIENTO DE LISTAS EN JAVA

Para la utilización de listas es necesario definir la clase NodoLista utilizando la

siguiente sintaxis:

class NodoLista {

public int clave;

public NodoLista sig;

public NodoLista(int x, NodoLista n) {

clave = x;

sig = n;

}

}



Así como la clase Lista:

public class Lista {

public Lista (String nombreLista) {

inicio = null;

nombre = nombreLista;

}

public NodoLista inicio;

public String nombre;

}



La representación gráfica de una variable de la clase Lista llamada lista1 que

contenga los elementos 10, 13 y 21 sería:



lista1
Variable
estática



“lista1”



nombre

inicio

Clase Lista



10



dato

sig

NodoLista



13



dato

sig

NodoLista



21 null

dato

sig

NodoLista

Figura 3.6. Ejemplo de lista enlazada.

98 LISTAS



ESTRUCTURAS DE DATOS

3.4. ALGORITMOS BÁSICOS CON LISTAS2.

Los algoritmos que implican el recorrido, parcial o total, de la lista pueden

implementarse tanto de forma recursiva como iterativa.

3.4.1. Recorrido completo.

El recorrido de una lista de manera recursiva se puede realizar por medio de un
método static invocado desde un programa que utilice la clase Lista. Esto implica utilizar el
tipo NodoLista para avanzar por la lista y ver el contenido del campo clave. Merecen una
consideración especial:

La llamada inicial donde lista es el valor de la variable estática.

El final del recorrido, que se alcanza cuando la lista está vacía.

En el siguiente método estático (escribirLista), se recorre una lista (nodoLista)
mostrando en la pantalla el contenido de sus campos clave. Se utiliza un método de llamada
(escribirListaCompleta), que recibe como argumento un objeto de la clase Lista (lista):

static void escribirLista (NodoLista nodolista) {



if (nodoLista != null) {

System.out.print (nodoLista.clave + " ");

escribirLista (nodoLista.sig);

}

else System.out.println (" FIN");

}

static void escribirListaCompleta (Lista lista) {



if (lista != null) {

System.out.print (lista.nombre + “: “);

escribirLista (lista.inicio);

}

else System.out.println ("Lista vacía);

}



Si se aplica el algoritmo anterior a la lista de la figura 3.6, el resultado sería la

secuencia:

lista1: 10 13 21 FIN.

La ejecución de escribirListaCompleta implicaría una llamada inicial al método
escribirLista, pasando como argumento lista.inicio (la referencia al nodo de clave 10) y 3
llamadas recursivas al método escribirLista:



2 Los siguientes algoritmos se han desarrollado considerando implementaciones de la lista como estructuras
dinámicas. A efectos de la realización de prácticas se utiliza la sintaxis del lenguaje java.

ESTRUCTURAS DE DATOS



LISTAS 99

En la primera llamada recursiva, nodoLista es el contenido del campo sig del nodo de

clave 10. Es decir, una referencia al nodo de clave 13.

En la segunda, nodoLista es el contenido del campo sig del nodo de clave 13. Es decir,

una referencia al nodo de clave 21.

En la tercera, nodoLista es el contenido del campo sig del nodo de clave 21, es decir,
null. Cuando se ejecuta esta tercera llamada se cumple la condición de finalización y, en
consecuencia, se inicia el proceso de “vuelta”. Ahora nodoLista toma sucesivamente los
valores:

o Referencia al nodo de clave 21