/* 
 * The following class implements an iterable linked list that maintains a reference to 
 * both the first and last nodes of the list.
 * 
 * If we restricted ourselves to using only the methods addFirst(Item item) and removeFirst 
 * to insert and remove elements, we would effectively be using a stack.
 * 
 * Similarly, If we restricted ourselves to using only the methods addLast(Item item) and 
 * removeFirst() to insert and remove elements, we would effectively would be using a queue.
 * 
 * For completeness, there is a removeLast() method, so that this class could also function 
 * as a deque -- but note that this method suffers from the inefficiency of having to 
 * traverse the list to get a reference to the parent of the last node. This could be fixed 
 * by implementing a doubly-linked list, where each node stores a link to both the next node 
 * and the previous node.
 * 
 * A similarly inefficient contains(Item item) method is also included so that we can 
 * determine if a given item is present in the list. This method would be more efficient
 * if our data structure was some sort of tree with sortable items instead of a list.
 */

import java.util.Iterator;

public class LinkedListHT<Item> implements Iterable<Item> {
    
    private class Node {
        Item item;
        Node next;
    }
   
    // instance variables
    private Node first;
    private Node last; 
    private int size;
    
    public boolean isEmpty() {
        return (first == null);
    }
    
    public void addFirst(Item item) {   
        Node node = new Node();
        node.item = item;
        
        if (this.isEmpty()) { // no items in list
            first = node;
            last = node;
        }
        else { // one or more items in list
            node.next = first;
            first = node;   
        }
        size++;
    }
    
    public Item removeFirst() {     
        if (this.isEmpty()) { //no nodes in list
            return null; 
        }
        else if (first == last) { // one node in list
            Item item = first.item;
            first = null;
            last = null;
            size--;
            return item;               
        }
        else { // more than one node in list
            Item item = first.item;      
            first = first.next; 
            size--;
            return item;  
        }
    }
    
    public void addLast(Item item) {
        Node node = new Node();
        node.item = item;
        
        if (this.isEmpty()) { // no items in list
            first = node;
            last = node;
        }
        else { // one or more items in list
            last.next = node;
            last = node;
        }
        size++;
    }
   
    public Item removeLast() {
        if (this.isEmpty()) {
            return null; //there is no last element
        }
        else if (first == last) { // one element in list
            Item item = first.item;
            first = null;
            last = null;
            size--;
            return item;
        }
        else { // more than one item in list
            Node n = first; //and we already know that first and second is not null

            // we need a link to the node previous to the last node, so...
            while (n.next.next != null) {  
                n = n.next;
            }
            //n is now parent to last node...
            Item item = n.next.item;
            n.next = null;
            // the above would have been much easier in a doubly-linked list, 
            // where we have a link to the previous node!

            //don't forget to update "last" before we return the item removed...
            last = n;
            size--;
            return item;
        }
    }
    
    public boolean contains(Item item) {  
        for (Node n = first; n != null; n = n.next) {
            if (n.item.equals(item)) return true;
        }
        return false;
    }
    
    public Iterator<Item> iterator() {  // one could improve this method by making it "fail-fast"
        return new Iterator<Item>() {
            Node node = first;

            public boolean hasNext() {
                return (node != null);
            }

            public Item next() {
                Item itemToReturn = node.item;
                node = node.next;
                return itemToReturn;
            }
        };
    }
    
    public String toString() {
        String outputStr = "";
        outputStr += "First: " + ((first != null) ? first.item : "-") + "   ";
        outputStr += "Last: " + ((last != null) ? last.item : "-") + "   ";
        outputStr += "size: " + this.size + "   ";
        outputStr += " List: ";
        for (Item i : this) {
            outputStr += i + " ";
        }
        return outputStr;
    }

    public static void main(String[] args) {
        String s;
        LinkedListHT<String> list = new LinkedListHT<String>();
        
        list.addFirst("a"); System.out.println(list);
        list.addFirst("b"); System.out.println(list);
        list.addFirst("c"); System.out.println(list);
        list.addFirst("d"); System.out.println(list);
        
        System.out.println("contains c? " + list.contains("b"));
        
        s = list.removeFirst(); System.out.println("removed " + s + ";   " + list);
        s = list.removeFirst(); System.out.println("removed " + s + ";   " + list);
        s = list.removeFirst(); System.out.println("removed " + s + ";   " + list);
        s = list.removeFirst(); System.out.println("removed " + s + ";   " + list);
        
        list.addLast("a"); System.out.println(list);
        list.addLast("b"); System.out.println(list);
        list.addLast("c"); System.out.println(list);
        list.addLast("d"); System.out.println(list);
        
        System.out.println("contains c? " + list.contains("b"));
        
        s = list.removeLast(); System.out.println("removed " + s + ";   " + list);
        s = list.removeLast(); System.out.println("removed " + s + ";   " + list);
        s = list.removeLast(); System.out.println("removed " + s + ";   " + list);
        s = list.removeLast(); System.out.println("removed " + s + ";   " + list);
    }
}