nodelist.java

为什么这个网站要弄这么麻烦啊？？真是搞不明白

public class NodeList implements List {
  protected int numElts;            	// Number of items in the list
  protected DNode header, trailer;	// Special sentinels
// Constructor; O(1) time
  public NodeList() {
    numElts = 0;
    header = new DNode(null, null, null);	// create header
    trailer = new DNode(header, null, null);	// create trailer
    header.setNext(trailer);	// make header and trailer point to each other
  }
  // Convenience function; O(1) time
  protected DNode checkPosition(Position p) 
	throws InvalidPositionException {
    if (p == null)
      throw new InvalidPositionException
	("Null Position passed to NodeList.");
    if (p == header)
	throw new InvalidPositionException
	  ("The header node is not a valid position");
    if (p == trailer)
	throw new InvalidPositionException
	  ("The trailer node is not a valid position");
    try {
      DNode temp = (DNode)p;
      if ((temp.getPrev() == null) || (temp.getNext() == null))
	throw new InvalidPositionException
	  ("Position does not belong to a valid NodeList");
      return temp;
    } catch (ClassCastException e) {
      throw new InvalidPositionException
	("Position is of wrong type for this container.");
    }
  }
  // Simple accessor methods:
  public int size() {  return numElts; }		// O(1) time
  public boolean isEmpty() { return (numElts < 1); }	// O(1) time
  public boolean isFirst(Position p)			// O(1) time
      throws InvalidPositionException {  
    DNode v = checkPosition(p);
    return v.getPrev() == header;
  }
  public boolean isLast(Position p)			// O(1) time
      throws InvalidPositionException {  
    DNode v = checkPosition(p);
    return v.getNext() == trailer;
  }
 public Position first()				// O(1) time
      throws EmptyContainerException {
    if (isEmpty())
      throw new EmptyContainerException("List is empty");
    return header.getNext();
  }
  public Position last()				// O(1) time
      throws EmptyContainerException {
    if (isEmpty())
      throw new EmptyContainerException("List is empty");
    return trailer.getPrev();
  }
  public Position before(Position p)			// O(1) time
      throws InvalidPositionException, BoundaryViolationException {
    DNode v = checkPosition(p);
    DNode prev = v.getPrev();
    if (prev == header)
      throw new BoundaryViolationException
	("Cannot advance past the beginning of the list");
    return prev;
  }
  public Position after(Position p)			// O(1) time
      throws InvalidPositionException, BoundaryViolationException {
    DNode v = checkPosition(p);
    DNode next = v.getNext();
    if (next == trailer)
      throw new BoundaryViolationException
	("Cannot advance past the ending of the list");
    return next;
  }
  public Position insertBefore(Position p, Object element) 
      throws InvalidPositionException {			// O(1) time
    DNode v = checkPosition(p);
    numElts++;
    DNode newNode = new DNode(v.getPrev(), v, element);
    v.getPrev().setNext(newNode);
    v.setPrev(newNode);
    return newNode;
  }
  public Position insertAfter(Position p, Object element) 
      throws InvalidPositionException {			// O(1) time
    DNode v = checkPosition(p);
    numElts++;
    DNode newNode = new DNode(v, v.getNext(), element);
    v.getNext().setPrev(newNode);
    v.setNext(newNode);
    return newNode;
  }
  public Position insertFirst(Object element) {		// O(1) time
    numElts++;
    DNode newNode = new DNode(header, header.getNext(), element);
    header.getNext().setPrev(newNode);
    header.setNext(newNode);
    return newNode;
  }
  public Position insertLast(Object element) {		// O(1) time
    numElts++;
    DNode newNode = new DNode(trailer.getPrev(), trailer, element);
    trailer.getPrev().setNext(newNode);
    trailer.setPrev(newNode);
    return newNode;
  }
  public Object remove(Position p)			// O(1) time
      throws InvalidPositionException {
    DNode v = checkPosition(p);
    numElts--;
    DNode vPrev = v.getPrev();
    DNode vNext = v.getNext();
    vPrev.setNext(vNext);
    vNext.setPrev(vPrev);
    Object vElem = v.element();
    // unlink the position from the list and make it invalid
    v.setNext(null);
    v.setPrev(null);
    return vElem;
  }

  public Object replaceElement(Position p, Object element)
      throws InvalidPositionException {			// O(1) time
    DNode v = checkPosition(p);
    Object oldElt = v.element();
    v.setElement(element);
    return oldElt;
  }
    
  public void swapElements(Position a, Position b)
      throws InvalidPositionException {			// O(1) time
    DNode pA = checkPosition(a);
    DNode pB = checkPosition(b);
    Object temp = pA.element();
    pA.setElement(pB.element());
    pB.setElement(temp);
  }
}