Reading

None.

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:
  1. 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.
  2. 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;
};

void add2front(string d, Node *&L)
{
  Node *T = new Node; 
  T->data = d; 
  T->next = L;
  L = T;
}
 
void 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;
  }
}
 
int main()
{
  Node *L = NULL;
  string s;
  while(cin >> s && s != ";")
    add2back(s,L);
  
  for(Node* p = L; p != NULL; p = p->next)
    cout << p->data << ' ';
  cout << endl;

  return 0;
}

If we want to take advantage of the add2front function we already have, we can simplify this code a little bit ... or at least we can make it shorter. I'll let you decide for yourselves whether or not you think it is simpler. 

void add2back(string d, Node* &L)
{
  if (L == NULL)
    add2front(d,L);
  else
  {
    Node* last = L; 
    while(last->next != NULL)
      last = last->next;
    add2front(d,last->next);  
  }
}

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. So, for example, in the following linked list The pointer L is the list 5,9,2,8,4, and just as much the pointer L->next is the list 9,2,8,4. This makes it natural for a recursive function called with argument L to make its recursive call with argument L->next. 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* L)
{
  if (L == NULL)
    return 0;
  else
    return L->data + sum(L->next);
}
 
void print(Node* L) // requires L non-empty
{
  if (L->next == NULL)
    cout << L->data;
  else
  {
    cout << L->data << ',';
    print(L->next);
  }
}
 
int maxelt(Node* L) // requires L non-empty
{
  if (L->next == NULL)
    return L->data;
  else
    return max(L->data,maxelt(L->next));
}

A recursive add2back function

We can also view add2back recursively. Adding to the back of list L is actually the same as adding to the back of list L->next Moreover, if L 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! 
void add2back(string d, Node* &L)
{
  if (L == NULL)
    add2front(d,L);
  else
    add2back(d,L->next);  
}

Tailpointer — easy add2back

The first node in a list is often called te 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 ints, 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);
}

Remember structs! (OFF THE SYLLABUS)

When we keep both head and tail pointers, a list no longer consists of a single object of type Node*. Instead, it consists of two objects, local variables head and tail. Whenever we see that a single entity in a program consists of several local variables like this, we should begin to think about wrapping them up in a struct. 
struct List
{
  Node *head, *tail;
};
With this declaration, a list in our program is an object of this new type "List", and the above program changes to: 
void add2front(int val, List &L)
{

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

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;
};
 
void 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;
  }
}
 
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 << "Reveresed, you entered: " << endl;
  for(Node* p = L.tail; p != 0; p = p->prev)
    cout << p->data << ' ';
  cout << endl;
  return 0;
}
 
void add2back(int val, List &L)
{
  if (L.head == 0)
    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;
  }  
}

Problems

  1. 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
  2. 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
  3. 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
  4. 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
  5. Try implementing an insert_in_order function for doubly linked lists.
  6. 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!