Nodes

At the heart of lists (and several other data structures) is the concept of a node. Before we go any further, let us consider this idea for a while.

To begin with, we shall create a few strings:

>>> a = "eggs"
>>> b = "ham"
>>> c = "spam"

Now you have three variables, each with a unique name, a type, and a value. What we do not have is a way of saying in which way the variables relate to each other. Nodes allow us to do this. A node is a container of data, together with one or more links to other nodes. A link is a pointer.

A simple type of node is one that only has a link to the next node.

Of course, knowing what we do about pointers, we realize that this is not entirely true. The string is not really stored in the node, but is rather a pointer to the actual string:

Thus the storage requirement for this simple node is two memory addresses. The data attribute of the nodes are pointers to the strings eggs and ham.