Association list
Association list | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | associative array | |||||||||||||||||||||||
|
In
Operation
An
To test whether a key is associated with a value in a given association list, search the list starting at its first node and continuing either until a node containing the key has been found or until the search reaches the end of the list (in which case the key is not present). To add a new key–value pair to an association list, create a new node for that key-value pair, set the node's link to be the previous first element of the association list, and replace the first element of the association list with the new node.[1] Although some implementations of association lists disallow having multiple nodes with the same keys as each other, such duplications are not problematic for this search algorithm: duplicate keys that appear later in the list are ignored.[2]
It is also possible to delete a key from an association list, by scanning the list to find each occurrence of the key and splicing the nodes containing the key out of the list.[1] The scan should continue to the end of the list, even when the key is found, in case the same key may have been inserted multiple times.
Performance
The disadvantage of association lists is that the time to search is O(n), where n is the length of the list.[3] For large lists, this may be much slower than the times that can be obtained by representing an associative array as a binary search tree or as a hash table. Additionally, 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 of association lists is that a new element can be added in constant time. Additionally, when the number of keys is very small, searching an association list may be more efficient than searching a binary search tree or hash table, because of the greater simplicity of their implementation.[4]
Applications and software libraries
In the early development of Lisp, association lists were used to resolve references to
Many programming languages, including Lisp,[5] Scheme,[8] OCaml,[9] and
See also
- Self-organizing list, a strategy for re-ordering the keys in an association list to speed up searches for frequently-accessed keys.
- Property list, or plist, another associative array data structure used in Lisp[11] (not to be confused with property lists, a file format also called plist files).
References
- ^ ISBN 9780262133418.
- ISBN 9781461430872.
- ISBN 0-201-89685-0.
- ISBN 9780735665279.
- ^ ISBN 0-262-13011-4. See in particular p. 12 for functions that search an association list and use it to substitute symbols in another expression, and p. 103 for the application of association lists in maintaining variable bindings.
- ISBN 9781461227106.
- ISBN 9781558604421.
- ISBN 9781461216827.
- ISBN 9781449324766.
- ISBN 9780596554309.
- ^ "10.1. The Property List". Cs.cmu.edu. Retrieved 29 September 2017.