CS 231: Data Structures and Algorithms (Lab Page)

Title image Lab 4
Fall 2016

Singly-Linked 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. Make a new folder for this week's project.
  2. Create a new java file called LinkedList.java.

    Import the necessary packages:

    import java.util.Iterator;
    import java.util.ArrayList;
    import java.util.Collections;
    

    Declare the class as a public class with a generic type T (T is a type variable). We will be updating this declaration once we add the iterator, but let's start out simply.

    public class LinkedList<T>
    
  3. First, we need to create a container class that will hold a generic object and a next pointer. Make a private inner class called Node that has a Node field called next, and a T field 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 the fields for the LinkedList class to store the head of the list and the number of items in the list. Then make the following methods for the LinkedList class.
    • public LinkedList() - a constructor that initializes the fields.
    • public void clear() - empties the list.
    • public int size() - returns the size of the list.
    • public void add(T item) - adds item to the head of the list.

    Write a very simple test function that creates a Linked List and adds one node. Compile and run it. Without an interator, you aren't in the best position to debug, so don't worry about getting it all working yet. But please do make sure it compiles.

  5. To enable another program to loop through our list, we're going to implement the Iterable interface, which allows a programmer to use the foreach loop structure on our LinkedLists. First, change the class definition for LinkedList to be:
    public class LinkedList<T> implements Iterable<T>
    

    Then we need to create our own 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) - creates an 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.

    In your LinkedList class, add a method that returns an Iterator. This is the method that makes your class actually implement Iterable:

        // Return a new LLIterator pointing to the head of the list
        public Iterator<T> iterator() {
            return new LLIterator( this.head );
        }
    
  6. Now copy the following main function to your LinkedList.java file and test out your Iterator (you may keep or trash your original test code as you wish).
    public static void main(String[] args) {
    		
    		LinkedList<Integer> llist = new LinkedList<Integer>();
    		
    		llist.add(5);
    		llist.add(10);
    		llist.add(20);
    		
    		System.out.printf("\nAfter setup %d\n", llist.size());
    		for(Integer item: llist) {
    			System.out.printf("thing %d\n", item);
    		}
    		
    		llist.clear();
    		
    		System.out.printf("\nAfter clearing %d\n", llist.size());
    		for (Integer item: llist) {
    			System.out.printf("thing %d\n", item);
    		}
    		
    		for (int i=0; i<20; i+=2) {
    			llist.add(i);
    		}
    		
    		System.out.printf("\nAfter setting %d\n", llist.size());
    		for (Integer item: llist) {
    			System.out.printf("thing %d\n", item);
    		}
    	}
    

    Compile and run the test code. Debug your code until it works perfectly.

  7. Create two more methods for your 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 your main test 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);
    	}
        

Once you have completed the lab, go on to the project.