Teoría Listas Enlazadas

Sebastián Gómez JaramilloTecnológico de Antioquia

Definición básica

• Colección o secuencia de elementos• Dispuestos uno detrás de otro • Cada elemento se conecta al siguiente elemento por un

«enlace” o “referencia”

Nodo

Se compone de dos partes:1. La información: Valor de tipo genérico (Dato)2. Referencia: Apuntador o enlace al siguiente elemento.

Representación Lista

Se apunta al primer elemento de la lista, y cada elemento apunta al siguiente.El último elemento apunta a nulo.

Representación Lista

La lista simple se recorre siempre desde la cabeza hasta la cola. Una sola dirección

Generalidades

• Los datos pueden ser de cualquier tipo (Objeto, entero, carácter…)

• La lista es dinámica: Maneja eficientemente la memoria en el sistema. Crece o decrece según se agregan o eliminan elementos

Ejemplo

• En un paradero de buses, se conoce la información del primer bus.

• El segundo bus en la lista de espera, está después del primero. Siguiente al segundo, se ubica el tercero…

• El último bus no tiene ningún elemento posterior a él

Ejemplo

Si llega un nuevo bus a la lista:• El nuevo bus, ya ocuparía la posición de cola de la

lista.• El que era el último, apuntaría al nuevo último.• La lista crece automáticamente

Ejemplo

El nuevo bus puede ubicarse en cualquier posición de la lista. Desde la cabeza hasta la cola