Lista de asociaciones

En programación informática , y en particular en Lisp , una lista asociativa , a menudo denominada lista de asociación , es una lista enlazada en la que cada elemento (o nodo ) consta de una clave y un valor . Se dice que la lista asocia el valor con la clave. Para encontrar el valor asociado a una clave dada, se utiliza una búsqueda secuencial : se busca en cada elemento de la lista, comenzando por el primero, hasta encontrar la clave. Las listas asociativas proporcionan una forma sencilla de implementar un array asociativo , pero solo son eficientes cuando el número de claves es muy pequeño.

Un array asociativo es un tipo de dato abstracto que se puede usar para mantener una colección de pares clave-valor y buscar el valor asociado a una clave determinada. La lista de asociación proporciona una forma sencilla de implementar este tipo de dato.

Para comprobar si una clave está asociada a un valor en una lista de asociaciones determinada, busque en la lista comenzando por su primer nodo y continuando hasta que se encuentre un nodo que contenga la clave o hasta que la búsqueda llegue al final de la lista (en cuyo caso la clave no está presente). Para añadir un nuevo par clave-valor a una lista de asociaciones, cree un nuevo nodo para ese par clave-valor, establezca el enlace del nodo como el primer elemento anterior de la lista de asociaciones y reemplace el primer elemento de la lista de asociaciones con el nuevo nodo. ^{[ 1 ]} Aunque algunas implementaciones de listas de asociaciones no permiten tener varios nodos con las mismas claves, tales duplicaciones no son problemáticas para este algoritmo de búsqueda: las claves duplicadas que aparecen más adelante en la lista se ignoran. ^{[ 2 ]}

También es posible eliminar una clave de una lista de asociaciones, escaneando la lista para encontrar cada aparición de la clave y eliminando de la lista los nodos que la contienen. ^{[ 1 ]} El escaneo debe continuar hasta el final de la lista, incluso cuando se encuentre la clave, en caso de que la misma clave se haya insertado varias veces.

La desventaja de las listas asociativas es que el tiempo de búsqueda es O ( n ) , donde n es la longitud de la lista. ^{[ 3 ]} Para listas grandes, esto puede ser mucho más lento que los tiempos que se pueden obtener al representar un arreglo asociativo como un árbol de búsqueda binaria o como una tabla hash . Además, a menos que la lista se pode regularmente para eliminar elementos con claves duplicadas, los múltiples valores asociados con la misma clave aumentarán el tamaño de la lista y, por lo tanto, el tiempo de búsqueda, sin proporcionar ninguna ventaja compensatoria.

Una ventaja de las listas de asociación es que se puede agregar un nuevo elemento en tiempo constante. Además, cuando el número de claves es muy pequeño, la búsqueda en una lista de asociación puede ser más eficiente que la búsqueda en un árbol de búsqueda binaria o una tabla hash, debido a la mayor simplicidad de su implementación. ^{[ 4 ]}

En el desarrollo inicial de Lisp, se utilizaban listas de asociación para resolver referencias a variables libres en procedimientos. ^{[ 5 ] [ 6 ]} En esta aplicación, resulta conveniente ampliar las listas de asociación con una operación adicional que revierte la adición de un par clave-valor sin buscar en la lista otras copias de la misma clave. De esta forma, la lista de asociación puede funcionar como una pila , permitiendo que las variables locales oculten temporalmente otras variables con los mismos nombres, sin destruir los valores de estas últimas. ^{[ 7 ]}

Muchos lenguajes de programación, incluidos Lisp, ^{[ 5 ]} Scheme , ^{[ 8 ]} OCaml , ^{[ 9 ]} y Haskell ^{[ 10 ]} tienen funciones para manejar listas de asociación en sus bibliotecas estándar .

• Lista autoorganizada , una estrategia para reordenar las claves en una lista de asociación con el fin de acelerar las búsquedas de claves a las que se accede con frecuencia.
• Lista de propiedades, o plist, otra estructura de datos de matriz asociativa utilizada en Lisp ^{[ 11 ]} (no confundir con listas de propiedades , un formato de archivo también llamado archivos plist).