Node

Even though the few tricks with a set class can make an array dynamic it still has to relie on the creation of a new array. Dynamic structures (ones that can take up a variable amount of memory at a time) can easily be made with a simple class called a Node. A Node consists of whatevery it is to hold, in this case an interger, and a pointer/reference to another Node. Think about it. A Node can point to another Node which can point to another Node ad infinitum. Since objects which pointers refer to are created when needed, new Nodes can be added or removed as they are needed. If a bunch of Nodes are linked together they form a sort of list. Hence the new container class a Linked List. Here is the definition of a Node.

struct Node      //a struct is just a class with everthing public
{
   Node(int i=0, Node* n=NULL) : data(i), link(n) {} 
   int data;
   Node* link; 	 
};

Node

a class that contains an element and a reference to another Node

head

a reference to a Node that is the begining of a list

tail

a reference to a Node that is the ending of a list

cursor

a reference to a Node that has general purposes in a list, similar to i in for loop with an array

precursor

a reference to a the Node that is before the Node which cursor points to

Before a list can be created the nature of the Node must be known, and before that just two commnets. First it is easier to link Nodes "backwards". By adding Nodes at the front instead of its own link, traversing the list to the get to the end is avoided. Of course a tail could keep track of it. However that is a another variable to worry about, and so it would not avoid the care needed for dealing with the list backwards. The second point is to use pointers. The allow simple general usage of Nodes without falling into hardcoding traps. E.g. to get the third Node just traverse three of them instead of head.link.link.link.data;. Here is a simple list holding the numbers one, two, and three.

Node *head, *cursor;
head = cursor = NULL;
*head = new Node(3, NULL);
*cursor = new Node(2, head);
head = cursor;
*cursor = new Node(1, head);
head = cursor;

Since Nodes deal with dynamic memory, programming is tricky. Make sure to trace code so that it functions correctly. Also when tracing keep track of your memory. In C++ any memory the programmer allocate must also be deleted by them. In Java loose memory is garbaged collected, but a programmer must still be trifty. See Tracing Dynamic Memory for some tips.

Here is the same list, but this time loops are used and the Nodes are deleted. Notice how the general form of a for loop is used with the deletion. It utilizes the parts of the for defined as start value, test value, and increament value.

Node *head, *cursor;
head = cursor = NULL;
for(int i=3; i>=1; i--)
{
   cursor* = new Node(i, head);
	 head = cursor; 
}

That's just about it for Nodes. The next step is to created a Linked List container consisting of Nodes. 


Prev --
Back to Portal --
Next