Let's go back to
our basic Node class and create three Node* pointers head,
x and y.
class Node
{ public:
int n;
Node* link;
};
...
Node* head, *x, *y;
At this point head, x and y are not pointing anywhere as they have not been initialised. Let us imagine now that we have created a linked list, where head points to the head of the list and x at the last item in the list (i.e. the one with the null pointer).
|
To create a new node, make y point at it, and initialise the node as follows:
y = new Node; y->n = 33; y->link = NULL;
We can add this new node at the head of the list as follows:
y->link = head; head = y;This works perfectly well even if the list is empty (i.e. the head pointer is NULL).
If we have a pointer to the tail node of the list, then adding a new node at the tail end is easy:
x->link = y;
 |
However, quite often the only list pointer we have access to is the head pointer. To get to the tail we have to scroll along the list until the end. We want a pointer that will stop while still pointing at the last node. Thus our termination condition is that the node's link field is NULL. Once we have a pointer to the end of the list, we can make it point to the node we want to add:
x = head; while (x->link != NULL) // assumes that head itself is not NULL x = x->link; x->link = y;
When removing a node, beware of memory leak; remember to give yourself a pointer to the node that is about to be removed before you lose your pointer to it:
Node* zap = head; // zap and head both point at the head node head = head->link; // move head along delete zap; // No memory leak
We now have the operations we need to implement a stack as a singly-linked list:
class Stack
{ public:
Stack() {top = NULL;}
void push(int);
int pop();
private:
Node* top; // assuming the Node class has already been defined
};
void Stack::push(int x)
{ Node* p = new Node;
p->n = x;
p->link = top;
top = p;
}
int Stack::pop()
{ if (top == NULL)
deal_with_underflow();
else
{ Node* zap = top;
top = zap->link;
int return_value = zap->n;
delete zap;
return return_value;
}
}
If we keep a pointer (here called rear) to the tail of the list, we can implement a queue also:
class Queue
{ public:
Queue() {front = NULL;} // if front is NULL, the queue is empty, whatever the value of rear may be
void add(int);
int remove();
private:
Node* front, *rear;
};
void Queue::add(int x)
{ Node* p = new Node;
p->n = x;
p->link = NULL;
if (front == NULL) // putting the first node into an empty queue
front = p;
else rear->link = p;
rear = p;
}
int Queue::remove()
{ if (front == NULL)
deal_with_underflow();
else
{ Node* zap = front;
front = zap->link; // if removing the final node, front becomes NULL
int return_value = zap->n;
delete zap;
return return_value;
}
}
Note that, in these implementations, all the data is kept on the heap. The only thing that a Stack object itself contains is a pointer (or two pointers in the case of the Queue). This has implications for the assignment operation and the copy constructor, which we will address in a later lecture.
The next trick is to add a node between two others. We have to make one node point to the new one, and the new node point to the next in the list. Assuming that x is pointing at the '99' node, then to add a node after 99 we use the following code:
y->link = x->link; // make the new node point at the 27 node x->link = y; // make the 99 node point at the new node
To perform the same operation, but starting from the head node, we have to stop at the node before the insertion point. Remember that a singly-linked list is a one way street!
x = head;
while (x->n != 99) // assumes that head is not NULL and that there is a 99 in the list
x = x->link;
y->link = x->link;
x->link = y;
 |
To remove a node from a list we have to do three things:
The order here is VERY important.
Let's assume that we want to delete the '99' node. To make the example easier, let's assume that there is a '99' node in the list, that it is not the head node, and that there are at least two nodes in the list. (In a real program, you cannot make such assumptions, of course.) The code for removing the '99' node is as follows:
x = head;
while (x->link->n != 99) // stop when you get to the
x = x->link; // node before 99
Node* zap = x->link;
x->link = zap->link;
delete zap; // avoid memory leakage
The above code will work, but expressions such as x->link->n
are not recommended. It is hard to keep track of what exactly you are doing
if you reference the node beyond the one you are pointing at. This would
be better:
Node* x = head, *zap = head->link; // we're assuming at least two nodes and 99 is not the head node
while(zap->n != 99) // we're assuming there is a 99 node
{ x = zap;
zap = zap->link;
}
// Now we've found it. zap points at it, x at the one before.
x->link = zap->link;
delete zap;
 |
Let's take one of the examples we began with - adding a node to the tail of the list - and turn it into a procedure. If we had a list with a pointer variable called head pointing at the head node, the call might be addnode(head, 33); The procedure might look like this:
void addnode(Node* h, int val)
{ Node* y = new Node; // Create a new node to put on the end
y->n = val;
y->link = NULL;
Node* x = h; // Find the tail node
while (x->link != NULL)
x = x->link;
x->link = y; // Link the new node to the tail node
}
What would happen if the list was empty, i.e. if the head pointer was NULL ? The procedure would get as far as x->link and crash, because x would be NULL - not pointing at anything. Presumably, if head were NULL, we would want it to be pointing at a new node by the end of the procedure. How about this?
void addnode(Node* h, int val)
{ Node* y = new Node; // Create a new node to put on the end
y->n = val;
y->link = NULL;
if (h == NULL) // special case - empty list
{ h = y;
return;
}
Node* x = h; // Otherwise, find the tail node
while (x->link != NULL)
x = x->link;
x->link = y; // Link the new node to the tail node
}
This looks OK, but it won't work. This is because h is a value parameter. Recall that a value parameter is like a local variable, so h is like a variable local to the addnode procedure, separate from the argument.
When the procedure gets called, as in addnode(head, 33); the value of head is passed over and becomes the initial value of h. So, if head is NULL, h also becomes NULL. In that case, addnode will build a new node, but will attach it to h, not to head. head will remain NULL (and you'll also have some memory leak since, when addnode returns, you lose your pointers to the new node).
If you want addnode(head, 33); to have the ability to change the value of the head pointer itself (not the thing it might be pointing at), you have to pass it by reference:
void addnode(Node*& h, int val)
Notes on R. Mitton's lectures by S.P. Connolly, edited by R. Mitton, 2000