List

By definition, a list is a finite set of entries with a certain order. The entries in the list, depending on the language, may be constrained to the same type, or may be of mixed types. An array is a related data structure that also stores its entries sequentially. However, the items in an array usually must be of the same type. Nearly all kinds of tree structures can also be stored as lists.

In Lisp, lists are the fundamental data type, which can represent either program code or data. Some languages do not offer a list data structure, but offer the use of associated lists or some kind of table to emulate lists.

In Ruby or Prolog lists can be written like:

[1,2,4.5,"hello",[1,2,3]]

In Java, list is an interface in its standard library. C++ provides general list facilities in its Standard Template Library (STL).

The standard way of implementing lists, originating with Lisp, is to have each element of the list contain both its value and a pointer indicating the location of the next element in the list. This results in either a linked list or a tree, depending on whether the list has nested sublists or not. Some languages may instead implement lists using other data structures, such as arrays.

The manipulation of lists can be done using iterations or a recursive algorithm.