CS 231: Lab #4

Title image Fall 2019

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 getThing() 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.

    It's probably worth implementing the first four methods, up though addFirst, then work on the Iterator. You can use this test file to test those four functions and the Iterator.

    • public LinkedList() constructor that initializes the fields so it is an empty list.
    • public void clear() empties the list (resets the fields so it is an empty list).
    • public int size() returns the size of the list.
    • public void addFirst(T item) inserts the item at the beginning of the list.
    • public void addLast(T item) appends the item at the end of the list.
    • public void add(int index, T item) inserts the item at the specified poistion in the list.
    • public T remove (int index) removes the item at the specified position in the list.

  5. 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. It should return a new LLIterator 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.

  6. Test the LinkedList class

    Download the LLTest file and test the standard LinkedList functions. Compile and run the test code. If the LinkedList is working properly, it should produce this output. Debug your code until it works.

  7. Write methods to convert the LinkedList to an ArrayList

    Create two more methods for the LinkedList class. You can make use of the foreach structure in the first method.

    • public ArrayList<T> toArrayList() returns an ArrayList of the list contents in order.
    • public ArrayList<T> toShuffledList() returns an ArrayList of the list contents in shuffled order.

    Then add the following to the end of the LLTest main function.

    	ArrayList<Integer> alist = llist.toArrayList();
    	System.out.printf("\nAfter copying %d\n", alist.size());
    	for(Integer item: alist) {
    		System.out.printf("thing %d\n", item);
    	}						
    	
    	alist = llist.toShuffledList();	
    	System.out.printf("\nAfter copying %d\n", alist.size());
    	for(Integer item: alist) {
    		System.out.printf("thing %d\n", item);
    	}

When you are done, you can proceed to the project