CS 112 Lab 4

Implement a generic Linked-List datastructure with the following associated methods,

• iterator () // Get an iterator for the linked list
• addToHead ( newNodeData ) // Add a new node to head of the list
• deleteFromHead () // Delete the head node and return data in head node
• addToTail ( newNodeData ) // Add a new node to tail of the list
• deleteFromTail () // Delete the tail node and return data in tail node

package lab04;
public class Client {
    public static void main(String [] args){
        
        //Initialize an empty list of Strings
        LinkedList<String> list = new LinkedList<String>();
        
        //Add names of planets at both ends of the list
        list.addToTail("Jupiter");
        list.addToHead("Mars");
        list.addToTail("Saturn");
        list.addToHead("Earth");
        list.addToTail("Uranus");
        list.addToHead("Venus");
        list.addToTail("Neptune");
        list.addToHead("Mercury");    
        System.out.println("List before deletion");
        list.printList();
        
        //Delete planets from both ends of the list
        for( int i = 1; i <= 3; i++ ){
            System.out.println("deleting head: " + list.deleteFromHead());
            System.out.println("deleting tail: " + list.deleteFromTail());
        }
        System.out.println("\nList after deletion");
        list.printList();
        
        System.out.println("deleting head: " + list.deleteFromHead());
        System.out.println("deleting tail: " + list.deleteFromTail());
        System.out.println("\nList after deletion");
        list.printList();
    }
}

List before deletion
Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune, 
 
deleting head: Mercury
deleting tail: Neptune
deleting head: Venus
deleting tail: Uranus
deleting head: Earth
deleting tail: Saturn
 
List after deletion
Mars, Jupiter, 
 
deleting head: Mars
deleting tail: Jupiter
 
List after deletion 

package lab04;
import java.util.Iterator;
 
// The LinkedList Node class  
class Node<T>{
    
    private T nodeData;
    private Node<T> nextNode;
    
    public Node( T newData, Node<T> newNextNode ){
        nodeData = newData;
        nextNode = newNextNode;
    }
    public T getData(){
        return nodeData;
    }
    public Node<T> getNextNode(){
        return nextNode;
    }
    public void setData(T newData){
        nodeData = newData;
    }
    public void setNextNode( Node<T> newNextNode ){
        nextNode = newNextNode;
    }
}
 
// The LinkedList class 
public class LinkedList<T> implements Iterable<T> {    
    
    private Node<T> headNode;
    
    public LinkedList(){
        headNode = null;
    }
    
    // Add a new node to head of the list
    public void addToHead( T newNodeData ){
        headNode = new Node<T>( newNodeData, headNode );
    }
    
    // Delete the head node and return data in the deleted node
    public T deleteFromHead() throws Exception{
     
        if( headNode != null ) {
            T headNodeData = headNode.getData(); 
            headNode = headNode.getNextNode();
            return headNodeData;
        } else
            throw new Exception("deleteFromHead(): Linked List is empty.");
    }
    
    // Get an iterator for this list
    public ListIterator<T> iterator(){
        return new ListIterator<T>( headNode );
    }
    
    // The ListIterator class below implements an iterator for the 
    // LinkedList class 
    static class ListIterator<T> implements Iterator<T> {
        
        // Keeps track of the iterator's position in the list
        private Node<T> currentNode;
        
        // The iterator starts off at head of the linked list
        public ListIterator( Node<T> headNode ){
            currentNode = headNode;
        }
        // Are there more nodes ahead of us?
        public boolean hasNext(){
            return ( currentNode != null ); 
        }
        // Output current "node data" and walk to the next node
        public T next(){
            T currentData = currentNode.getData();
            currentNode = currentNode.getNextNode();
            return currentData;
        }
        // Output current "node" and walk to the next node
        public Node<T> nextNode(){
            Node<T> tempNode = currentNode;
            currentNode = currentNode.getNextNode();
            return tempNode;
        }
        // remove not implemented here but implemented in the 
        // LinkedList class above
        public void remove(){
        }
    }
    
    // Print elements in the list using the list-iterator
    public void printList(){
        // Use the list-iterator to walk down the list
        ListIterator<T> listIterator = this.iterator();
        while(listIterator.hasNext()){
            System.out.print(listIterator.next()+", ");
        }
        System.out.println("\n");
    }
    
    // Add a new node to tail of the list
    public void addToTail( T newNodeData ){
        // Locate the last node in the list so that we can 
        // add newNode after it.
        Node<T> lastNode = null;
        
        // Use the listIterator to walk through the list to find last node
        ListIterator<T> listIterator = this.iterator();
        // TASK: FILL IN YOUR CODE HERE
        
        // Create a new Node with newNodeData and set it as next node for lastNode
        // *** check whether lastNode is null and deal with appropriately 
        
        // TASK: FILL IN YOUR CODE HERE 
    }
    
    // Delete the tail node and return data in the deleted node
    public T deleteFromTail(){
        // Find the last two nodes in the list so that we can   
        // delete the last node and update the forward reference to it.
        Node<T> lastNode = null;
        Node<T> previousToLastNode = null;
        
        // Use the list-iterator to walk through the list to find the 
        // last two nodes.
        ListIterator<T> listIterator = this.iterator();
        // TASK: FILL IN YOUR CODE HERE
        
        T tailNodeData;
        // (a) assign data from lastNode to tailNodeData
        // (b) change forward reference to nextNode in previousToLastNode
        // *** check whether any of lastNode or previousToLastNode 
        // *** is null and deal with appropriately 
        
        // TASK: FILL IN YOUR CODE HERE
        
        // return data in the deleted node
        return tailNodeData;
    }
}

http://cs-people.bu.edu/tvashwin/cs112_spring09/lab04.html