public class FavoriteList {
  protected List fList;               // List of entries
  /** Constructor; O(1) time */
  public FavoriteList() { fList = new NodeList(); }
  /** Return the number of elements in the list; O(1) time */
  public int size() { return fList.size(); }
  /** Return true iff the list is empty; O(1) time */
  public boolean isEmpty() { return fList.isEmpty(); }
  /** Find the position of an element; O(n) time */
  protected Position find(Object obj) {
    if (fList.isEmpty()) return null;
    Position p;
    for (p = fList.first(); p != fList.last(); p = fList.next(p))
      if (value(p).equals(obj)) return p; // found it
    if (value(p).equals(obj)) return p; // found it at end
    return null;         // we have not found it
    }
  /** Find and remove a given object if it's in the list; O(n) time */
  public Object remove(Object obj) {
    Position pos = find(obj);        // Search for obj in the favorites list
    if (pos == null) return null;    // obj is not in the list in this case
    Entry ent = entry(pos);
    fList.remove(pos);	 // remove this entry from the favorites list
    return ent.value();  // return the removed object
    }
  /** Incr. access count for obj or insert it if it's not present; O(rank(obj)) time */
  public void access(Object obj) {
    Position pos = find(obj);         // search for obj in the favorites list
    if (pos != null)                  // obj is in the favorites list
      entry(pos).incrementCount();    // increment obj's access count
    else                              // obj is not in list, so add it at end
      pos = fList.insertLast(new Entry(obj));
    moveUp(pos);                      // We may want to move obj up in fList
    }
  /** Move up an entry in the favorites list if needed;  O(n) time */
  protected void moveUp(Position pos) {
    Entry ent = entry(pos);           // the entry for obj
    for (Position prev=null; pos != fList.first();) { // Move ent to correct position
      prev = fList.prev(pos);         // the position before obj's
      if (ent.count() <= entry(prev).count()) break; // obj now at correct position
      Object temp = prev.element();   // move obj up in the favorites list
      fList.replace(prev,pos.element());      
      fList.replace(pos,temp);
      pos = fList.prev(pos);          // go to prev position (new pos. for ent)
      }
    }