None.

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

## 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
{
};```
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!
• Problem I: Customer orders come in to a warehouse like this: (customerID, itemNumber, quantity) and these items are prefetched and brought to a holding area. Then the command to ship to customer identified by ID comes in, and all the prefetched items are shipped to that customer in a single box. Assume the total number of items in the order (sum or quantities) is all that's required to determine the box size. Assume each customerID is a unique string of upper-case letters , e.g. "JONEXXK" or "BROWKZL".
```  A. Read from user a sequence of commands:

maxq <-- prints out the (customerID, itemNumber, quantity) of order
with the largest quantity seen so far.  If no items have

quit <-- quits program

B. Assume that the system will not need to process more than 1000 orders
before quitting.  Read a sequence of commands:

print <-- writes out all the orders (don't care what order they appear)

quit

C. Assume that the system will not need to process more than 1000 orders
before quitting.  Read a sequence of commands:

print <-- writes out all the order summaries for each customer, like
this:

BROWKZL
108520 4
228700 1
920022 1
Total: 6
JONEXXK
800231 2
920022 1
998735 10
Total: 13

Customers should be listed alphabetically by CustomerID.

quit <-- quits program

D.  Make no assumption about number of orders.  Now we add a command
to ship to a customer, which should print a summary of the order,
and remove the shipped orders from storage.  If a customerID is
entered with the ship command for which there are no unshipped
orders, print "No orders pending!".

ship CustomerID
quit```
• Problem II: Your job is to read in a bunch of (alphacode,1/C..4/C,M/F,100m-sprint-times) data lines like:
`  (183488,4/C,F,11.33)`
and process them.
```  A. print the average time

B. print average times for each class/gender (8 total)

C. print the alphacodes/class/geneder/time of the first 20 data lines
(read in but ignore all subsequent lines) in increasing order of
times.  If multiple data lines have the same time, they should appear
in increasing alphacode order.

D. after reading the data lines, you are given range (rmin,rmax)
print the alphacodes/class/geneder/time  of all mids whose
100m-sprint-time lies within the range.
```

## 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!