Reading

None.

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;
  }  
}

All-together now: tying up the whole semester

When you have a new problem to solve, you should ask yourself: do I need to store stuff beyond local variables? should I use an array? should I use a 2D array? should I use a struct? should I use a linked list? Do I need to sort? The answers to these questions will help shape your solution. Below are two Problem Scenarios, each with several variations of what problem actually needs to be solved. Annotate each with your answers to the above questions, along with justifications!

Problems

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