nodelist.java

用java实现的LinkedList二叉树

/*
 * Created on 2005-10-18
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */

/**
 * @author dieks
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */

package linkedBinaryTree;

public class NodeList implements List{
	
	private DNode head, tail;

	private int size;
	
    public NodeList() {
        head = new DNode(null, null, null);
        tail = new DNode(null, head, null);
        head.setNext(tail);
        size = 0;
    }

    protected DNode checkPosition(Position p) throws InvalidPositionException {
        if (p == null) throw new InvalidPositionException("Null position passed to NodeList");
        if (p == head) throw new InvalidPositionException("The head is not a valid position");
        if (p == tail) throw new InvalidPositionException("The tail is not a valid position");

        try {
            DNode temp = (DNode) p;
            if ((temp.getPrev() == null) || (temp.getNext() == null))
                throw new InvalidPositionException("Not a valid position");
            return temp;
        } catch (ClassCastException cce) {
            throw new InvalidPositionException("Position is incorrect for this type of list");
        }
    }

	public int size(){
		return size;
	}
    
	public boolean isEmpty(){
    	return (size==0);
    }
    
	public Position first(){
    	return head.getNext();
    }
    
	public Position last(){
    	return tail.getPrev();
    }
    
    public Position prev(Position p) throws BoundaryViolationException{
    	DNode node = checkPosition(p);
    	return node.getPrev();
    }
    
    public Position next(Position p) throws BoundaryViolationException{
    	DNode node = checkPosition(p);
    	return node.getNext();
    }

    public Position insertFirst(Object e){
    	DNode node = new DNode(e, head, head.getNext());
    	head.getNext().setPrev(node);
    	head.setNext(node);
    	size++;
    	//System.out.println(node.element().toString()+size);
    	return node;
    }
    
    public Position insertLast(Object e){
    	DNode node = new DNode(e, tail.getPrev(), tail);
    	tail.getPrev().setNext(node);
    	tail.setPrev(node);
    	size++;
    	return node;
    }
    
    public Position insertBefore(Position p, Object e) throws InvalidPositionException{
    	DNode node = checkPosition(p);
    	DNode newNode = new DNode(e, node.getPrev(), node);
    	node.getPrev().setNext(newNode);
    	node.setPrev(newNode);
    	size++;
    	return newNode;
    }
    
    public Position insertAfter(Position p, Object e) throws InvalidPositionException {
    	DNode node = checkPosition(p);
    	DNode newNode = new DNode(e, node, node.getNext());
    	node.getNext().setPrev(newNode);
    	node.setNext(newNode);
    	size++;
    	return newNode;
    } 
   
    public Object replace(Position p, Object e) throws InvalidPositionException{
    	DNode node = checkPosition(p);
    	Object element = node.element();
    	DNode newNode = new DNode(e, node.getPrev(), node.getNext());
    	node.getPrev().setNext(newNode);
    	node.getNext().setPrev(newNode);
    	return element;
    }
  
    public Object remove(Position p) throws InvalidPositionException {
        DNode node = checkPosition(p);
        Object element = node.element();
        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());
        node. setPrev(null);
        node.setNext(null);
        size--;
        return element;
    }
    
    
    public void printList(){
    	DNode node = head.getNext();
    	//System.out.println(size);
    	for(int i=0;i<size;i++){
    		System.out.print(node.element().toString()+" ");
    		node = node.getNext();
    	}
    	System.out.println();
    }
}