The list Data Structure

par::list<T> is a persistent (immutable) singly-linked list. Operations such as push and pop do not modify the original list. Instead, they return a new list that may share structure with the old one. Unlike most C++ data structures (such as std::vector), copying a list is not expensive. Copying a list only copies a pointer to the head node, so it takes constant time.

This data structure is similar to lists in SML. It is particularly useful when writing functional-style algorithms where previous versions of a list must remain valid.

For example, starting with a list L containing the elements [3,1,2], writing L2 = L.push(5) produces a new list containig [5,3,1,2] without changing the value of L. Under the hood, persistent lists achieve this efficiently by sharing nodes that they have in common rather than creating deep copies.

A pair of persistent lists sharing three common nodes

Creating lists

Default Constructor Work Span 
list()
 $O(1)$ $O(1)$

Creates an empty list. 

par::list<int> L;   // empty list

Member Functions

empty Work Span 
bool empty()
 $O(1)$ $O(1)$
Returns true if the list is empty, false otherwise. 
par::list<int> L;
assert(L.empty());

L = L.push(42);
assert(!L.empty());
push Work Span 
list push(T x)
 $O(1)$ $O(1)$

Returns a new list with x added to the front. The original list is unchanged. 

par::list<int> L;
auto L1 = L.push(3);
auto L2 = L1.push(2);

//  L == []
// L1 == [3]
// L2 == [2, 3]
pop Work Span 
std::pair<T, list> pop()
 $O(1)$ $O(1)$

Returns the first element and the remainder of the list. The list must not be empty, or pop() is undefined. 

par::list<int> L;
L = L.push(3).push(2).push(1);  // [1, 2, 3]

auto [x, tail] = L.pop();
//    x == 1
// tail == [2, 3]
peek Work Span 
T peek()
 $O(1)$ $O(1)$

Returns the first element of the list without removing it. The list must not be empty, or peek() is undefined. 

par::list<int> L;
L = L.push(10).push(20);  // [20, 10]

int x = L.peek();  // x == 20
length / size Work Span 
std::size_t length()
std::size_t size()
 $O(n)$ $O(n)$

Returns the number of elements in the list. 

par::list<int> L;
L = L.push(3).push(2).push(1);

std::size_t n = L.size();    // n == 3
std::size_t m = L.length();  // also 3

Conversions

to_sequence Work Span 
par::array_sequence<T> to_sequence()
 $O(n)$ $O(n)$

Returns a par::array_sequence containing the elements of the list in order. 

par::list<int> L;
L = L.push(3).push(2).push(1);  // [1, 2, 3]

par::array_sequence<int> S = L.to_sequence();  // S == [1, 2, 3]
from_sequence Work Span 
static list from_sequence(const sequence<T> auto& S)
 $O(|S|)$ $O(|S|)$

Constructs a list containing the elements of S in the same order. 

par::array_sequence<int> S{1, 2, 3};

auto L = par::list<int>::from_sequence(S); // L == [1, 2, 3]