lab 32.1

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;   // last element
  private ListNode prevTemp;

  /**
   *  Constructor for the SinglyLinkedList object
   *  Generates an empty list.
   */
  public SinglyLinkedList()
  {
    first = last = null;
  }

  /**
   *  Returns true if this list contains no elements.
   *
   * @return    true iff the list is empty
   */
  public boolean isEmpty()
  {
    return true;
  }

  /**
   *  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();
  }

  /**
   *  Inserts the given element at the beginning of this list.
   *
   * @param  element  the element to be inserted at the beginning of this list.
   */
  public void addFirst(Object element)
  {
    // note the order that things happen:
    // head is parameter, then assigned
    first = new ListNode(element, first);
    if (last == null)
    {
      last = first;
    }
  }

  /**
   *  Returns the last element in this list.
   *
   * @return  the last element in the linked list.
   */
  public Object getLast()
  {
    if (last == null)
    {
      throw new NoSuchElementException();
    }
    else
      return last.getValue();
  }

  /**
   *  Adds and object to the end of the list
   *
   * @param  element  adds element to end of list
   */
  public void addLast(Object element)
  {
    if (first == null)
    {
      first = last = new ListNode(element, first);
    }
    else
    {
      tempPrev = last;
      last.setNext(new ListNode(element, null));
      last.setPrev(tempPrev);
      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
   */
  public void insert(Comparable element)
  {
    System.out.println("insert: " + element);
  }

  /**
   *  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)
  {
    System.out.println("find: " + element);
    return null;
  }

  /**
   *  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 prev = first;
    while(temp != null)
    {
    	if(((Comparable)temp.getValue()).compareTo(element)==0)  //middle of list
    		prev.setNext(temp.getNext());
    		temp = temp.getNext();
    		temp.setPrev(prev.getValue());
  }

  /**
   *  Returns the number of elements in this list.
   *
   * @return    number of elements in this list.
   */
  public int size()
  {
    int count = 0;
    return count;
  }

  /**
   *  Prints all the elements of the list
   */
  public void printList()
  {
    ListNode temp = first;  // start from the first node
    while (temp != null)
    {
      System.out.println(((Item)temp.getValue()).getId() + " " +
                         ((Item)temp.getValue()).getInv());
      temp = temp.getNext();  // go to next node
    }
  }

  /**
   *  Prints all the elements of the list in reverse order
   */
  public void printBackwards()
  {
    ListNode temp = last;
    while(temp!=null)
    {
		System.out.println(((Item)temp.getValue()).getId() + " " +
                         ((Item)temp.getValue()).getInv());
        temp = temp.getPrev();
  }

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

  /**
   *  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    Description of the Returned Value
   */
  public String toString()
  {// post: returns a string representing list

    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
    }
    s += "]";
    return s;
  }
}



/**
 *  Implementation of a node of a singly linked list.
 *
 *  Adapted from the College Board's AP Computer Science AB:
 *  Implementation Classes and Interfaces.
 */
public class ListNode
{
  private Object value;
  private ListNode next;
  private ListNode prev;
  private ListNode temp;

  /**
   *  Constructs a new element with object initValue,
   *  followed by next element
   *
   * @param  initValue  New element object
   * @param  initNext   Reference to next element
   */
  public ListNode(Object initValue, ListNode initNext)
  {
    value = initValue;
    next = initNext;
    prev = null;
  }

  /**
   *  Constructs a new tail of a list with object initValue
   *
   * @param  initValue  New element object
   */
  public ListNode(Object initValue)
  {
    this(initValue, null);
  }

  /**
   *  Sets the value attribute of the ListNode object
   *
   * @param  theNewValue  value attribute of the ListNode object
   */
  public void setValue(Object theNewValue)
  {
    value = theNewValue;
  }

  /**
   *  Sets reference to new next value
   *
   * @param  theNewNext  The new next value
   */
  public void setNext(ListNode theNewNext)
  {
    next = theNewNext;
  }

  public void setPrev(ListNode theNewPrev)
  {
    prev = theNewPrev;
  }

  /**
   *  Returns value associated with this element
   *
   * @return    The value associated with this element
   */
  public Object getValue()
  {
    return value;
  }

  /**
   *  Returns reference to next value in list
   *
   * @return    The next value in the list
   */
  public ListNode getNext()
  {
    return next;
  }

  public ListNode getPrev()
  {
  	return prev;
  }
}