1
LISTAS ENLAZADAS
1.1. LISTAS ENLAZADAS
El concepto matemático es el de lista de elementos de
un conjunto L.
1.1.1. DEFINICIONES:
a) Una lista L es una secuencia de cero o
más elementos de L:
a1, a2, ...., an
b) Si n=0, L no tiene elementos y será
llamada la lista nula o vacía.
c) Si n>=1, L tiene n elementos y diremos
que su longitud es n.
d) a1 es el primer elemento de L y an es el
último elemento de L.
e) Para i= 1, 2, ... , n-1, ai precede a ai+1
f) Para i= 2, 3, … , n, ai sigue a ai-1
g) El orden en la secuencia determina la
posición de cada elemento si es que es
una lista ordenada.
1.1.2. OPERACIONES BÁSICAS CON UNA LISTA
Suponemos que L es una lista y a continuación
se dan algunas operaciones sobre listas.
anular() convierte a L en la lista vacía o nula.
primero() devuelve el valor del primer elemento de la lista L, si esta es no vacía.
ultimo() devuelve el valor del ultimo elemento de la lista L, si esta es no vacía.
localizar(x) retorna la posición del primer elemento de L que es igual a x o devuelve nulo si tal elemento no existe.
suprimir(x) elimina el elemento x de la lista L.
insertarAlInicio(x) inserta x al inicio en la lista L.
insertarAlFinal(x) inserta x al final en la lista L.
eliminarAlInicio() elimina el primer elemento de la lista L.
eliminarAlFinal() suprime el último elemento de la lista L.
insertar(x) inserta x en la lista L en forma ordenada
2
ascendente si es una lista ordenada.
mostrar() Muestra los elementos de la lista
1.2. IMPLEMENTACIÓN DE LISTAS USANDO
REFERENCIAS A OBJETOS
Ahora definimos el concepto de estructuras dinámicas
de datos. Mediante este método, los elementos de una
lista se "enlazan" usando referencias, dando lugar a
la estructura de datos llamada lista enlazada. Es
decir, las variables pueden crearse y destruirse
durante la ejecución del programa. Dependiendo de como
se enlazan los elementos de una lista, ésta será:
1.3. LISTA LINEAL SIMPLEMENTE ENLAZADA
La lista lineal simplemente enlazada tiene la
siguiente disposición:
L Nulo
Donde la clase de un nodo es:
Información
Tipo de datos que
se quiere almacenar
en la lista.
Una referencia que se utiliza para
establecer el enlace con el otro nodo de la
lista.
L es un puntero al inicio de la lista (referencia al
primer elemento de la lista) y cada flecha representa
una referencia; además nulo representa el fin de la
lista. La lista enlazada completa se accede desde el
apuntador externo L. La clase en Java puede ser: