Editing Association list (section)

{{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.