listas encadenadas jose tannous

7
LISTAS ENCADENADAS JOSÉ TANNOUS C.I. 21.126.003

Upload: jose-tannous

Post on 26-Jul-2015

82 views

Category:

Career


0 download

TRANSCRIPT

Page 1: Listas Encadenadas Jose Tannous

LISTAS ENCADENADASJOSÉ TANNOUS

C.I. 21.126.003

Page 2: Listas Encadenadas Jose Tannous

DEFINICIÓN

• Es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior.

• En listas encadenadas, los elementos consecutivos en la lista no significa que los mismos estén consecutivamente representados, en la implementación es necesario almacenar separadamente la información de un elemento de la lista, normalmente el primero.

• Existen dos formas representar listas encadenadas, a través de array, denominadas listas estáticas, o por punteros llamadas listas dinámicas.

Page 3: Listas Encadenadas Jose Tannous

VENTAJAS Y DESVENTAJAS

1. Elimina el problema de los traslados de nodos2. En el caso de listas dinámicas no se requiere saber previamente el número de elementos a ser almacenados.

1. No se consigue (de manera directa) el acceso a los elementos de la lista en tiempo constante.2. Mayor número de operaciones para mantener la integridad de los datos.

Page 4: Listas Encadenadas Jose Tannous

TIPOS DE LISTA ENCADENADA

• La lista encadenada básica es la lista simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo (o indica que tiene la dirección en memoria del siguiente nodo) en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Listas simples

• Un tipo de lista encadenada más sofisticado es la lista doble o lista encadenada de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Listas dobles

• En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin.

Listas circulares

Page 5: Listas Encadenadas Jose Tannous

ALGORITMO LISTAS ENCADENADAS SIMPLES (INSERTAR Y ELIMINAR)

Nuestra estructura de datos tendrá dos campos. Vamos a mantener la variables PrimerNodos que siempre apunta al primer nodo de tal lista, ó nulo para la lista vacía.

El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final.

Page 6: Listas Encadenadas Jose Tannous

El siguiente código inserta un elemento a continuación de otro en una lista simple. El diagrama muestra como funciona.

Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.

Page 7: Listas Encadenadas Jose Tannous

De forma similar, también tenemos funciones para borrar un nodo dado ó para borrar un nodo del principio de la lista

Advertimos que BorrarPrincipio pone PrimerNodo a nulo cuando se borra el último elemento de la lista. Adjuntar una lista enlazada a otra puede resultar ineficiente a menos que se guarde una referencia a la cola de la lista, porque si no tendríamos que recorrer la lista en orden hasta llegar a la cola y luego añadir la segunda lista.