jonnifyelixir
F4 / F4.01 / cons

F4.01 · part 1 of 3

Cons cells & the shape of a list

A cons cell is a pair: a head and a pointer to the tail. Building a list with [head | tail] makes one new cell that points at an existing list — so prepending is O(1) and the old list is shared, never copied. Reading the head or tail is O(1) too. Appending is the expensive one: it must copy the whole left-hand list.

Three operations on [1, 2, 3], and what each does to the cells. Watch which cells are reused and which are copied.

Three operations In code

Three operations

Prepending adds one cell at the front and shares the rest. Head and tail only read an existing cell. Appending walks to the end, copying every cell on the way, because the original cells already point somewhere. Select each and see the cost.

The operation · select one

0 1 2 3 [] 99 one new cell points at the existing list — nothing is copied 

      

      
result: [0, 1, 2, 3]  ·  cost: O(1)

    

    
Prepend and read are cheap because they touch one cell. Append is linear because the cells of the
      left list already point at their own tails, so the runtime must build fresh copies to redirect them.

  


  

    
In code

    

      
The cons operator | builds and destructures cells. hd/1 and
        tl/1 read them; pattern matching does the same in a function head. The
        ++ operator concatenates by copying its left operand.

    

    
list = [1, 2, 3]

[0 | list]      # prepend  => [0, 1, 2, 3]   · O(1), shares list
hd(list)        # head     => 1              · O(1)
tl(list)        # tail     => [2, 3]         · O(1)
list ++ [99]   # append   => [1, 2, 3, 99]  · O(n), copies list

case list do
  [head | tail] -> {head, tail}   # {1, [2, 3]}
  [] -> :empty
end

    

      

        
The idea

        
A list is a value and the rest of the list — a head and a tail, all the way down to [].

      

      
      

        
In Elixir

        
[h | t] builds or matches a cell; prepend shares the old list, append copies it.

      

    

    
Next: recursion over lists —
      the head-and-tail split is exactly how you walk one.

  


  

    
References

    
Primary sources for this lesson, and where it connects in the course.

    

      
Sources

      
      
Related in this course