Origen de las listas enlazadas 


Las listas enlazadas fueron desarrolladas entre 1955 y 1956 por Allen Newell, Cliff Shaw y Herbert A. Simon. Se crearon en la Universidad Carnegie Mellon y en RAND Corporation como la estructura de datos principal para su lenguaje de procesamiento de información (IPL).  
Las listas enlazadas se crearon para resolver los problemas de almacenamiento y manipulación de datos en las computadoras de la época, que tenían poca memoria y hardware de bajo rendimiento. 

Comentarios

Publicar un comentario

Entradas populares de este blog

Imagen
Listas enlazadas  Una lista enlazada es un conjunto de elementos  llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo, donde el orden de los mismos se  es tablece mediante punteros. La idea básica  es   que  cada componente de la  lista  incluya un puntero  que  indi que  donde puede encontrarse el siguiente componente por lo  que  el orden relativo de  es tos puede ser fácilmente alterado modificando los punteros lo  que  permite, a su vez, añadir o suprimir elementos de la  lista .  El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista. El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.
Leer más
Imagen
Tipos de listas enlazadas  Listas doblemente enlazadas : Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo. En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque esta técnica no se suele utilizar. Listas enlazadas circulares: En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas ...
Leer más
 Ventajas y desventajas de las listas enlazadas  Ventajas  Es muy sencillo implementar pilas y  colas  usando listas enlazadas. Las  tablas hash  (usadas en diccionarios o mapas) tienen sus elementos distribuidos en un array gigante, donde los elementos colisionados pueden estar almacenados en una lista enlazada. Podrían estar almacenados en un array dinámico, pero el proceso de rehashing (cuando cambian las dimensiones del array gigante de la tabla hash) es más eficiente reusando los nodos de la lista enlazada. Cuando tienes un conjunto de elementos del que quieres remover algunos elementos dependiendo de alguna condición. Removerlos de una lista enlazada consiste simplemente en destruir el elemento preciso y actualizar los enlaces de sus nodos siguiente y anterior adecuadamente. Removerlos de un array dinámico implicaría recorrer todos los elementos siguientes en cada eliminación, mucho menos eficiente. Desventajas  Utilizan más memoria que los ...
Leer más