/*  LinkedList.java with inner class ListNode Authors: Koffman & Wolz
 *  Represents a linked list whose first node is referenced
 *  by head.
 */
public class LinkedList {

  // Declare inner class ListNode
  private class ListNode {

    // Data field for ListNode
    private Object info;           // data stored in the node
    private ListNode link;         // link to next node

    // Methods
    // Constructors
    // postcondition: Creates a new empty node.
    public ListNode() {
      info = null;
      link = null;
    }

    // postcondition: Creates a new node storing obj.
    public ListNode(Object obj) {
      info = obj;
      link = null;
    }

    // postcondition: Creates a new node storing obj and linked to
    //   node referenced by next.
    public ListNode(Object obj, ListNode next) {
      info = obj;
      link = next;
    }
  } // class ListNode


  // Data field for LinkedList
  private ListNode head;   // first list node

  // Methods 
  // constructor
  public LinkedList() {
     head = null;
  }

  // postcondition: Adds a node storing obj at front of list.
  public void addFirst(Object obj) {
    ListNode newHead = new ListNode(obj, head);
    head = newHead;
  }

  // postcondition: Adds a node storing obj at end of list.
  public void addLast(Object obj) {
    if (head == null)
       addFirst(obj);  // insert in empty list
    else {
       // Advance next to end of list
       ListNode next = head;
       while (next.link != null)
          next = next.link;

       // At last element - insert obj
       next.link = new ListNode(obj);
    }
  }

  // postcondition: Returns object stored at head of list.
  public Object getFirst() {
    if (head == null)
       return null;
    else
       return head.info;
  }

  // postcondition: Returns object stored at end of list.
  public Object getLast() {
    if (head == null)
       return null;
    else {
       // Advance next to end of list
       ListNode next = head;
       while (next.link != null)
          next = next.link;

       // At last element - retrieve its info.
       return next.info;
    }
  }

  public int lastIndexOf(Object obj) {
     int index = -1;
     int pos = 0;
     ListNode next = head;
     while (next != null) {
        if (next.info.equals(obj))
           index = pos;
        pos++;
        next = next.link;
     }
     return index;
  }

  // postcondition: Returns the length of the linked list.
  public int size() {
    ListNode next = head;
    int count = 0;
    while (next != null) {
       count++;
       next = next.link;
    }
    return count;
  }

  // postcondition: Displays data fields of each list node.
  public String toString() {
    String result = "";
    ListNode next = head;
    while (next != null) {
       result = result + next.info + "\n";
       next = next.link;
    }
    return result;
  }

  public static void main(String[] args) {
     LinkedList lL = new LinkedList();
     lL.addFirst("top");
     lL.addLast("hat");
     lL.addLast("box");
     lL.addFirst("the");
     lL.addFirst("in");
     System.out.println(lL.toString());
     System.out.println("List has " + lL.size() + " elements");
     System.out.println("First element is " + lL.getFirst() +
                        ", last element is " + lL.getLast());
     System.out.println(" index is " + lL.lastIndexOf(""));
  }

} // class LinkedList