Listas EnlazadasIng. Vanessa Borjas

Listas Enlazada Es una colección o secuencia de elementos

dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un “enlace” o “puntero”.

La idea básica consiste en construir una lista cuyos elementos llamados “nodos” se componen de dos partes o “campos”: la primera parte o campo contiene la información y es, por consiguiente, un valor de un tipo genérico (denominado Dato, TipoElemento, Info, etc.) y la segunda parte o campo es un puntero (denominado enlace o siguiente) que apunta al siguiente elemento de la lista.

Lista enlazada (representación simple)

NODO NODO NODOPuntero Puntero

e1 e2 e3

en

…..

…..

Una lista enlazada consta de un número de elementos y cada elemento tiene dos componentes (campos), un puntero al siguiente elemento de la lista y un valor, que puede ser de cualquier tipo.

Los enlaces se representan por flechas para facilitar la comprensión de la conexión entre dos nodos; ello indica que el enlace tiene la dirección en memoria del siguiente nodo. Los enlaces también sitúan los nodos en una secuencia.

El primer nodo se enlaza al segundo, el segundo nodo se enlaza al tercero y así sucesivamente hasta llegar al último nodo.

El último nodo ha de ser representado de forma diferente para significar que este nodo no se enlaza a ningún otro.

Diferentes representaciones gráficas del nodo “último”

e

NULL

Clasificación de las Listas Enlazadas LISTAS SIMPLEMENTE ENLAZADAS

Cada nodo (elemento) contiene un único enlace que conecta ese nodo al nodo siguiente o nodo sucesor. Es eficiente en recorridos directos (“hacia adelante”).

e1 e2 e3

LISTAS DOBLEMENTE ENLAZADAS Cada nodo contiene dos enlaces, uno a s

nodo predecesor y el otro a su nodo sucesor. Es eficiente tanto en recorrido directo (“adelante”) como en recorrido inverso (“atrás”)

Clasificación de las Listas Enlazadas

e1 e2 e3

LISTA CIRCULAR SIMPLEMENTE ENLAZADA Es una lista enlazada simplemente en la

que el último elemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser recorrida de un modo circular (“en anillo”).

Clasificación de las Listas Enlazadas

e1 e2 e3

LISTA CIRCULAR DOBLEMENTE ENLAZADA Es una lista doblemente enlazada en la

que el último elemento se enlaza al primer elemento y viceversa. Se puede recorrer de modo circular (“en anillo”) tanto en dirección directa (“adelante”) como inversa (“atrás”).

Clasificación de las Listas Enlazadas

e1 e2 e3

Dato Sgte. Dato Sgte

. Dato Sgte.

Dato

Cabeza…..

…..

Ptr_actual

Cola

El primer nodo, frente, es el nodo apuntado por Cabeza. La lista encadena nodos juntos

desde el frente hasta el final (Cola) de la lista. El final se identifica como el nodo cuyo campo

puntero tiene el valor NULL = 0. La lista se recorre desde el primero al Último nodo; en

cualquier punto del recorrido, la posición actual se referencia por el puntero Ptr_actual. En el caso de que la lista no contenga ningún nodo (está vacía), el puntero Cabeza es Nulo.

Operaciones en Listas Enlazadas Declaración de los tipos nodo y puntero a

nodo. Inicialización o creación. Insertar elementos en una lista. Eliminar elementos de una lista. Buscar elementos de una lista (comprobar la

existencia de elementos en una lista). Recorrer una lista enlazada (visitar cada nodo

de la lista). Comprobar si la lista está vacía.