1.1: The Node

The first data structure we look at is the node structure. A node is simply a container for a value, plus a pointer to a "next" node (which may be null).

Node<Element> Operations

make-node(Element v, Node next): Node

Create a new node, with v as its contained value and next as the value of the next pointer

get-value(Node n): Element

Returns the value contained in node n

get-next(Node n): Node

Returns the value of node n's next pointer

set-value(Node n, Element v)

Sets the contained value of n to be v

set-next(Node n, Node new-next): Node

Sets the value of node n's next pointer to be new-next

All operations can be performed in time that is \(O(1)\).

Examples of the "Element" type can be: numbers, strings, objects, functions, or even other nodes. Essentially, any type that has values at all in the language.

The above is an abstraction of a structure:

  structure node {
    element value     // holds the value
    node next         // pointer to the next node; possibly null
  }

In some languages, structures are called records or classes. Some other languages provide no direct support for structures, but instead allow them to be built from other constructs (such as tuples or lists).

Here, we are only concerned that nodes contain values of some form, so we simply say its type is "element" because the type is not important. In some programming languages no type ever needs to be specified (as in dynamically typed languages, like Scheme, Smalltalk or Python). In other languages the type might need to be restricted to integer or string (as in statically typed languages like C). In still other languages, the decision of the type of the contained element can be delayed until the type is actually used (as in languages that support generic types, like C++ and Java). In any of these cases, translating the pseudocode into your own language should be relatively simple.

Each of the node operations specified can be implemented quite easily:

// Create a new node, with v as its contained value and next as
// the value of the next pointer
function make-node(v, node next): node
  let result := new node {v, next}
  return result
end

// Returns the value contained in node n
function get-value(node n): element
  return n.value
end

// Returns the value of node n's next pointer
function get-next(node n): node
  return n.next
end

// Sets the contained value of n to be v
function set-value(node n, v)
  n.value := v
end

// Sets the value of node n's next pointer to be new-next
function set-next(node n, new-next)
  n.next := new-next
  return new-next
end

Principally, we are more concerned with the operations and the implementation strategy than we are with the structure itself and the low-level implementation. For example, we are more concerned about the time requirement specified, which states that all operations take time that is \(O(1)\). The above implementation meets this criteria, because the length of time each operation takes is constant. Another way to think of constant time operations is to think of them as operations whose analysis is not dependent on any variable. (The notation \(O(1)\) is mathematically defined in the next chapter. For now, it is safe to assume it just means constant time.)

Because a node is just a container both for a value and container to a pointer to another node, it shouldn't be surprising how trivial the node data structure itself (and its implementation) is.