CS231

Linked Lists

The goal of this lab period is to give you an opportunity to implement a generic singly-linked list with an Iterator.

You are expected to implement the Linked List without importing any packages beside the Iterator interface mentioned below.

Tasks

Setup
Make a new folder for this week's project.

Download both the LabLinkedListTests file and LinkedListTests file. You will use the LabLinkedListTests file to show us that you have completed the lab checkpoint. You may/should edit the LinkedListTests to comment out methods that you haven't written yet so that you can test your methods as you write them.

Remeber to run your testers from the command line using the -ea flag to run assertions! These tests are hard to check by eye. You will need to compile the test code before running it this way.

Create a new java file called LinkedList.java. Import a necessary package:
```
import java.util.Iterator;    // defines the Iterator interface
            
```
Define the LinkedList class
Define a public class LinkedList that has a generic type specifier. The type specifier indicates what type of class is stored in the linked list. If no specifier is provided in the declaration, the defualt type is Object.
```
public class LinkedList<T> {
```
Create a container class (a Node)
A Node needs to hold a generic object and a next pointer. Make a private class inside the LinkedList class called Node that has a field of type Node called next, and a field of type T with a name of your choice. The Node class should have the following methods.
- public Node(T item) a constructor that initializes next to null and the container field to item.
- public T getData() returns the value of the container field.
- public void setNext(Node n) sets next to the given node.
- public Node getNext() returns the next field.
Create fields and methods for the LinkedList class
The LinkedList needs to store the head of the list and the number of items in the list. In addition to those fields, the LinkedList class should support the following methods (we recommend working on them in this order).
- public LinkedList() constructor that initializes the fields so it is an empty list.
- public int size() returns the size of the list.
- public void clear() empties the list (resets the fields so it is an empty list).M
- public boolean isEmpty() returns true if the list is empty, otherwise this method returns false.
- public String toString() returns a String representation of the list.
- public void add(T item) inserts the item at the beginning of the list.
- public T get(int index) returns the item specified by the given index.
- public void add(int index, T item) inserts the item at the specified position in the list.
- public boolean contains(Object o) returns true if o is present in this list, otherwise this method returns false. More specifically, if there is an item item in this list such that item.equals(o), then this method should return true.
- public T remove() removes the first item of the list and returns it.
- Lab checkpoint: Congrats, you've written your add, get and contains method! Call us over and show us they work by running the LabLinkedListTests file (But also please stick around and finish the lab if you're able to!)
- public T remove(int index) removes the item at the specified position in the list and returns it.
- public boolean equals(Object o) returns true if o is a LinkedList that also contains the same items in the same order.
  Notice that for this method the parameter is of type Object instead of being a LinkedList itself. This was done purposefully, to comply with Java's standard equals method, which all Objects technically support. For this method, I recommend first checking if the parameter is itself a LinkedList; if it is not, then you can immediately return false. You can do so by creating an if statement like:
```
if (!(o instanceof LinkedList)){
    return false;
}
// If I have reached this line, o must be a LinkedList
LinkedList oAsALinkedList = (LinkedList) o;
// Now I have a reference to something Java knows is a LinkedList!
```
Implement the Iterable interface
To enable another program to loop through the list, implement the Iterable interface, which allows a programmer to use a foreach loop structure on our LinkedLists. First, change the class definition for LinkedList to specify that it implements the Iterable interface.
```
    public class LinkedList<T> implements Iterable<T>
```
Then create an Iterator subclass that handles traversing the list. Create a new private class inside the LinkedList class with the following definition.
```
    private class LLIterator implements Iterator<T>
```
Give the class one field, which is of type Node, and which will hold the next node to be provided during a traversal. Then implement the following methods in the class.
- public LLIterator(Node head) the constructor for the LLIterator given the head of a list.
- public boolean hasNext() returns true if there are still values to traverse (if the current node reference is not null).
- public T next() returns the next item in the list, which is the item contained in the current node. The method also needs to move the traversal along to the next node in the list.
- public void remove() does nothing. Implementing this function is optional for an Iterator.
Finally, add the function iterator public Iterator iterator() to the LinkedList class. This should not be in the LLIterator class! This method should return a new LLIterator object with head passed to the constructor, shown as the following code:
```
    // Return a new LLIterator pointing to the head of the list
    public Iterator<T> iterator() {
    return new LLIterator( this.head );
    }
```
The iterator method makes the class actually implement Iterable.
Final test of the LinkedList class
Run the full LinkedListTests file that you downloaded at the start of the lab to test the standard LinkedList functions. Debug your code until it works! (But we hope you've already been doing this along the way).

When you are done, you can proceed to the project.