Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Data Structures

Lists in Erlang

Work with Erlang lists: linked-list structure, head and tail, cons, append, the lists module, sorting, searching, zipping, proper lists and performance traps.

The list is the workhorse collection in Erlang. It is an ordered sequence of any terms, implemented as a singly linked list. Everything about list performance follows from that: adding to the front is free, while reaching the end or the Nth element takes time proportional to the position.

Building lists

ERLANG
1> [1, 2, 3].
[1,2,3]
2> [a, "text", {tuple}, 3.5, [nested]].
[a,"text",{tuple},3.5,[nested]]
3> [].
[]
4> lists:seq(1, 5).
[1,2,3,4,5]
5> lists:seq(0, 20, 5).
[0,5,10,15,20]
6> lists:duplicate(3, x).
[x,x,x]

Elements may be of different types. A list is written with square brackets, and [] is the empty list, also called nil.

Head, tail and cons

Internally a list is a chain of cells; each cell holds one element (the head) and a pointer to the rest (the tail). The | operator builds or splits a cell:

ERLANG
1> L = [2, 3].
[2,3]
2> [1 | L].
[1,2,3]
3> [H | T] = [1, 2, 3].
[1,2,3]
4> hd([10, 20, 30]).
10
5> tl([10, 20, 30]).
[20,30]
6> [0, 1 | [2, 3]].
[0,1,2,3]

Adding an element to the front, [X | L], creates only a new cell and shares the old list, so it takes constant time and no copying. Because of this sharing, "modifying" a list never changes the original.

flowchart LR
    A["1"] --> B["2"] --> C["3"] --> D["[]"]
    X["0"] -.-> A

Consing 0 onto [1,2,3] reuses the old cells.

A list that ends in [] is a proper list. [1 | 2] is an improper list whose tail is not a list. It is legal but most library functions reject it; avoid it unless you build iolists.

Joining and splitting

ERLANG
1> [1, 2] ++ [3, 4].
[1,2,3,4]
2> [1, 2, 3, 2, 1] -- [2, 1].
[3,2,1]
3> lists:append([[1], [2, 3], [4]]).
[1,2,3,4]
4> lists:flatten([1, [2, [3, 4]], 5]).
[1,2,3,4,5]
5> lists:split(2, [a, b, c, d]).
{[a,b],[c,d]}
6> lists:sublist([1, 2, 3, 4, 5], 2, 3).
[2,3,4]
7> lists:nth(2, [a, b, c]).
b

lists:nth/2 is 1-based and walks the list, so avoid it in loops. If you find yourself indexing a lot, a tuple, a map or the array module may fit better.

The lists module tour

Information

ERLANG
1> length([a, b, c]).
3
2> lists:member(b, [a, b, c]).
true
3> lists:sum([1, 2, 3]).
6
4> lists:max([3, 9, 2]).
9
5> lists:min([3, 9, 2]).
2
6> lists:last([1, 2, 3]).
3

Reordering

ERLANG
1> lists:reverse([1, 2, 3]).
[3,2,1]
2> lists:sort([3, 1, 2]).
[1,2,3]
3> lists:sort(fun(A, B) -> A >= B end, [3, 1, 2]).
[3,2,1]
4> lists:usort([3, 1, 3, 2, 1]).
[1,2,3]
5> lists:keysort(2, [{a, 3}, {b, 1}, {c, 2}]).
[{b,1},{c,2},{a,3}]

usort/1 sorts and removes duplicates. The lists:key* functions work on lists of tuples by position:

ERLANG
1> Pets = [{cat, 4}, {dog, 7}, {fish, 1}].
2> lists:keyfind(dog, 1, Pets).
{dog,7}
3> lists:keyfind(bird, 1, Pets).
false
4> lists:keydelete(cat, 1, Pets).
[{dog,7},{fish,1}]
5> lists:keystore(dog, 1, Pets, {dog, 8}).
[{cat,4},{dog,8},{fish,1}]

Lists of {Key, Value} tuples are called property lists or association lists, and are fine for small tables. For bigger ones use maps.

Combining

ERLANG
1> lists:zip([1, 2, 3], [a, b, c]).
[{1,a},{2,b},{3,c}]
2> lists:unzip([{1, a}, {2, b}]).
{[1,2],[a,b]}
3> lists:zipwith(fun(A, B) -> A * B end, [1, 2, 3], [4, 5, 6]).
[4,10,18]
4> lists:merge([1, 3, 5], [2, 4]).
[1,2,3,4,5]
5> lists:join(", ", ["a", "b", "c"]).
["a",", ","b",", ","c"]

Higher-order list functions

map, filter, foldl, any, all, partition, takewhile, dropwhile, flatmap, foreach take funs; see funs and list comprehensions for a nicer syntax.

Performance notes

Operation Cost
[X | L] O(1)
hd/1, tl/1 O(1)
length/1 O(N)
L ++ R O(length of L)
lists:nth(N, L) O(N)
lists:reverse/1 O(N)

Do not call length(L) repeatedly in a loop or append single items with ++ in a recursive loop. Build the list in reverse with cons, then reverse once.

Stand-ins in JavaScript

JavaScript arrays are not linked lists, so this snippet builds a real cons-cell list to show sharing. It is not Erlang.

JS Stand-in: cons cells and sharing (JavaScript, not Erlang)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

JS Stand-in: keyfind, keysort and usort (JavaScript, not Erlang)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the cost of [X | List]?

    Consing creates one new cell that points to the old list.
  2. 2. What does lists:usort([3,1,3,2,1]) return?

    usort sorts and removes duplicates.
  3. 3. Which is true of lists:nth(N, List)?

    Lists are linked, so reaching the Nth element takes N steps; nth is 1-based.
  4. 4. What is an improper list?

    [1 | 2] ends in a non-list tail, so most list functions reject it.

Summary

  • Lists are singly linked: prepend and head/tail are O(1); length, nth and append-to-end are linear.
  • [H | T] builds and splits lists; ++ joins; -- removes.
  • The lists module offers sort, usort, reverse, zip, split, member, key* functions and more.
  • Build lists by prepending and reverse once; avoid ++ in loops.
  • Lists of {Key, Value} tuples are fine for small tables; use maps for larger ones.

Next: List Comprehensions