Listas enlazadas

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: