There are three parts to this assignment: two implementations of linked lists and an implementation of a queue using stacks.

1) [15 points] Implement a singly linked-list class for strings similar to the one of week IV's lab. This implementation, however, should always maintain a tail pointer to the last node in the list. Run your code with the sequence of method invocations in ~lorenz/cs35-2/hw3/test-sequence.1; you may, however, want to design more thorough test cases while debugging. Be sure to recover from errors.

a) Provide methods for:

public void insertHead(String s);

-inserts s at the head of the list

public String deleteHead();
-removes the head of the list and returns it

public void append1(String s);
-appends s at the tail of the list.

public void print();
-prints the list

b) What is the time complexity of append1, insertHead, and deleteHead for list implementations with and without tail pointers? That is, given that the list is of length n, give the big-O running time for the three methods for an implementation that maintains pointers to both the list's head and tail and for an implementation that only maintains the list's head.

2) [20 points] Build an implementation of doubly linked lists (also for strings). In addition to the next link in a node of a singly linked list, a doubly linked-list node has a prev link that contains the previous node in the list (null for the list's first node). Doubly linked lists simplify list navigation at the expense of larger nodes (prev field) and more complicated algorithms for list operations. Provide the following methods. As always, recover and handle errors as necessary.

public void insertHead(String s);

-inserts s at the head of the list

public String deleteHead();
-removes the head of the list and returns it

public boolean insertBefore(String where,String s);
-creates a node for s and inserts it immediately before the first node containing the string where; returns true on successful insertion, false if no node with the string where is in the list

public void printForward();
-prints the list from head to tail

public void printBackward();
-prints the list from tail to head

3) [15 points] A queue can be implemented with two stacks, called in-stack and out-stack, as follows. An insert(x) operation pushes x on the in-stack. A remove() operation pops and returns an element from the out-stack if this stack is non-empty. When the out-stack is empty, remove() repeatedly pops an element from the in-stack and pushes it onto the out-stack until the in-stack is empty; the remove() is then satisfied from the now non-empty out-stack. Only when both the in-stack and out-stack are empty does a remove() fail. Convince yourself that this algorithm gives a FIFO queue.

Implement the following queue methods using two integer stacks.

public void insert(int i);

-inserts i into the queue

public int remove();
-removes and returns the next item in the queue

Run your code with the sequence of method invocations in ~lorenz/cs35-2/hw3/test-sequence.3

Hand in: complete code and comments for 1-3; be sure to answer 1b (as comments to the respective methods would be fine). Hand in scripts of your code on the supplied test sequences.
instructions on how to submit