/*
 * LinkedList.java
 * Example is based on an example from
 * D. Flanagan, "Java Examples in a Nutshell"
 */


// package pic20a;

public class LinkedList extends Object {

    public interface Linkable {
        public Linkable getNext();
        public void setNext(Linkable node);
    }
    
    Linkable head;
    
    /** Creates new LinkedList */
    public LinkedList() {}
    
    /** Returns the first node in the list */
    public synchronized Linkable getHead() {
        return head;
    }
    
    /** Inserts a node at the beginning of the list */
    public synchronized void insertAtHead(Linkable node) {
        node.setNext(head);
        head = node;
    }
    
    /** Inserts a node at the end of the list */
    public synchronized void insertAtTail(Linkable node) {
        if (head == null) {
            head = node;
        } else {
            Linkable p, q;
            for (p = head; (q = p.getNext()) != null; p = q);
            p.setNext(node);
        }
    }
    
    /** Removes and returns the node at the head of the list */
    public synchronized Linkable removeFromHead() {
        Linkable node = head;
        if (node != null) {
            head = node.getNext();
            node.setNext(null);
        }
        return node;
    }
    
    /** Removes and returns the node at the end of the list */
    public synchronized Linkable removeFromTail() {
        if (head == null) {
            return null;
        }
        Linkable p = head, q = null, next = head.getNext();
        if (next == null) {
            head = null;
            return p;
        }
        while ((next = p.getNext()) != null) {
            q = p;
            p = next;
        }
        q.setNext(null);
        return p;
    }
    
    /** Removes a node matching the specified node from the list */
    public synchronized void remove(Linkable node) {
        if (head == null) {
            return;
        }
        if (node.equals(head)) {
            head = head.getNext();
            return;
        }
        Linkable p = head, q = null;
        while ((q = p.getNext()) != null) {
            if (node.equals(q)) {
                p.setNext(q.getNext());
                return;
            }
            p = q;
        }
    }
    
    
    /**
     * nested class Test defines a main() method that tests the LinkedList class
     */
    public static class Test {
        
        /**
         * inner class LinkableInteger implements Linkable interface for Test purposes
         */
        static class LinkableInteger implements Linkable {
            int i;
            Linkable next;
        
            public LinkableInteger(int i) {
                this.i = i;
            }

            public Linkable getNext() {
                return next;
            }
            
            public void setNext(Linkable node) {
                next = node;
            }
            
            public String toString() {
                return i + " ";
            }
            
            public boolean equals(Object o) {
                if (this == o) {
                    return true;
                }
                if (!(o instanceof LinkableInteger)) {
                    return false;
                }
                if (((LinkableInteger) o).i == this.i) {
                    return true;
                }
                return false;
            }
        }
        
        /** the Test driver: insert some nodes, remove some nodes, print out nodes in the list */
        public static void main(String[] args) {
            LinkedList ll = new LinkedList();
            ll.insertAtHead(new LinkableInteger(1));
            ll.insertAtHead(new LinkableInteger(2));
            ll.insertAtHead(new LinkableInteger(3));
            ll.insertAtHead(new LinkableInteger(4));
            ll.insertAtTail(new LinkableInteger(5));
            ll.insertAtTail(new LinkableInteger(6));
            System.out.println(ll.removeFromHead());
            System.out.println(ll.removeFromTail());
            ll.remove(new LinkableInteger(2));
            
            // print out the contents of the list
            System.out.println();
            for (Linkable l = ll.getHead(); l != null; l = l.getNext()) {
                System.out.print(l);
            }
        }
    }
}