Continuing with the discussion of trees, representations based on linked structures are normally preferred
- more flexible than indexed ones;
- more efficient structure modifications.
There are three main ones
Pointer to children
If each node has at most $d$, it is possible to keep in each node a pointer to each of the possible children. In the case of $d \geq 2$, if a child is absent we set the pointer to null. Required space is $O(n \times d)$, which for constant $d$ is $O(n)$.
Child list
If the maximum number of children is not known a priori, it is possible to associate each node with a list of pointers to its children; this list can in turn be represented in a linked or indexed manner. Required space is $O(n)$ regardless of the number of children of a node.
First child next sibling
As a variant of the previous one without having to keep the additional data structure (the child list) For each node a pointer to the first child (set to null if there are no children) and a pointer to the next sibling
Required space O(n) To scan all the children of a node simply go down to the first child and then scan all subsequent siblings by jumping from sibling to sibling.