alists

An alist, short for association list, is a simple data structure used to map keys to values in Lisp and related languages. It consists of a list whose elements are pairs, typically represented as cons cells with the key in the car and the value in the cdr. Alists are often used for small, static mappings and can be implemented with keys of any comparable type.

Access and modification in an alist are usually done through linear search. Common operations include looking up a value by key and returning the associated value or the pair itself. In Common Lisp and Emacs Lisp, functions such as assoc (or alist-get in some dialects) perform key-based lookup. A lookup returns the matching cons cell (key . value); the value is obtained from the cdr. To update, you generally rebuild the alist with the new pair or modify the element in place if supported by the language.

Complexity and trade-offs: lookup time is O(n) in the length of the alist, and updates may require traversing the list. Alists are memory-light and easy to serialize, making them convenient for small datasets or configuration data. They contrast with hash tables or dictionaries, which provide near-constant-time lookups at the cost of hashing logic and potentially more complex maintenance.

Example (Lisp-like syntax): A = ((apple . 3) (banana . 5) (orange . 2)); (assoc 'banana A) yields (banana . 5); (cdr (assoc 'banana A)) yields 5. In Emacs Lisp, (alist-get 'banana A) returns 5.

See also: association list, plist, hash table, dictionary, assoc.