SinglyLinkedList

import java.util.*;

/**
 *  Implementation of lists, using singly linked elements.
 *
 * @author     G. Peck
 * @created    April 27, 2002
 */
public class SinglyLinkedList{
    private ListNode first;  // first element
    private ListNode last;
    private int size;
    private ListNode back;
    private ListNode temp;

  /**
   *  Constructor for the SinglyLinkedList object
   *  Generates an empty list.
   */
    public SinglyLinkedList(){
        first = null;
        last = null;
    }
  /**
   *  Returns the first element in this list.
   *
   * @return  the first element in the linked list.
   */
    public Object getFirst(){
        if (first == null){
            throw new NoSuchElementException();
        }
        else return first.getValue();
    }
    public Object getLast(){
        if (last == null)
            throw new NoSuchElementException();
        else return last.getValue();
    }
  /**
   *  Inserts the given element at the beginning of this list.
   *
   * @param  value  the element to be inserted at the beginning of this list.
   */
    public void addFirst(Object value){
        if (first == null){
            first = last = new ListNode(value, null);
        }
        else first = new ListNode(value, first);

        /*
         *first = new ListNode(value, first);
         *if (last == null)
         *  last = first;
         *
         */
    }
    public void addLast(Object value){
        if (first == null){
            first = last = new ListNode(value, first);
        }
        else{
            last.setNext(new ListNode(value, null));
            last = last.getNext();
        }
    }
      /**
   *  Inserts the specified element at the position in this list
   *  according to the natural ordering of its elements. All elements
   *  in the list must implement the Comparable interface. Shifts
   *  the element currently at that position (if any) and any
   *  subsequent elements to the right.
   *
   * @param  element  element to be inserted
   *create the new node with its link field pointing to temp
   *
    if (node is to be inserted at head of list)     // back == null
       first = new node;
     else
        back.next = new node;
    if (node is to be inserted at end of list)      // temp == null
        last = new node;
   */
  public void insert(Comparable element){
    temp = first;
    back = null;
    while((temp != null) && (element.compareTo(temp.getValue()) > 0)){
        back = temp;
        temp = temp.getNext();
    }
    ListNode newNode = new ListNode(element, null);
    newNode.setNext(temp);
    if(back == null){
        first = newNode;
    }
    else{
        back.setNext(newNode);
    }
    if (temp == null){
        last = newNode;
    }
  }

  /**
   *  Returns the first occurrence of the specified element, or null
   *  if the List does not contain this element.
   *
   * @param  element  element to search for.
   * @return        first occurrence of the specified element, or null
   *                if the list doesn not contain the element.
   */
  public Object find(Comparable element){
    ListNode temp = first;
    ListNode back = null;
    while ((temp != null) && (element.compareTo(temp.getValue())) != 0){
        back = temp;
        temp = temp.getNext();
    }
    if (temp == null)
        return null;
    return temp.getValue();
  }

  /**
   *  Removes the first occurrence of the specified element in
   *  this list. If the list does not contain the element, it
   *  is unchanged.
   *
   * @param  element  element to be removed from this list, if present.
   * @return          removes first element with matching element, if any.
   */
  public Object remove(Object element){
    ListNode temp = first;
    ListNode back = null;
    while ((temp!= null) && (element.equals(temp.getValue()) == false)){
        back = temp;
        temp = temp.getNext();
    }
    if (temp == null)
        return null;
    if (back == null)
        first = temp.getNext();
    else
        back.setNext(temp.getNext());
    return temp.getValue();
  }
 /**
   *  Prints all the elements of the list in reverse order
   */
  public void printBackwards(){
    printBackwards(first);
  }

  /**
   *  Recursive helper method to print all the elements of
   *  the list in reverse order
   */
  private void printBackwards(ListNode temp){
        if (temp != null){
            printBackwards(temp.getNext());
            System.out.println(temp.getValue());
        }
  }
  /**
   *  Removes all of the elements from this list.
   */
  public void clear(){
    first = null;
    last = null;
    System.out.println("clear");
  }

  /**
   *  Print the contents of the entire linked list
   */
    public void printList(){
        ListNode temp = first;// start from the first node
        while (temp != null){
            System.out.println(temp.getValue() + " ");
            temp = temp.getNext();// go to next node
        }
        System.out.println();
    }

  /**
   *  Returns a string representation of this list. The string
   *  representation consists of the list's elements in order,
   *  enclosed in square brackets ("[]"). Adjacent elements are
   *  separated by the characters ", " (comma and space).
   *
   * @return    string representation of this list
   */
    public int size(){
        ListNode temp = first;// start from the first node
        size = 0;
        while (temp != null){
            size++;
            temp = temp.getNext();
        }
        return size;
    }
    public String toString(){
        String s = "[";
        ListNode temp = first;  // start from the first node
        while (temp != null){
            s += temp.getValue(); // append the data
            temp = temp.getNext();      // go to next node
            if (temp != null)
                s += ", ";
        }
        s += "]";
        return s;
    }
}