View
3.525
Download
2
Category
Preview:
DESCRIPTION
Listas Enlazadas. Concepto. Representación gráfica de Listas. Clasificación de Listas enlazadas.
Citation preview
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.
Recommended