List (abstract data type)

A list is an ordered collection in which entries may repeat. Removing duplicates would discard information about both multiplicity and, depending on the representation, order. A linked list and an array are different ways to implement list operations.

Replacing a list by a list containing each of its distinct elements once. Retaining first occurrences gives a stable order. A recursive implementation emits the head and removes all its occurrences from the tail before continuing. On an infinite input with only finitely many distinct values, detecting that there are no further new values may diverge; on an infinite input with infinitely many distinct values and terminating equality tests, each successive new value has a finite position and can be emitted.

Retain the first occurrence of each distinct value in a list. The right fold foldr (\x ys -> x : filter (/= x) ys) [] preserves this order under lazy evaluation. With terminating equality tests, an infinite input containing infinitely many distinct values produces every finite output prefix. If only finitely many distinct values occur, those values appear but the remaining infinite input cannot generally be certified empty: the result has an undefined tail rather than a terminating empty list.

Reverse the order of a finite list. Reversal is an involution and satisfies $(AB{)}^R=B^R{A}^R$ for list concatenation. In an array segment of length $n$, exchanging symmetric offsets $j$ and $n-1-j$ for $0\le j<\lfloor n/2\rfloor$ realizes reversal in constant auxiliary space.

A tree representation of a list with empty nodes, single-element nodes and binary concatenation nodes. Concatenation constructs one node without traversing either operand. The representation need not be unique: adding empty branches changes its size without changing the denoted list. An accumulator-based traversal gives linear flattening of a binary tree in the representation's size rather than merely the output length.

Combine corresponding entries of two lists into a list of tuples. The usual finite-list operation stops when either input ends. A lazy evaluation implementation can produce entries from infinite lists, but its exact strictness depends on the order of pattern matching in the definition.

Represent a finite list by a function from indices to optional values. There must be a length $m$ for which exactly the indices $0\le i<m$ are present; later indices are absent, so the representation has no holes. Prepending and removing a head shift indices, taking restricts the present domain, and dropping translates it. Functional composition can accumulate query costs, so array-like constant-time access does not follow from the representation type.

A persistent list representation supporting positional lookup more efficiently than a conventional linked list. Different implementations trade lookup, insertion and deletion costs; “random-access” does not itself guarantee constant-time indexing. A skew-binary random-access list supports worst-case constant-time front insertion and removal with logarithmic worst-case lookup.

Represent a finite list by a forest of value-bearing perfect binary trees of sizes $1,3,7,\dots$, in nondecreasing order, using the greedy largest sizes and allowing a repeated size only in the first two positions. Concatenated preorder traversals recover the list. Cached tree sizes guide indexing.

Front insertion merges the first two equal-size trees beneath a new root, or adds a singleton if they differ. Removing the first root either discards a singleton or splits its two children into the initial equal-size pair. Both operations inspect and allocate only a bounded number of constructors, taking worst-case constant time and sharing the remaining representation. A positional query skips whole cached tree sizes and then descends through one tree, taking $O(\log (n+1))$ time. Conversion in either direction takes linear time on finite input.

The duplicate-size restriction follows directly from greediness. If two size-$w$ trees had any preceding nonempty portion, there would be at least $2w+1$ elements available, enough for the next larger perfect binary tree. Three equal-size trees would likewise suffice for that larger tree. Both contradict the greedy representation.

Represent a list $xs$ by the function \ys -> xs ++ ys. Concatenation becomes function composition, the empty list is represented by id, and applying to [] recovers the list. Only functions of this tail-prepending form are valid representations; arbitrary functions of the displayed type need not satisfy the invariant. A higher-order tree fold using difference lists produces an inorder traversal in linear time on every tree shape.

For a leaf-labelled binary tree, define go (One x) acc = x:acc and go (Two l r) acc = go l (go r acc), then apply go t []. The invariant in the title follows by structural induction and associativity of list concatenation. It proves preservation of leaf order. Each leaf supplies one output constructor and each internal node requires constant bookkeeping, giving linear time in the number of nodes. By contrast, flattening both subtrees and concatenating their results can copy prefixes of sizes $1,2,\dots ,n-1$ on a left-branching tree, taking quadratic time. The accumulator is the already-known suffix in a difference list representation.

Append the second list after the first. For a finite left list of length $n$, consuming the concatenation costs $\Theta (n)$ to copy its spine and can share the second argument. Repeatedly appending large left lists can cause quadratic time complexity; difference lists make concatenation into function composition.

Concatenating the initial list prefix accepted by a predicate with the remaining list suffix reconstructs the input, provided every test reached before the first false result terminates. Prove the finite case by structural induction: a true test copies the head, and a false test returns the untouched list suffix. An undefined reached test is an obstruction because reconstruction loses an exposed cons cell. An infinite all-true list prefix can still reconstruct the input, since list concatenation never demands its second argument there.

A list obtained by dropping an initial segment. The whole list and, for finite lists, the empty list are suffixes. Proper suffixes exclude the whole list; nonempty suffixes exclude []. In a linked list, suffixes can share the original nodes, permitting a list of all suffixes to be constructed with linear additional space.

An initial segment of a list, including the empty segment and, for finite lists, the whole list. A proper prefix excludes the whole list. Fully materialising all prefixes of a length-$n$ list needs $\Theta (n^2)$ element constructors, although the outer list of prefixes has only $n+1$ entries.

An initial segment of a string, including the empty string or the whole string. Two strings share a prefix exactly when their initial characters agree up to its length. The longest common prefix is the longest such shared initial segment.