Editing Association list

{{Short description|Linked list of key-value pairs}}
{{Infobox data structure
|name=Association list
|type=[[associative array]]
|invented_by=
|invented_year=
|space_avg=O(''n'')
|space_worst=O(''n'')
|search_avg=O(''n'')
|search_worst=O(''n'')
|insert_avg=O(1)
|insert_worst=O(1)
|delete_avg=O(''n'')
|delete_worst=O(''n'')
}}

In [[computer programming]] and particularly in [[Lisp (programming language)|Lisp]], an '''association list''', often referred to as an '''alist''', is a [[linked list]] in which each list element (or [[Node (computer science)|node]]) comprises a [[Attribute–value pair|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, a [[sequential search]] is used: each element of the list is searched in turn, starting at the head, until the key is found.  Associative lists provide a simple way of implementing an [[associative array]], but are efficient only when the number of keys is very small.

==Operation==
An [[associative array]] is an [[abstract data type]] that can be used to maintain a collection of [[Attribute–value pair|key–value pairs]] and look up the value associated with a given key. The association list provides a simple way of implementing this data type.

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.<ref name="pwc">{{cite book|title=Programming with Constraints: An Introduction|first1=Kim|last1=Marriott|first2=Peter J.|last2=Stuckey|publisher=MIT Press|year=1998|isbn=9780262133418|pages=193–195|url=https://books.google.com/books?id=jBYAleHTldsC&pg=PA193}}</ref> 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.<ref>{{cite book|title=Logic and the Organization of Information|first=Martin|last=Frické|publisher=Springer|year=2012|isbn=9781461430872|pages=44–45|contribution-url=https://books.google.com/books?id=HnAmoLBcilIC&pg=PA44|contribution=2.8.3 Association Lists}}</ref>

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.<ref name="pwc"/> 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 {{math|[[Big O notation|''O''(''n'')]]}}, where {{mvar|n}} is the length of the list.<ref>{{cite book|first=Donald|last=Knuth|author-link=Donald Knuth|contribution=6.1 Sequential Searching|title=[[The Art of Computer Programming]], Vol. 3: Sorting and Searching|date=1998 |pages=396–405|publisher=Addison Wesley|edition=2nd|isbn=0-201-89685-0}}</ref> 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.<ref>{{cite book|title=Developer's Guide to Collections in Microsoft .NET|first=Calvin|last=Janes|publisher=Pearson Education|year=2011|isbn=9780735665279|page=191|contribution-url=https://books.google.com/books?id=-KdCAwAAQBAJ&pg=PT191|contribution=Using Association Lists for Associative Arrays}}</ref>

==Applications and software libraries==
In the early development of Lisp, association lists were used to resolve references to [[Free variables and bound variables|free variables]] in procedures.<ref name="mccarthy_lisp_1.5">{{cite book | url = https://archive.org/details/lisp15programmer00john | title = LISP 1.5 Programmer's Manual | publisher = [[MIT Press]] | first1 = John | last1 = McCarthy | first2 = Paul W. | last2 = Abrahams | first3 = Daniel J. | last3 = Edwards | first4 = Timothy P. | last4 = Hart | first5 = Michael I. | last5 = Levin | isbn = 0-262-13011-4 | year = 1985 | url-access = registration }} See in particular p.&nbsp;12 for functions that search an association list and use it to substitute symbols in another expression, and p.&nbsp;103 for the application of association lists in maintaining variable bindings.</ref><ref>{{cite book|title=What Computing Is All About|series=Monographs in Computer Science|first=Jan L. A.|last=van de Snepscheut|publisher=Springer|year=1993|isbn=9781461227106|page=201|url=https://books.google.com/books?id=VXPrBwAAQBAJ&pg=PA201}}</ref> In this application, it is convenient to augment association lists with an additional operation, that reverses the addition of a key–value pair without scanning the list for other copies of the same key. In this way, the association list can function as a [[Stack (abstract data type)|stack]], allowing [[local variables]] to temporarily [[Variable shadowing|shadow]] other variables with the same names, without destroying the values of those other variables.<ref>{{cite book|title=Programming Language Pragmatics|first=Michael Lee|last=Scott|publisher=Morgan Kaufmann|year=2000|isbn=9781558604421|page=137|contribution-url=https://books.google.com/books?id=To3xpkvkPvMC&pg=PA137|contribution=3.3.4 Association Lists and Central Reference Tables}}</ref>

Many programming languages, including
Lisp,<ref name="mccarthy_lisp_1.5"/>
[[Scheme (programming language)|Scheme]],<ref>{{cite book|title=Programming and Meta-Programming in Scheme|series=Undergraduate Texts in Computer Science|first=Jon|last=Pearce|publisher=Springer|year=2012|isbn=9781461216827|page=214|url=https://books.google.com/books?id=uDzaBwAAQBAJ&pg=PA214}}</ref>
[[OCaml]],<ref>{{cite book|title=Real World OCaml: Functional Programming for the Masses|first1=Yaron|last1=Minsky|first2=Anil|last2=Madhavapeddy|first3=Jason|last3=Hickey|publisher=O'Reilly Media|year=2013|isbn=9781449324766|page=253|url=https://books.google.com/books?id=nabtAQAAQBAJ&pg=PA253}}</ref> and
[[Haskell (programming language)|Haskell]]<ref>{{cite book|title=Real World Haskell: Code You Can Believe In|first1=Bryan|last1=O'Sullivan|first2=John|last2=Goerzen|first3=Donald Bruce|last3=Stewart|publisher=O'Reilly Media|year=2008|isbn=9780596554309|page=299|url=https://books.google.com/books?id=nh0okI1a1sQC&pg=PA299}}</ref> have functions for handling association lists in their [[standard library|standard libraries]].

==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<ref>{{cite web|url=https://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node108.html|title=10.1. The Property List|website=Cs.cmu.edu|accessdate=29 September 2017}}</ref> (not to be confused with [[Property list|property lists]], a file format also called plist files).

==References==
{{Reflist}}

{{Data structures}}

[[Category:Linked lists]]
[[Category:Associative arrays]]