World Library  
Flag as Inappropriate
Email this Article

Association list

Article Id: WHEBN0000394077
Reproduction Date:

Title: Association list  
Author: World Heritage Encyclopedia
Language: English
Subject: Associative array, Associative arrays, Fexpr, AutoLISP, Fundamental Data Structures
Collection: Associative Arrays, Linked Lists
Publisher: World Heritage Encyclopedia

Association list

Association list
Type associative array
Time complexity
in big O notation
Average Worst case
Space O(n) O(n)
Search O(n) O(n)
Insert O(1) O(1)
Delete O(n) O(n)

In computer programming and particularly in Lisp, an association list, often referred to as an alist, is a linked list in which each list element (or node) comprises a 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, each element of the list is searched in turn, starting at the head, until the key is found. Duplicate keys that appear later in the list are ignored. It is a simple way of implementing an associative array.

The disadvantage of association lists is that the time to search is O(n), where n is the length of the list. And 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 is that a new element can be added to the list at its head, which can be done in constant time. For quite small values of n it is more efficient in terms of time and space than more sophisticated strategies such as hash tables and trees.

In the early development of Lisp, association lists were used to resolve references to free variables in procedures.[1]

Many programming languages, including Lisp, Scheme, OCaml, and Haskell have functions for handling association lists in their standard library.


The markup language HTML and its derivative XHTML have an analogous set of association list elements, more often referred to as description lists,[2] and known as definition lists prior to HTML5.[3] The

element delimits the list, the term (key) is delimited by
element, and the description or definition (value) is delimited by the
element. The
elements are sister elements, under (inside) the
node. Any given term may be followed by multiple descriptions/definitions, and any of the latter may be preceded by more than one of the former (e.g., alternative spellings of or names for the term). A
does not require a
at all (i.e., may be undefined); a null
can be used as an empty placeholder for later association. A
with no
(or only a null
) with which to associate is not technically invalid markup, but is semantically poorly formed in most contexts. No other elements may be directly under the
node. Basic flow content nodes (elements), such as italicization and links, may be used within a term node. The description node may contain any flow content at all, including sectioning and heading elements.


  1. ^ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985). LISP 1.5 Programmer's Manual (PDF).  
  2. ^ "4.5 Grouping content – HTML5". HTML5: A vocabulary and associated APIs for HTML and XHTML – W3C Recommendation.  
  3. ^ "Lists in HTML documents". HTML 4.01 Specification – W3C Recommendation. World Wide Web Consortium. 24 December 1999. 10.3 Definition lists: the DL, DT, and DD elements. Retrieved 2 May 2015. 

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.