Dynamic Circular Arrays Top Singly Linked-Lists Contents

Nodes

Synopsis

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.

Structure

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
        //operations
        ...
        }

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

Vocabulary

The terms used in describing a node are:

value
The value stored in the node.
next
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.
prev/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.
left/right
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.

Supports

A node is used to implement:

Dependencies

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.

Operations

get-value

This operation returns the value stored in the node.

set-value

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

get-next/get-prev/get-left/get-right

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

set-next/set-prev/set-left/set-right

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

Traversals

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

lusth@cs.ua.edu


Dynamic Circular Arrays Top Singly Linked-Lists Contents