Estructuras de datos Lineales/ Listas enlazadas

Listas Enlazadas 

 

Las listas al igual que las pilas y las colas, son una estructura de datos de tipo lineal  diferenciándose de las anteriores en el hecho de que pueden las  inserciones y eliminaciones se  en cualquier parte de la lista. Esto hace que tengan mayor aplicabilidad en el entorno real. Se abordan los temas relacionados con los conceptos básicos de las listas, así como tipos de listas y  las operaciones que se pueden realizar con las listas, todo conjugado en programas de aplicación, implementados con apuntadores. Es importante tener en cuenta que una estructura de datos lineal pueden representarse en memoria ya sea a través de arreglos  o a través de listas enlazadas implementadas haciendo uso de los apuntadores y por ende con la gestión de memoria dinámica que se asigna en tiempo de ejecución.

Concepto básicos de Listas

Una lista puede considerarse como una colección o secuencia de elementos del mismo tipo que van en una posición uno de tras del otro,  a este tipo de lista se le conoce como lista continua,  esta es una definición general, que incluye los ficheros y vectores.

 Las entradas de una guía o directorio telefónico, por ejemplo, están en líneas sucesivas, excepto en las partes superior e inferior de cada columna.  Una lista lineal se almacena en la memoria principal de una computadora en posiciones sucesivas de memoria;  en el caso cuando se almacenan en cinta magnética, los elementos sucesivos se presentan en sucesión en la cinta.  Esta asignación de memoria se denomina almacenamiento secuencial.

Una lista lineal se almacena en la memoria de la computadora en posiciones sucesivas o adyacentes y se procesa como un arreglo unidimensional. En este caso, el acceso a cualquier elemento de la lista es fácil; sin embargo, la inserción o borrado requiere un desplazamiento de lugar de los elementos que le siguen y en consecuencia el diseño de un algoritmo específico.

Para permitir operaciones con las listas como arreglos se deben dimensionar éstos con tamaño suficiente para que contengan todos los posibles elementos de la lista.

La inserción o eliminación de un elemento, excepto en la cabecera o final de la lista, necesita una traslación de un parte de los elementos de la misma: la que precede o sigue a la posición del elemento modificado.

Las operaciones directas de añadir y eliminar se efectúan únicamente en los extremos de la lista.  Esta limitación es una de las razones por las que esta estructura  de lista continua es poco utilizada.

 

Veamos una representación gráfica de una lista continua.

Imagen 1. Representación gráfica de una lista contigua

Como se puede apreciar en la figura 1, se trata de una lista contigua de elementos de tipo entero representados en un arreglo unidimensional de 6 campos, de tal manera que no es posible insertar un nuevo elemento por que la lista está completa, esta es una de las desventajas de este tipo de lista.

Posteriormente, se verá que existe otro tipo de almacenamiento denominado encadenado o enlazado. Naciendo así el concepto de las listas enlazadas, veamos en que consiste.

Listas enlazadas:  es una colección o secuencia de elementos del mismo tipo dispuestos uno detrás de otro, en el que cada elemento se liga al siguiente elemento por un enlace que no es más que un puntero previamente definido dentro de los miembros de la estructura .

 Las listas según su estructura se han dividido en cuatro grandes categorías:

• Listas Simplemente enlazadas
• Listas Doblemente enlazadas
• Listas Circular simplemente enlazada
• Lista circular doblemente enlazada

Las listas enlazadas o de almacenamiento enlazado son mucho más flexibles y potentes, su uso es mucho más amplio comparado con la lista contigua.

 Una lista enlazada o encadenada es un conjunto de elementos del mismo tipo en los que cada elemento contiene la posición o dirección del siguiente elemento de la lista.  Cada elemento de la lista enlazada debe tener al menos dos campos: un campo que tiene el valor del elemento y un campo (enlace o liga) que contiene la posición del siguiente elemento, es decir, su conexión, enlace o encadenamiento.  Los elementos de una lista son enlazados por medio de los campos enlaces.

Una lista enlazada sin ningún elemento se llama lista vacía.  Su puntero inicial o de cabecera tiene el valor nulo, es decir apunta a NULL.

 *puntero ->NULL;   haciendo uso de la sintaxis de C++ puede expresarse como:  *puntero=NULL;

 

Imagen 2. Representación gráfica de las listas enlazadas

 

 

 

Operaciones con las listas enlazadas

Generalmente las operaciones básicas que se pueden realizar en una lista enlazada son las siguientes:

Operación de Inserción. Esta operación consiste en agregar un nuevo elemento a la lista. Se pueden considerar tres casos especiales:

• Insertar un elemento al inicio de la lista.
• Insertar un elemento antes o después de un determinado elemento o nodo de la lista.
• Insertar un elemento al final de la lista.

Operación de Visualización. Esta operación consiste en mostrar o visualizar los elementos de la lista que han sido insertados o almacenados previamente en la estructura, para lo cual se hace el recorrido para ir mostrando en pantalla cada elemento de la lista iniciando desde la cabeza hasta llegar al ultimo nodo,  es decir,cuando el nodo siguiente es igual a NULL.

Operación de Recorrido. Esta operación consiste en visitar cada uno de los elementos que forman la lista. Para ello se comienza con el primer elemento, se toma el valor del campo enlace para avanzar al segundo elemento, el campo enlace de este elemento dará la dirección del tercer elemento y así sucesivamente hasta que la información del campo enlace sea NULL, lo que indica que el recorrido llegó a su final.

Operación de Búsqueda. Esta operación consiste en buscar un determinado elemento en la lista, que es solicitado por el usuario en tiempo de ejecución, se procede a  hacer la comparación entre el elemento a buscar con  cada uno de los elementos previamente ingresados a la lista , el recorrido se hace  tomando al campo enlace como puntero al siguiente elemento a visitar en la lista, una vez se encuentre el elemento se procede a mostrarlo en pantalla.

Operación de Borrado. La operación de borrado consiste en eliminar  un elemento de la lista, se pueden presentar cuatro casos básicos:

• Eliminar el primer elemento de la lista.
• Eliminar el último elemento de la lista.
• Eliminar de la lista un elemento específico, es decir, que tenga cierta información independientemente de su ubicación.

Implementación de una lista enlazada con punteros

El siguiente programa se plantea como ejemplo guía para implementar una lista simplemente enlazada con punteros, para gestionar números enteros, ingresados por teclado con funciones de insertar, eliminar, recorrer y buscar.

Las eliminaciones se realizan en cualquier lugar de la lista.

 Programa  Lista.cpp

 

El resultado dela salida en pantalla del listado anterior se puede observar en la siguiente imagen.

Imagen 4. Salida en pantalla del programa Lista.Cpp

Analice el código y plantee modificaciones al programa, en busca de mejoras, una de ellas puede ser implementar el programa a través de un menú de opciones con funciones que respondan a cada opción, de Insertar, visualizar, buscar y eliminar.