Lista enlazada
En informática , una lista enlazada es una colección lineal de elementos de datos cuyo orden no viene dado por su ubicación física en la memoria. En cambio, cada elemento apunta al siguiente. Es una estructura de datos que consta de una colección de nodos que juntos representan una secuencia . En su forma más básica, cada nodo contiene: datos y una referencia (en otras palabras, un enlace) al siguiente nodo en la secuencia. Esta estructura permite la inserción o eliminación eficiente de elementos desde cualquier posición en la secuencia durante la iteración. Las variantes más complejas agregan enlaces adicionales, lo que permite una inserción o eliminación más eficiente de nodos en posiciones arbitrarias. Un inconveniente de las listas enlazadas es que el tiempo de acceso es lineal (y difícil de canalizar ). Un acceso más rápido, como el acceso aleatorio, no es factible. Las matrices tienen una mejor localidad de caché en comparación con las listas vinculadas.
Las listas enlazadas se encuentran entre las estructuras de datos más simples y comunes. Se pueden usar para implementar varios otros tipos de datos abstractos comunes , incluidas listas , pilas , colas , matrices asociativas y expresiones S , aunque no es raro implementar esas estructuras de datos directamente sin usar una lista vinculada como base.
El principal beneficio de una lista enlazada sobre una matriz convencional es que los elementos de la lista se pueden insertar o eliminar fácilmente sin reasignación o reorganización de toda la estructura porque los elementos de datos no necesitan almacenarse contiguamente en la memoria o en el disco, mientras se reestructura una matriz en el tiempo de ejecución es una operación mucho más costosa. Las listas enlazadas permiten la inserción y eliminación de nodos en cualquier punto de la lista, y permiten hacerlo con un número constante de operaciones manteniendo el enlace anterior al enlace que se agrega o elimina en la memoria durante el recorrido de la lista.
Por otro lado, dado que las listas enlazadas simples por sí solas no permiten el acceso aleatorio a los datos ni ninguna forma de indexación eficiente, muchas operaciones básicas, como obtener el último nodo de la lista, encontrar un nodo que contenga un dato dado o ubicar el lugar donde se debe insertar un nuevo nodo, puede requerir iterar a través de la mayoría o todos los elementos de la lista. Las ventajas y desventajas de usar listas enlazadas se dan a continuación.
Las listas vinculadas fueron desarrolladas en 1955-1956 por Allen Newell , Cliff Shaw y Herbert A. Simon en RAND Corporation como la estructura de datos principal para su lenguaje de procesamiento de información . Los autores utilizaron IPL para desarrollar varios de los primeros programas de inteligencia artificial , incluida la Máquina de teoría lógica, el Solucionador general de problemas y un programa de ajedrez por computadora. Los informes sobre su trabajo aparecieron en IRE Transactions on Information Theory en 1956, y varias actas de conferencias de 1957 a 1959, incluidas las Actas de la Western Joint Computer Conference en 1957 y 1958, y Information Processing (Proceedings of the firstConferencia Internacional de la UNESCO sobre Procesamiento de la Información) en 1959. El diagrama ahora clásico que consta de bloques que representan nodos de lista con flechas que apuntan a nodos de lista sucesivos aparece en "Programación de la máquina de teoría lógica" de Newell y Shaw en Proc. WJCC, febrero de 1957. Newell y Simon fueron reconocidos con el premio ACM Turing en 1975 por haber "realizado contribuciones básicas a la inteligencia artificial, la psicología de la cognición humana y el procesamiento de listas". El problema de la traducción automática para el procesamiento del lenguaje natural llevó a Victor Yngve del Instituto Tecnológico de Massachusetts(MIT) para utilizar listas enlazadas como estructuras de datos en su lenguaje de programación COMIT para la investigación informática en el campo de la lingüística . Un informe sobre este lenguaje titulado "Un lenguaje de programación para traducción mecánica" apareció en Mechanical Translation en 1958. [ cita requerida ]
Otra aparición temprana de las listas enlazadas fue la de Hans Peter Luhn , quien escribió un memorándum interno de IBM en enero de 1953 que sugería el uso de listas enlazadas en tablas hash encadenadas. [1]
