• Author / Uploaded
• Willian Heredia

Citation preview

Nombre: Willian Pillaga Carrera: Ingeniería de Sistemas Paralelo: 7mo “A”

Listas Enlazadas Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un índice sino mediante un puntero. La asignación de memoria es hecha durante la ejecución. En una lista enlazada la memoria se va tomando según se necesita. Cuando queremos añadir un nuevo elemento reservamos memoria para él y lo añadimos a la lista. Cuando queremos eliminar el elemento simplemente lo sacamos de la lista y liberamos la memoria usada. Las listas enlazadas pueden ser simples, dobles o circulares En Ciencias de la Computación, 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 y/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. Una lista enlazada es un tipo de dato auto referenciado porque contienen un puntero o link a otro dato del mismo tipo. Características: 1.

Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante, pero no permiten un acceso aleatorio. 2. Existen diferentes tipos de listas enlazadas: Listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares. 3. Pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.

Tipos de Listas Listas Enlazadas Simples

Listas enlazadas simples Una lista enlazada simple es una colección de nodos que tienen una sola dirección y que en conjunto forman una estructura de datos lineal. Cada nodo es un objeto compuesto que guarda una referencia a un elemento (dato) y una referencia a otro nodo (dirección). La referencia que guarda un nodo a otro nodo se puede considerar un enlace o un puntero hacia el segundo nodo y el salto que los relaciona recibe el nombre de salto de enlace o salto de puntero. El primer nodo de una lista recibe el nombre de cabeza, cabecera o primero y el último es llamado final, cola o último (es el único nodo con la referencia a otro objeto como nula). Un nodo de una lista enlazada simple puede determinar quien se encuentra después de él pero no puede determinar quien se encuentra antes, ya que solo cuenta con la dirección del nodo siguiente pero no del anterior. Listas doblemente enlazadas Una lista enlazada doble es una colección de nodos que cuentan con dos direcciones en cada uno de sus nodos y que en conjunto forman una estructura de datos lineal. Cada nodo es un objeto compuesto que guarda una referencia a un elemento (dato), una referencia al nodo anterior (dirección predecesora) y una referencia al nodo siguiente (dirección sucesora). Un nodo de una lista enlazada doble puede determinar quien se encuentra después de él y quien se encuentra antes de él, ya que cuenta con las direcciones de los nodos siguiente y anterior.

Listas enlazadas circulares La lista circular es una especie de lista enlazada simple o doblemente enlazada, pero que posee una característica adicional para el desplazamiento dentro de la lista: esta no tiene fin. Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el primer elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples o doblemente enlazadas. En las listas circulares, nunca se llega a una posición en la que ya no sea posible desplazarse. Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento.

Listas enlazadas doblemente circulares. La lista circular doble es una especie de lista enlazada “doblemente enlazada”, pero que posee una característica adicional para el desplazamiento dentro de la lista, “ésta no tiene fin” y tiene 2 apuntadores a si misma.

Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el 1er elemento y el puntero anterior del primer elemento apuntara hacia el ultimo elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples o doblemente enlazadas.

En las listas circulares dobles, nunca se llega a una posición en la que ya no sea posible desplazarse. Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento.     

Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden. Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato. Buscar: busca un elemento en la lista. Localizar: obtiene la posición del nodo en la lista. Imprimir: imprime los elementos de la lista.

Usos: La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener. Se utilizan para organizar los datos, realizar búsquedas, almacenamiento de datos. Se aplica en todos aquellos casos en que se deba almacenar registros con informacion, pero no se sabe cuántos registros se usarán

Bibliografía: http://es.ccm.net/faq/2972-las-listas-circulares https://sites.google.com/site/estdatinfjiq/unidad-iii-listas-enlazadas http://galaxygun.blogspot.com/2008/11/conceptos-caractersticas-yejemplos-de.html http://uisraelonline.edu.ec/pluginfile.php/195195/mod_resource/content/1/Li stas_Est_Datos.pdf