Cons and Linked Representation

The cons operator

The operator :: (pronounced “cons”, short for “construct”) puts a new element onto the head of an existing list:

1 :: [3; 5; 9]     (* [1; 3; 5; 9] *)
1 :: 2 :: []        (* [1; 2] *)

Critically, :: is an O(1) operation — it uses constant time and space regardless of the length of the list.

Internal structure

Lists are represented internally as a linked structure of cons cells. Each cons cell contains:

• A reference to the head (an element)
• A reference to the tail (another cons cell or [])

Adding a new element to a list merely hooks a new cons cell to the front of the existing structure. The existing structure continues to denote the same list as it did before — to see the new list, one must look at the new cons cell.

Sharing of tails

Because cons does not copy the tail, multiple lists can share their tails:

let xs = [3; 5; 9]
let ys = 1 :: xs     (* ys = [1; 3; 5; 9], xs still = [3; 5; 9] *)

ys and xs share the tail [3; 5; 9]. No copying occurred — only one new cons cell was allocated. This is a key efficiency property of functional lists: building a list with cons does not disturb existing lists.

The cons diagram

In the diagram notation:

:: --> :: --> :: --> :: --> []
 |      |      |      |
 1      3      5      9

Each :: is a cons cell. The rightward arrow points to the tail; the downward arrow points to the head. Taking the head or tail of a list is O(1) — each operation just follows one link.

The tail is not the last element; it is the list of all elements other than the head. The tail of [1; 3; 5; 9] is [3; 5; 9], and the tail of [9] is [].

Why this matters

Understanding the linked representation explains:

• Why cons is O(1): only one new cell allocated
• Why head/tail are O(1): following one pointer
• Why append is O(n): must copy the entire first list
• Why sharing is safe: OCaml values are immutable — no one can modify a shared tail