What do nodes do?

In programming a node is a pointer to some data. For instance, if we allocate objects non-contiguously we can treat them as if they were allocated contiguously by storing pointers to those objects in a contiguous array:

foo* a[100];
for (int i=0; i<100; ++i) a[i] = malloc (sizeof(foo));

In the above example we have an array of foo nodes. The foo objects themselves are individually allocated on the heap but they need not be allocated contiguously. But this does not matter because an array is always allocated contiguously so the order of the objects is determined by the order of the nodes in the array. If we change the order of the nodes, we change the order of the objects, but the objects don't actually move. This is useful when the objects are large or complex because it means we can change their order much more efficiently just by moving the nodes.

As well as pointers, a node can also be defined as a structure:

struct node {
foo* data;
node* next;
};

Here, the node still points to an object but also points to another node, the next node in the sequence. In this case we don't need an array, we simply need to keep track of the first node in the sequence. This means we are no longer restricted by the array length; we can have as many or as few nodes as we require. Changing the order of the nodes is simply a matter of changing which data element each node points to. We can also insert and extract elements from the sequence by changing which node each node points to.

More complex data structures require additional node pointers. For instance, a bi-directional list requires two node pointers, one to the next element in the sequence and one to the previous element:

struct node {
foo* data;
node* next;
node* prev;
};


A binary tree node also has two node pointers:

struct node {
foo* data;
node* left;
node* right;
};


A binary tree node might also point to its parent node:

struct node {
foo* data;
node* parent;
node* left;
node* right;
};

A tertiary node has at least three node pointers:


struct node {
foo* data;
node* left;
node* middle;
node* right;
};


Nodes make it possible to construct highly-complex data structures regardless of where the data is physically allocated and the order in which it is allocated. The point is that we don't need to move any data around because the nodes themselves define the data structure. The nodes can be thought of as being metadata (data about data).

Any node that allows traversal to any other node in the structure can be used to keep track of the structure, however we typically use the node that provides the most efficient traversal. In a tree structure, that is always the root node. In a list, it is the head node.