En programación informática y particularmente en Lisp , una lista de asociación , a menudo denominada alist , es una lista enlazada en la que cada elemento de la lista (o nodo ) comprende una clave y un valor . Se dice que la lista de asociación asocia el valor con la clave. Para encontrar el valor asociado con una clave dada, se utiliza una búsqueda secuencial : se busca cada elemento de la lista por turno, comenzando por el encabezado, hasta que se encuentra la clave. Las listas asociativas proporcionan una forma sencilla de implementar una matriz asociativa , pero son eficientes solo cuando el número de claves es muy pequeño.
Una matriz asociativa es un tipo de datos abstracto que se puede utilizar 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 datos.
Para comprobar si una clave está asociada a un valor en una lista de asociaciones dada, 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 agregar 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 múltiples nodos con las mismas claves entre sí, 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 ocurrencia de la clave y uniendo los nodos que contienen la clave fuera de la lista. [1] El escaneo debe continuar hasta el final de la lista, incluso cuando se encuentra la clave, en caso de que la misma clave se haya insertado varias veces.
La desventaja de las listas de asociación 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 una matriz asociativa como un árbol de búsqueda binario o como una tabla hash . Además, a menos que la lista se pode regularmente para eliminar elementos con claves duplicadas, 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 añadir 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 binario de búsqueda o una tabla hash, debido a la mayor simplicidad de su implementación. [4]
En los primeros desarrollos de Lisp, se utilizaban listas de asociación para resolver referencias a variables libres en procedimientos. [5] [6] En esta aplicación, es conveniente aumentar las listas de asociación con una operación adicional, que invierte la adición de un par clave-valor sin escanear la lista en busca de otras copias de la misma clave. De esta manera, la lista de asociación puede funcionar como una pila , lo que permite que las variables locales oculten temporalmente otras variables con los mismos nombres, sin destruir los valores de esas otras variables. [7]
Muchos lenguajes de programación, incluidos Lisp, [5] Scheme , [8] OCaml , [9] y Haskell [10] tienen funciones para manejar listas de asociaciones en sus bibliotecas estándar .