## Adding to the back of a list

Adding to the front of our bare-bones linked lists is very natural. Adding to the back takes more work! You have two basic cases, which really need to be handled separately:

- the original list
`L`

is empty

In this case you must create a new node and change the actual pointer L to point to that new node. - the original list
`L`

is non-empty

In this case the pointer`L`

will remain unchanged. Instead, you will have to traverse the list in order to get to the last node, and then set the last node's`next`

to point to a new node that you create.

Here's a nice little implementation of an `add2back`

function that works in just this way.

```
#include <iostream>
using namespace std;
struct Node {
string data;
Node *next;
};
Node* add2front(string d, Node *L) {
Node *T = new Node;
T->data = d;
T->next = L;
return T;
}
Node* add2back(string d, Node* L) {
Node* newlast = new Node;
newlast->data = d;
newlast->next = NULL;
if (L == NULL) { // empty L case
L = newlast;
} else { // non-empty L case
Node* last = L;
while(last->next != NULL)
last = last->next;
last->next = newlast;
}
return L;
}
int main() {
Node *L = NULL;
string s;
while(cin >> s && s != ";")
L=add2back(s,L);
for(Node* p = L; p != NULL; p = p->next)
cout << p->data << ' ';
cout << endl;
return 0;
}
```

## Recursion and linked lists

Let's look carefully at recursion and linked lists. An essential property of a recursive solution to a problem is that solving the initial problem involves solving a smaller version of the same problem. How does this fit with linked lists? Very nicely, actually. Remember that a list is represented by a variable `L`

that is a pointer — a pointer to the first node in the list. Now, if you look at the `next`

member of that first node (i.e. look at `L->next`

), what is that? It's a pointer — a pointer that represents the list of everything after the first node.

We saw the example of such a recursive call with the recursive version of length:

```
int length(Node* L) {
if (L == NULL)
return 0;
return 1 + length(L->next);
}
```

Hopefully this makes sense now that we see that `L`

is the list `L->next`

plus one extra node, the node with data value 5. Most other recursive functions with lists work the same way. For example, suppose we want to calculate the sum of the elements of list L. In the above example, it is 5 + the sum of 9,2,8,4. In other words, `L->data`

plus the sum of the elements of the list `L->next`

. So the recursive case is:

`return L->data + sum(L->next);`

If you're printing out the list L from the example above recursively, you think of printing 5, then printing the list 9,2,8,4. So the recursive case for `print(L)`

is

```
cout << L->data << ',';
print(L->next);
```

If you want to find the maximum element of L recursively, you think about comparing the data value of the first node with the maximum of the list of the remaining elements. Assuming you have a function `int max(int,int);`

, you'd have something like this:

`return max(L->data,maxelt(L->next));`

Of course to make complete recursive functions, you need base cases as well.

```
int sum(Node* head) {
if (head == NULL)
return 0;
else
return head->data+sum(head->next);
}
void print(Node* head) { //requires head non-empty
if (head->next == NULL)
cout << head->data;
else {
cout << head->data << ',';
print(head->next);
}
}
int maxelt(Node* head) {// requires head non-empty
if (head->next == NULL)
return head->data;
else
return max(head->data,maxelt(head->next));
}
```

## A recursive add2back function

We can also view add2back recursively. Adding to the back of list `head`

is actually the same as adding to the back of list `head->next`

Moreover, if `head`

is empty, adding to the back is the same as adding to the front. Those two observations give us the following recursive formulation which, I hope you'll admit, is really beautiful!

```
Node* add2back(string d, Node* head) {
if (head == NULL)
return add2front(d,head);
head->next = add2back(d,head->next);
return head;
}
```

## Tailpointer — easy add2back

The first node in a list is often called the *head* of the list and the last node is often called the *tail*. Adding a new node to the front of the list is easy, because we need only change the pointer to the head to point to our new node, and set our new node's `next`

to point to the old head node. Adding a new node to the back of the list is more difficult, because we must first create a temporary pointer and set it to point to the last node in the list (tail), and this means traversing our entire list from front to back. This is a lot of work if you're going to be adding new nodes to the back frequently, so it is sometimes nice to keep a second pointer that points to the tail of the list, along with the pointer to the head of the list that we always have. So, if we're talking about linked lists of `int`

s, we might have something like the following, which simply reads positive ints from the user and prints them back out in the same order they were entered:

```
void add2front(int val, Node* &head, Node* &tail) {
Node* p = new Node;
p->data = val;
p->next = head;
if (head == NULL)
head = tail = p;
else
head = p;
}
void add2back(int val, Node* &head, Node* &tail) {
if (head == NULL)
add2front(val,head,tail);
else {
tail->next = new Node;
tail = tail->next;
tail->next = NULL;
tail->data = val;
}
}
int main() {
Node* head, *tail;
head = tail = NULL;
cout << "Enter ints, end with 0: ";
int temp;
while(cin >> temp && temp > 0)
add2back(temp,head,tail);
cout << "you entered: " << endl;
for(Node* p = head; p != 0; p = p->next)
cout << p->data << endl;
return 0;
}
```

**Alternate implementation:**

```
void add2back(int val, Node* &head, Node* &tail) {
if (head == NULL)
add2front(val,head,tail);
else
add2front(val,tail->next,tail);
}
```

## Doubly Linked Lists (OFF THE SYLLABUS)

One thing that makes linked lists a pain sometimes is that you can only move in one direction: from head to tail. If you find yourself wanting to traverse a list in both directions, you simply need to add a second pointer to each node pointing to the *previous* node in the list. This is called a doubly linked list since, obviously, each node has two links rather than one. Our Node struct for a doubly linked list of strings would look like this:

```
struct Node {
string data;
Node *next, *prev;
};
```

Now we need to think about some of our basic list functions all over again. For the sake of practice, let's assume that we want to add to the back often, so we'll adopt the previous scheme of keeping pointers to both the front and the back of our list.

```
struct Node {
string data;
Node *next, *prev;
};
struct List {
Node *head, *tail;
};
List add2front(int val, List L) {
Node* p = new Node;
p->data = val;
p->next = head;
p->prev = 0;
if (L.head == 0)
L.head = L.tail = p;
else
{
L.head->prev = p;
L.head = p;
}
return L;
}
int main() {
List L;
L.head = L.tail = 0;
cout << "Enter ints, end with 0: ";
int temp;
while(cin >> temp && temp > 0)
add2back(temp,L);
cout << "In order, you entered: " << endl;
for(Node* p = L.head; p != 0; p = p->next)
cout << p->data << ' '; cout << endl;
cout << "Reversed, you entered: " << endl;
for(Node* p = L.tail; p != 0; p = p->prev)
cout << p->data << ' ';
cout << endl;
return 0;
}
List add2back(int val, List L) {
if (L.head == 0)
L = add2front(val,L);
else {
Node *p = new Node;
p->data = val;
p->next = 0;
p->prev = L.tail;
L.tail->next = p;
L.tail = p;
}
return L;
}
```

## Problems

Assuming you have files dbpoint.h and dbpoint.cpp that provide a nice implementation of a struct

`Point`

, write a program that reads a comma separated list of data points from the user (terminated by a semi-colon) and then repeatedly asks the user for a reference point, and responds by printing out average of the distances of the data points from the reference point.

**Note:**By all means look at the code from the previous lesson that shows how to build and traverse (to print) a linked list.`~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453`

Build on the above problem code, and print the list out in the same format it was entered: comma-separated, semi-colon terminated. A run of the program might look like this:

`~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; List read was (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453`

Build on the above problem code, and print the last element in the list. A run of the program might look like this:

`~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; Last element is (-0.8,-1.1) (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453`

Build on the above problem code, and print the next-to-last element in the list. A run of the program might look like this:

`~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; Next to last element is (3.1,0.9) (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453`

- Try implementing an
`insert_in_order`

function for doubly linked lists. Try implementing a

`deleteNode`

function, which takes a pointer to a node in a doubly linked list and and removes that node from the list. Don't forget to delete the node when you're done with it!