Dynamic Circular Arrays Top Singly Linked-Lists Contents



A node is a simple data structure that bundles together a value and a set of node pointers, each of which point to a node or to nothing. At its simplest, there is but a single node pointer.

To signify that a node pointer points to nothing, a sentinal value, usually named null or nil, is stored in the variable representing the node pointer.

Pictorially, a node is often drawn using a box to represent a node with arrows representing the value and node pointers. Usually, the value pointer is drawn in the downward direction:

Here, the value is "elephant" and a single node pointer is shown, set to null.


The typical node object holds a single value pointer and some number of node pointers. As an example, when nodes are used to build a singly linked-list, a single node pointer, usually named next, is sufficient.

    class node
        var value = ?;          //points to the stored value
        var next = ?;           //optional: for singly/doubly linked-lists
        var prev = ?;           //optional: for doubly linked-lists
        var left = ?;           //optional: for binary trees
        var right = ?;          //optional: for binary trees

The initializers for value and the node pointer(s) are expected to be passed as arguments to the constructor.


The terms used in describing a node are:

The value stored in the node.
In the case of a node with a single node pointer that is used to implement a singly linked-list, the node pointer is usually named next.
In the case of a node with two node pointers that is used to implement a doubly linked-list, the two node pointers are commonly named prev (for previous) and next.
In the case of a node with two node pointers that is used to implement a binary tree, the two node pointers are often named left and right.


A node is used to implement:


A node is a fundamental data structure often provided by the language processor or, if not provided, easily constructed using a heterogeneous array or object. A heterogeneous array can hold elements of different types (e.g. the first element can be an integer, the second a string, and so on). In the case of a heterogeneous array, the first slot can hold the value and subsequent slots can hold the node pointers.



This operation returns the value stored in the node.


This operation updates the value in the node with the given value.


This operation returns the node that is stored in the associated node pointer.


This operation updates the associated node pointer with the given node. The actual names of the operations depend on the number of node pointers.


Nodes, having usually one value pointer, are not traversed.

Concept Inventory

  1. Generally, a node pointer points to...
    1. another node
    2. a value
    3. a string


Dynamic Circular Arrays Top Singly Linked-Lists Contents