Lista Enlazadas

Lista Enlazadas

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 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. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.

Las listas enlazadas 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.

•

Historia

Las listas enlazadas fueron desarrolladas en 1955-56 por Cliff Shaw y Herbert Simon en RAND Corporation como la principal estructura de datos para su Lenguaje de Procesamiento de la Información (IPL). IPL fue usado por los autores para desarrollar varios programas relacionados con la inteligencia artificial, incluida la Máquina de la Teoría General, el Solucionador de Problemas Generales, y un programa informático de ajedrez. Se publicó en IRE TransactionsonInformationTheory en 1956, y en distintas conferencias entre 1957-1959, incluida Proceedings of the Western JointComputer en 1957 y 1958, y en InformationProcessing (Procendents de la primera conferencia internacional del procesamiento de la información de la Unesco) en 1959. El diagrama clásico actual, que consiste en bloques que representan nodos de la lista con flechas apuntando a los sucesivos nodos de la lista, apareció en ProgrammingtheLogicTheory Machine, de Newell y Shaw. Newell y Simon fueron reconocidos por el ACM TuringAward en 1975 por “hacer contribuciones básicas a la inteligencia artificial, a la psicología del conocimiento humano y al procesamiento de las listas”.

El problema de los traductores del procesamiento natural del lenguaje condujo a VictorYngve del Instituto Tecnológico de Massachusetts (MIT) a usar listas enlazadas como estructura de datos en su COMIT, lenguaje de programación para computadoras, que investigó en el campo de la Lingüística computacional. Un informe de este lenguaje, titulado “A programminglanguageformechanicaltranslation” apareció en MechanicalTranslation en 1958.

LISP, el principal procesador de listas, fue creado en 1958. Una de las mayores estructuras de datos de LISP es la lista enlazada.

En torno a los 60, la utilidad de las listas enlazadas y los lenguajes que utilizaban estas estructuras como su principal representación de datos estaba bien establecida. Bert Green del MITLincoln Laboratory, publicó un estudio titulado Computerlanguagesfor symbol manipulation en IRE Transactionon Human Factors in Electronics en marzo de 1961 que resumía las ventajas de las listas enlazadas. Un posterior artículo, A Comparison of list-processing computer languages by Bobrow and Raphael, aparecía en Communications of the ACM en abril de 1964.

Muchos sistemas operativos desarrollados por TechnicalSystemsConsultants (originalmente de West Lafayette Indiana y después de Raleigh, Carolina del Norte) usaron listas enlazadas simples como estructuras de ficheros. Un directorio de entrada apuntaba al primer sector de un fichero y daba como resultado porciones de la localización del fichero mediante punteros. Los sistemas que utilizaban esta técnica incluían Flex (para el Motorola 6800 CPU), mini-Flex (la misma CPU) y Flex9 (para el Motorola 6809 CPU). Una variante desarrollada por TSC se comercializó a SmokeSignalBroadcasting en California, usando listas doblemente enlazadas del mismo modo.

El sistema operativo TSS, desarrollado por IBM para las máquinas System 360/370, usaba una lista doblemente enlazada para su catálogo de ficheros de sistema. La estructura del directorio era similar a Unix, donde un directorio podía contener ficheros u otros directorios que se podían extender a cualquier profundidad. Una utilidad fue creada para arreglar problemas del sistema después de un fallo desde las porciones modificadas del catálogo de ficheros que estaban a veces en memoria cuando ocurría el fallo. Los problemas eran detectados por comparación de los links posterior y anterior por consistencia. Si el siguiente link era corrupto y el anterior enlace del nodo infectado era encontrado, el posterior link era asignado al nodo con el link del anterior.

Tipos de Listas Enlazadas

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

Aplicaciones de las listas enlazadas

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

A veces, las listas enlazadas son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos

Ventajas

Como muchas opciones en programación y desarrollo, no existe un único método correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aquí una lista con un algunas de las ventajas más comunes que implican las estructuras de tipo lista. En general, teniendo una colección dinámica donde los elementos están siendo añadidos y eliminados frecuentemente e importa la localización de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.

Listas Enlazadas vs. Vectores o Matrices

Array Lista Enlazada

Indexado O(1) O(n)

Inserción / Eliminación al final O(1) O(1) or O(n)2

Inserción / Eliminación en la mitad O(n) O(1)

Persistencia

No Simples sí

Localización Buena Mala

Las listas enlazadas poseen muchas ventajas sobre los arrays. Los elementos se pueden insertar en una lista indefinidamente mientras que un array tarde o temprano se llenará ó necesitará ser redimensionado, una costosa operación que incluso puede no ser posible si la memoria se encuentra fragmentada.

En algunos casos se pueden lograr ahorros de memoria almacenando la misma ‘cola’ de elementos entre dos o más listas – es decir, la lista acaba en la misma secuencia de elementos. De este modo, uno puede añadir nuevos elementos al frente de la lista manteniendo una referencia tanto al nuevo como a los viejos elementos - un ejemplo simple de una estructura de datos persistente.

Por otra parte, los arrays permiten acceso aleatorio mientras que las listas enlazadas sólo permiten acceso secuencial a los elementos. Las listas enlazadas simples, de hecho, solo pueden ser recorridas en una dirección. Esto hace que las listas sean inadecuadas para aquellos casos en los que es útil buscar un elementos por su índice rápidamente, como el heapsort. El acceso secuencial en los arrays también es más rápido que en las listas enlazadas.

Otra desventaja de las listas enlazadas es el almacenamiento extra necesario para las referencias, que a menudos las hacen poco prácticas para listas de pequeños datos como caracteres o valores booleanos.

También puede resultar lento y abusivo el asignar memoria para cada nuevo elemento. Existe una variedad de listas enlazadas que contemplan los problemas anteriores para resolver los mismos. Un buen ejemplo que muestra los pros y contras del uso de arrays sobre listas enlazadas es la implementación de un programa que resuelva el problema de Josephus. Este problema consiste en un grupo de personas dispuestas en forma de círculo. Se empieza a partir de una persona predeterminadas y se cuenta n veces, la persona n-ésima se saca del círculo y se vuelve a cerrar el grupo. Este proceso se repite hasta que queda una sola persona, que es la que gana. Este ejemplo muestra las fuerzas y debilidades de las listas enlazadas frente a los arrays, ya que viendo a la gente como nodos conectados entre sí en una lista circular se observa como es más fácil

...