A list node is a data structure, consisting of two elements:
\[\mathtt{node}:=\cases{ \mathtt{content:Abstract Type;}\\ \mathtt{next:}\uparrow\mathtt {node};}\]
A linked list is a finite group of nodes \(\mathtt{n_1,n_2,\ldots,n_k}\), such that
\[ \mathtt{n_i\uparrow.next}= \cases{ \mathtt{n_{i+1},\quad 1\le i\le k-1}\\ \mathtt{\boxtimes,\quad i=k} }, \]
i.e. the pointer \(\mathtt{\uparrow.next}\) of the \(i\)-th node "points" to the \((i+1)\)-th node. The last node points to nothing, which is denoted by \(\boxtimes\) (sometimes also denoted by \(\mathtt{NIL}\) = "not in list").
A linked list of \(k\) nodes is denoted by \((n_1,n_2,...,n_k)\).
A list with three linked nodes:
(Source: Uploaded by Lasindi: Public Domain)
Definitions: 1