Lists

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

Tasks

1. Setup

   Make a new folder for this week's project.

   Create a new java file called LinkedList.java. Import some necessary packages:

   import java.util.Iterator;    // defines the Iterator interface
   import java.util.ArrayList;   
   import java.util.Collections; // contains a shuffle function

2. 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> {

3. 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.

4. 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 (note that these methods are in alphabetical order, not necessarily the easiest order of implementation. If I were to implement these, I would probably do: size(), isEmpty(), clear(), add(item), remove(), get(), add(index, item), remove(index), contains(o), equals(o)):

   • public LinkedList() constructor that initializes the fields so it is an empty list.
   • public void add(T item) inserts the item at the beginning of the list.
   • public void add(int index, T item) inserts the item at the specified position in the list.
   • public void clear() empties the list (resets the fields so it is an empty 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 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!
     

   • public T get(int index) returns the item specified by the given index.
   • public boolean isEmpty() returns true if the list is empty, otherwise this method returns false.
   • public T remove() removes the first item of the list and returns it.
   • public T remove(int index) removes the item at the specified position in the list and returns it.
   • public int size() returns the size of the list.
   • public String toString() returns a String representation of the list.

---

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

---