Association list
| Association list | ||
|---|---|---|
| Type | associative array | |
| Time complexity in big O notation | ||
| Average | Worst case | |
| Space | O(n) | O(n) |
| Search | O(n) | O(n) |
| Insert | O(1) | O(1) |
| Delete | O(n) | O(n) |
In computer programming and particularly in Lisp, an association list, often referred to as an alist, is a linked list in which each list element (or node) comprises a key and a value. The association list is said to associate the value with the key. In order to find the value associated with a given key, each element of the list is searched in turn, starting at the head, until the key is found. Duplicate keys that appear later in the list are ignored. It is a simple way of implementing an associative array.
Performance
The disadvantage of association lists is that the time to search is O(n), where n is the length of the list. And unless the list is regularly pruned to remove elements with duplicate keys, multiple values associated with the same key will increase the size of the list, and thus the time to search, without providing any compensatory advantage. One advantage is that a new element can be added to the list at its head, which can be done in constant time. For quite small values of n it is more efficient in terms of time and space than more sophisticated strategies such as hash tables and trees.
Applications and software libraries
In the early development of Lisp, association lists were used to resolve references to free variables in procedures.[1]
Many programming languages, including Lisp, Scheme, OCaml, and Haskell have functions for handling association lists in their standard library.
See also
- Description lists, an element of HTML coding analogous to association lists
References
- ↑ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985). LISP 1.5 Programmer's Manual (PDF). MIT Press. ISBN 0-262-13011-4.
| ||||||||||||||||||||||||||||||