◀ ▲ ▶Branches / Theoretical-computer-science / Data-structures / Definition: Linked List, List Nodes

Definition: Linked List, List Nodes

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)$.

Example

A list with three linked nodes:

(Source: Uploaded by Lasindi: Public Domain)

Mentioned in:

Definitions: 1

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition