1: Linked Lists

In this problem you will write a class that implements an ordered list of Strings. Your class will able to add and remove elements in the list at arbitrary positions. Your implementation will use linked lists and recursion (when appropriate). Your implementation should be ecient.

Create a Java class called LinkedList that extends the LinkedListABS class. Your class must have a public constructor that has zero arguments (which creates an empty list of Strings). You may add as many private attributes and helper methods in your class as you need. You are not allowed to use an array, ArrayList, or any other container class that Java provides to store your list. You must use a linked list with the Node class provided. Mark breakdown: style:5, correctness:15

2: Copy

In the provided CopyLinkedList class, implement the copy() method as described. The resulting (copied) list should not share any memory with the input list. (That is, the list that makes up the copy must have its own Nodes.) Mark breakdown: correctness:10

3: Queue

In this problem you will implement a queue of Strings using a linked list. For this you will need to decide how to deal with adding and removing nodes (in a FIFO manner) eciently.

Your enqueue and dequeue methods should not use recursion (or iteration). A queue with less Strings in it is smaller (less than) a queue with more Strings. Two empty queues are considered the same. If two queues have the same size (bigger than 0), the order is determined alphabetically using the rst string in each queue.

Create a Java class called Queue that extends the provided QueueABS class. Your class must have a zero argument constructor that creates an empty queue. Your implementation must use linked lists with the Node class provided. Do not use recursion or iteration in your method, unless otherwise told to do so (in the toString() method for example). Your methods must be ecient.

4: Mergesort

In this problem, you will implement the mergesort sorting algorithm using linked lists.

Complete the methods in the Merge class that is provided. Your nal method (sort()) is the mergesort method. It will sort lists of Strings alphabetically. It should use both the merge() and split() methods in it. (You will also need the copy() method from the CopyLinkedList class.)