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 de la secuencia. Esta estructura permite la inserción o eliminación eficiente de elementos de 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 ). No es posible un acceso más rápido, como el acceso aleatorio. Las matrices tienen una mejor ubicación de caché en comparación con las listas vinculadas.
Las listas vinculadas 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 reasignar o reorganizar 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 cara. 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í mismas no permiten el acceso aleatorio a los datos o cualquier 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 de todos los elementos de la lista. Las ventajas y desventajas de usar listas enlazadas se detallan a continuación.
Las listas enlazadas 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 programas tempranos de inteligencia artificial , incluida la máquina de teoría lógica, el solucionador de problemas generales y un programa de ajedrez informático. Los informes sobre su trabajo aparecieron en IRE Transactions on Information Theory en 1956, y en varias actas de conferencias de 1957 a 1959, incluidas las Actas de la Western Joint Computer Conference en 1957 y 1958, y Information Processing (Actas de la primeraConferencia 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 "hecho 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 de lenguaje natural procesamiento llevó Victor Yngve en el 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 la traducción mecánica" apareció en Mechanical Translation en 1958. [ cita requerida ]
Otra aparición temprana de listas enlazadas fue la de Hans Peter Luhn, quien escribió un memorando interno de IBM en enero de 1953 que sugería el uso de listas enlazadas en tablas hash encadenadas. [1]
