AList

An alist, short for association list, is a simple data structure used to store key-value pairs as a list of pairs. Each element in the list is a pair, with the key typically stored in the car and the value in the cdr. In Lisp and related languages, alists are a common way to represent small maps or configuration data. Keys are usually unique within a given alist, though some codebases allow shadowing by placing newer bindings at the front.

Access and mutation: To retrieve a value, a language-specific function such as assoc is used to search the list for a pair whose key matches the desired key. Because the alist is a linear list, lookup is generally O(n) time. Insertion often means consing a new pair to the front of the list, which creates a new binding (potentially shadowing older ones). Deletion involves removing the matching pair from the list. In many Lisp dialects, alternative helpers such as assq or test parameters in assoc customize how keys are compared.

Variants and relation to other structures: A sorted alist organizes pairs by key and can support faster lookups in certain circumstances, though the underlying search remains linear unless augmented with additional structures. A related concept is the plist (property list), which stores data as a flat list of alternating keys and values. For larger datasets or performance-critical code, a hash table is typically preferred due to faster average-case lookups.

Use and limitations: Alists are convenient for small, simple mappings or for code that favors immutability and functional style. They are easy to construct and reason about in Lisp and similar languages, but their linear-search characteristic makes them less suitable for large maps or performance-sensitive applications.