• boolean equals(Object other)
• String toString()
• int hashCode()

• int compareTo(Object other)
  // return value < 0 if this is less than other
  // return value = 0 if this is equal to other
  // return value > 0 if this is greater than other

• Integer(int value)
  // constructor
• int intValue()

• Double(double value)
  // constructor
• double doubleValue()
  

• int length()
• String substring(int from, int to)
  // returns the substring beginning at from
  // and ending at to-1
• String substring(int from)
  // returns substring(from, length())
• int indexOf(String s)
  // returns the index of the first occurrence of s;
  // returns -1 if not found

• static int abs(int x)
• static double abs(double x)
• static double pow(double base, double exponent)
• static double sqrt(double x)

• int nextInt(int n)
  // returns an integer in the range from 0 to n-1 inclusive
• double nextDouble()
  // returns a double in the range [0.0, 1.0)

• boolean add(Object x)
  // appends x to the end of list; returns true
• int size()
• Object get(int index)
  // returns the element at the specified position
• Object set(int index, Object x)
  // replaces the element at index with x
  // returns the element formerly at the specified position
• Iterator iterator()
• ListIterator listIterator()

• Methods in addition to the List methods:
• void add(int index, Object x)
  // inserts x at position index, sliding elements
  // at position index and higher to the right
  // (adds 1 to their indices) and adjusts size
  
• Object remove(int index)
  // removes element from position index, sliding elements
  // at position index + 1 and higher to the left
  // (subtracts 1 from their indices) and adjusts size
  // returns the element formerly at the specified position

• Methods in addition to the List methods:
• void addFirst(Object x)
• void addLast(Object x)
• Object getFirst()
• Object getLast()
• Object removeFirst()
• Object removeLast()

• boolean add(Object x)
• boolean contains(Object x)
• boolean remove(Object x)
• int size()
• Iterator iterator()

• Object put(Object key, Object value)
  // associates key with value
  // returns the value formerly associated with key
  // or null if key is not in the map
• Object get(Object key)
• Object remove(Object key)
• boolean containsKey(Object key)
• int size()
• Set keySet()

• boolean hasNext()
• Object next()
• void remove()

• Methods in addition to the Iterator methods
• void add(Object x)
• void set(Object x)

public class ListNode
{  
  private Object value;
  private ListNode next;
  
  public ListNode(Object initValue, ListNode initNext)
    { value = initValue; next = initNext; }

  public Object getValue() { return value; }
  public ListNode getNext() { return next; }

  public void setValue(Object theNewValue) { value = theNewValue; }
  public void setNext(ListNode theNewNext) { next = theNewNext; }
}

public class TreeNode
{
  private Object value;
  private TreeNode left;
  private TreeNode right;
  
  public TreeNode(Object initValue)
    { value = initValue; left = null; right = null; }

  public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
    { value = initValue; left = initLeft; right = initRight; }

  public Object getValue() { return value; }
  public TreeNode getLeft() { return left; }
  public TreeNode getRight() { return right; }

  public void setValue(Object theNewValue) { value = theNewValue; }
  public void setLeft(TreeNode theNewLeft) { left = theNewLeft; }
  public void setRight(TreeNode theNewRight) { right = theNewRight; }
}


 
Interface for stacks (* See note at end of reference)

public interface Stack 
{ 
  /**
   * postcondition: returns true if stack is empty; 
   *                otherwise, returns false 
   */
  boolean isEmpty();
 
  /**
   * precondition:  stack is [e1, e2, ..., en] with n >= 0 
   * postcondition: stack is [e1, e2, ..., en, x] 
   */
  void push(Object x); 

  /**
   * precondition:  stack is [e1, e2, ..., en] with n >= 1 
   * postcondition: stack is [e1, e2, ..., e(n-1)]; returns en 
   * exceptions:    throws an unchecked exception if the stack is empty 
   */
  Object pop(); 

  /**
   * precondition:  stack is [e1, e2, ..., en] with n >= 1 
   * postcondition: returns en 
   * exceptions:    throws an unchecked exception if the stack is empty 
   */
  Object peekTop(); 
} 


Interface for queues (* See note at end of reference)

public interface Queue 
{ 
  /**
   * postcondition: returns true if queue is empty;
   *                otherwise, returns false 
   */
  boolean isEmpty(); 

  /**
   * precondition:  queue is [e1, e2, ..., en] with n >= 0 
   * postcondition: queue is [e1, e2, ..., en, x] 
   */
  void enqueue(Object x); 

  /**
   * precondition:  queue is [e1, e2, ..., en] with n >= 1 
   * postcondition: queue is [e2, ..., en]; returns e1 
   * exceptions:    throws an unchecked exception if the queue is empty 
   */
  Object dequeue(); 

  /**
   * precondition:  queue is [e1, e2, ..., en] with n >= 1 
   * postcondition: returns e1 
   * exceptions:    throws an unchecked exception if the queue is empty 
   */
  Object peekFront(); 
} 



Interface for priority queues (* See note at end of reference)

public interface PriorityQueue 
{ 
  /**
   * postcondition: returns true if the number of elements in
   *                the priority queue is 0; 
   *                otherwise, returns false 
   */
  boolean isEmpty(); 

  /**
   * postcondition: x has been added to the priority queue; the number 
   *               of elements in the priority queue is increased by 1. 
   */
  void add(Object x); 

  /**
   * postcondition: The smallest item in the priority queue is removed 
   *                and returned; the number of elements in the priority 
   *                queue is decreased by 1. 
   * exceptions:    throws unchecked exception if priority queue is empty 
   */
  Object removeMin(); 

  /**
   * postcondition: The smallest item in the priority queue is returned; the 
   *                priority queue is unchanged 
   * exceptions:    throws unchecked exception if priority queue is empty 
   */
  Object peekMin(); 
}