Listas enlazadas

CONCEPTO DE LISTA ENLAZADA.

Una lista enlazada 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 (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

TIPOS DE LISTAS.

Listas enlazadas lineales

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo



Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas 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.

Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior

Inserción por la cabeza de lista enlazada

1. Crear un nuevo nodo.

2. Almacenar el dato en el campo correspondiente (datos).

3. Como va a ser el primer nodo, su enlace deberá apuntar al que hasta ahora era el primer nodo

(apuntado por el enlace externo).

4. El elnace externo deberá apuntar al nuevo nodo (que ahora es el primero)

Inserción por el final de lista enlazada

Para insertar por el final, se debe llegar hasta el último nodo de la lista. Para ello, y partiendo del enlace

externo, se saltará de nodo a nodo (a través del campo enlace), hasta alcanzar un nodo cuyo enlace sea

nulo (NIL). En ese momento, el campo enlace se cambiará por el enlace hacia el nuevo nodo (recordar que

al crear un nuevo nodo, por defecto, su enlace debe estar siempre a NIL).

Suprimir por la cabeza de lista enlazada

1. Almacenar la dirección del primer elemento apuntado por el enlace externo en una variable puntero

temporal.

2. Se asigna al enlace externo el elemento que figura en el enlace del primer elemento.

3. Se elimina el nodo apuntado por el puntero auxiliar.

Suprimir por el final de lista enlzada

En este caso se procederá del mismo modo que en la inserción por el final pero con una variable puntero

auxiliar se irá guardando la dirección del nodo anterior. Al alcanzar el nodo con enlace=NIL, se borrará y al

nodo anterior apuntado por el puntero auxiliar, se modificará su enlace a NIL..

OPERACION CON LISTAS CIRCULARES

Inserción de un elemento en la lista

A continuación el algoritmo de inserción y registro de los elementos:

• declaración del elemento a insertar
• asignación de la memoria para el nuevo elemento
• rellenar el contenido del campo de datos
• actualizar los punteros hacia el 1er y ultimo elemento si es necesario.
• Caso particular: en una lista con un solo elemento, el 1er elemento es al mismo tiempo el ultimo.
• Actualizar el tamaño de la lista.

Eliminación de un elemento en la lista

A continuación el algoritmo de eliminación de un elemento de la lista:

• uso de un puntero temporal para guardar la dirección de los elementos a eliminar
• el elemento a eliminar se encuentra después del elemento actual

Hacer apuntar el puntero siguiente del elemento actual hacia la dirección del puntero siguiente del elemento a eliminar

• liberar la memoria ocupada por el elemento eliminado
• actualizar el tamaño de la lista

Para eliminar un elemento de la lista hay varias situaciones:

• 1. Eliminación dentro de la lista
• 2. Eliminación del último elemento de la lista

Mostrar la lista

Para mostrar la lista completa, es necesario posicionarse al inicio de la lista (el puntero inicio lo permitirá). Luego, utilizando el puntero siguiente de cada elemento, la lista es recorrida del 1er al ultimo elemento.
En comparación con las listas simples y doblemente enlazadas, en el que la condición para detenerse esta dada por el puntero siguiente del ultimo elemento, que vale NULL, para la lista circular, no hay punto de detención, a menos que elijamos uno.

A continuación dos variantes de visualización:

• Mostrar la lista (del 1er al último elemento)
• Mostrar la lista sin una condición para detenerse.

Listas enlazadas circulares

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. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Listas enlazadas circulares simples

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. 1

Lista Enlazada Doblemente Circular

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo

apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

OPERACIONES CON LISTAS ENLAZADAS