lista

Lista (informática)
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, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadasrespecto a los vectores 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 autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Laslistas 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: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares.
Laslistas 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.
Índice
1 Historia
2 Tipos de listas enlazadas
2.1Listas enlazadas lineales
2.1.1 Listas simples enlazadas
2.1.2 Listas doblemente enlazadas
2.2 Listas enlazadas circulares
2.2.1 Listas enlazadas simples circulares
2.2.2 Listas enlazadas doblemente circulares
2.3 Nodos centinelas
3 Aplicaciones de las listas enlazadas
4 Ventajas
4.1 Listas enlazadas vs. vectores o matrices
4.2 Doblemente enlazadas vs. simplemente enlazadas
4.3Circulares enlazadas vs. lineales enlazadas
4.4 Nodos centinelas (header nodes)
5 Listas enlazadas usando vectores de nodos
6 Lenguajes soportados
7 Almacenamiento interno y externo
8 Agilización de la búsqueda
9 Estructuras de datos relacionadas
10 Implementaciones
10.1 Operaciones sobre listas enlazadas
10.1.1 Listas enlazadas lineales
10.1.1.1 Listas simples enlazadas
10.1.1.2 Listasdoblemente enlazadas
10.1.2 Listas enlazadas circulares
10.1.2.1 Listas enlazadas doblemente circulares
10.2 Listas enlazadas usando vectores de nodos
10.3 Implementación de una lista enlazada en C
10.4 Implementación de una lista enlazada en C++
10.5 Implementación de una lista enlazada en Maude
10.6 Ejemplos de almacenamiento interno y externo
11 Referencias
12 Enlaces externos
HistoriaLas 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 unprograma 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 Information Processing (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 querepresentan 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...