Continuing with the discussion of trees, representations based on linked structures are normally preferred
- more flexible than idicised 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 from 2 if a child is absent we place the pointer to Null Required space O(n*d) which for d constant 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 indexed manner, required space 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.