# Dynamic Data Structures II

## Adding nodes to a list

Let's go back to our basic Node class and create three `Node*` pointers head, x and y.

```class Node
{ public:
int n;
};

...

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).

### Creating a new node

To create a new node, make y point at it, and initialise the node as follows:

```y = new Node;
y->n = 33;

We can add this new node at the head of the list as follows:

```y->link = head;
```
This works perfectly well even if the list is empty (i.e. the head pointer is NULL).

### Adding at the tail of the list

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

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
delete zap;		// No memory leak
```

### Stack and Queue again

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;
top = p;
}

int Stack::pop()
{	if (top == NULL)
deal_with_underflow();
else
{	Node* zap = top;
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
int remove();
private:
Node* front, *rear;
};

{	Node*	p = new Node;
p->n = x;
if (front == NULL)	// putting the first node into an empty queue
front = 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.

### Adding nodes in the middle of the list

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

### Removing nodes from the middle of a list

To remove a node from a list we have to do three things:

1. use a handle pointer to keep hold of the unwanted node
2. make the node before the unwanted node point to the node after the unwanted node
3. delete the unwanted node

The order here is VERY important.

• If you don't use the 'handle' pointer, the unwanted node will 'float away' when you close the gap, causing a memory leak.
• if you delete the unwanted node before closing the gap, you will lose the pointer to the bottom end of the list.

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
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;
}
// Now we've found it. zap points at it, x at the one before.
delete zap;
```

### Pointers as parameters

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;
Node* x = h;                 // Find the tail node
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;
if (h == NULL)               // special case - empty list
{   h = y;
return;
}
Node* x = h;                 // Otherwise, find 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)