A finite ordered sequence of items (x1,x2,…xn), where n ≥ 0. If n = 0, the list has no elements and is called the null list (or empty list). If n > 0, the list has at least one element, x1, which is called the head of the list (see also header). The list consisting of the remaining items is called the tail of the original list. The tail of the null list is the null list, as is the tail of a list containing only one element.
The items in a list can be arbitrary in nature, unless stated otherwise. In particular it is possible for an item to be another list, in which case it is known as a sublist. For example, let L be the list
then the third item of L is the list (C,D), which is a sublist of L. If a list has one or more sublists it is called a
list structure. If it has no sublists it is a
linear list. The two basic representation forms for lists are sequentially allocated lists and linked lists, the latter being more flexible.