Listas enlazadas

Lista (estructura de datos)

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 enlazadasrespecto 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 yeliminación de nodos en cualquier punto de la lista en tiempo constante, pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas y Listas Enlazadas Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto conoperaciones 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.
Contenido[ocultar] * 1 Historia * 2 Tipos de Listas Enlazadas * 2.1 Listas enlazadas lineales * 2.1.1 Listas simples enlazadas * 2.1.2 Lista Doblemente Enlazada * 2.2 Listasenlazadas circulares * 2.2.1 Listas enlazadas circulares simples * 2.2.2 Lista Enlazada Doblemente Circular * 2.3 Nodos Centinelas * 3 Aplicaciones de las listas enlazadas * 4 Ventajas * 4.1 Listas Enlazadas vs. Arrays * 4.2 Doblemente Enlazadas vs. Simples Enlazadas * 4.3 Circulares Enlazadas vs. Lineales Enlazadas * 4.4 Nodos Centinelas (header nodes) * 5Operaciones sobre listas enlazadas * 5.1 Listas Enlazadas Lineales * 5.1.1 Listas Simples Enlazadas * 5.1.2 Listas Doblemente Enlazadas * 5.2 Listas Enlazadas Circulares * 5.2.1 Listas Enlazadas Doblemente Circulares * 6 Listas enlazadas usando Arrays de Nodos * 7 Lenguajes soportados * 8 Almacenamiento interno y externo * 8.1 Ejemplos dealmacenamiento interno y externo * 9 Agilización de la búsqueda * 10 Estructuras de datos relacionadas * 11 Referencias * 12 Enlace Externos |
Historia [editar]
Las listas enlazadas fueron desarrolladas en 1955-56 por Allen Newell, 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 losautores 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 Transactions on Information Theory en 1956, y en distintas conferencias entre 1957-1959, incluida Proceedings of the Western Joint Computer 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 Programming the Logic Theory Machine, de Newell y Shaw. Newell y Simon fueron reconocidos por el ACM Turing Award 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 Victor Yngve 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ó...