The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Linked lists Revenge of the Node
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Revenge of the Node

As usual when we write a new class, we'll start with the instance variables, one or two constructors and toString so that we can test the basic mechanism of creating and displaying the new type.

struct Node {

    public:

      int cargo;
      Node* next;

      Node () {
          cargo = 0;
          next = null;
      }

      Node (int Cargo, Node Next) {
            cargo = Cargo;
            next = Next;
      }

      pstring toString () {
        pstring s;
        for(; n; n/=10)
        s = char(n%10 + '0') + s;
        return s;
      }
}

The declarations of the instance variables follow naturally from the specification, and the rest follows mechanically from the instance variables. The expression cargo + "" is an awkward but concise way to convert an integer to a String.

To test the implementation so far, we would put something like this in main:

    Node node = new Node (1, null);
    cout << node.cargo;

The result is simply

1

To make it interesting, we need a list with more than one node!

    Node node1 = new Node (1, null);
    Node node2 = new Node (2, null);
    Node node3 = new Node (3, null);

This code creates three nodes, but we don't have a list yet because the nodes are not linked. The state diagram looks like this:

To link up the nodes, we have to make the first node refer to the second and the second node refer to the third.

    node1.next = node2;
    node2.next = node3;
    node3.next = null;

The reference of the third node is null, which indicates that it is the end of the list. Now the state diagram looks like:

Now we know how to create nodes and link them into lists. What might be less clear at this point is why. Now that we're a little more familiar with the use of the struct Node, we can now introduce you to the other style of notation. The use of dot notation can be replaced by the more well-known ->

For example:

    node1->next = node2;
    node2->next = node3;
    node3->next = null;

Home Linked lists Revenge of the Node

Last Update: 2005-12-05