'''Lista de nodos'''

De 15Mpedia
Saltar a: navegación, buscar

'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 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 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.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 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 Listas doblemente 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