Lista Inform Tica

16/3/2015

Lista (informática) ­ Wikipedia, la enciclopedia libre

Lista (informática)
De Wikipedia, la enciclopedia libre
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  enlazadas  respecto  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.  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:  listas  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.

Índice
1 Historia
2 Tipos de listas enlazadas
2.1 Listas 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 circulares2.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.3 Circulares enlazadas vs. lineales enlazadas
4.4 Nodos centinelas (header nodes)
5 Listas enlazadas usando vectores de nodos
6 Lenguajes soportados
7 Almacenamiento interno y externo8 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
http://es.wikipedia.org/w/index.php?title=Lista_(inform%C3%A1tica)&printable=yes

1/19

16/3/2015

Lista (informática) ­ Wikipedia, la enciclopedia libre

10.1.1.1 Listas simples enlazadas
10.1.1.2 Listas doblemente enlazadas10.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

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  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 ...