Linked lists

What’s a linked list?

1.  Let V be a set of values and A be a set of “addresses”.
2. Say a map f is a “linked list element” compatible with values V  and addresses A if and only if f(value)∈ V and f(next) ∈  A. A linked list element map can have an arbitrary additional domain – we don’t specify that here.
3. Let L: A→ X where X is a set of  linked list elements compatible with V and A.  L associates addresses with linked list elements.
4. Given any a ∈ A we want to be able to trace the linked list with “a” as the head element. Define E(L,a,0) = a and  E(L,a,n+1) = (L(E(L,a,n)))(next).  The expression (L(E(L,a,n)))(next) can be unwrapped to understand it better (L(E(L,a,n)))(next) = (L(a’))(next) where E(L,a,n) = a’. Then (L(a))(next) = f(next) where L(a)=f is a linked list element. So the final value is some a”, an element of A.
5. Say (L,a) is a linked list iff for every element a’∈A s.t. L(a’) is defined,  there is some non-negative n so that E(L,a,n) = a’
6. Say (L,a) is a circular linked list iff it is a linked list and for some n, E(L,a,n+1) = a.

Finite sequences of length n>0 can be represented mathematically as maps u:{0, … n-1}→ Y for some set Y.   If  (L,a) is a circular linked list, define u(0) = L(a)(value) and  u(n+1) =  L(E(L,a,n+1))  if E(L,a,n+1)=  a, and undefined otherwise.