Java LinkedList and Search Tree

abstract Class ListItem

package abstract_exp;

public abstract class ListItem{
    protected ListItem rightLink;
    protected ListItem leftLink;
    protected Object value;

    public ListItem(Object value) {
        this.value = value;
    }

    abstract ListItem next();
    abstract ListItem setNext(ListItem item);
    abstract ListItem prev();
    abstract ListItem setPrev(ListItem item);
    abstract int compareTo(ListItem other);

    public Object getValue(){
        return value;
    }

    public void setValue(Object value){
        this.value = value;
    }
}

下面是interface 

public interface NodeList {
    ListItem getRoot();
    boolean addItem(ListItem newItem);
    boolean removeItem(ListItem item);
    void traverse(ListItem root);

}

Node 

public class Node extends ListItem {
    public Node(Object value) {
        super(value);
    }

    @Override
    ListItem next() {
        return this.rightLink;
    }

    @Override
    ListItem setNext(ListItem item) {
        this.rightLink = item;
        return this.rightLink;
    }

    @Override
    ListItem prev() {
        return leftLink;
    }

    @Override
    ListItem setPrev(ListItem item) {
        this.leftLink = item;
        return this.leftLink;
    }

    @Override
    int compareTo(ListItem other) {
        if(other != null){
            return ((String) super.getValue()).compareTo(
                    (String) other.getValue());
        }else{
            return -1;
        }
    }
}

MyLinkedList

public class MyLinkList implements NodeList {
    private ListItem root = null;

    public MyLinkList(ListItem root) {
        this.root = root;
    }

    @Override
    public ListItem getRoot() {
        return this.root;
    }

    @Override
    public boolean addItem(ListItem newItem) {
        if (this.root == null) {
            //The list was empty,
            this.root = newItem;
            return true;
        }
        ListItem currentItem = this.root;
        while (currentItem != null) {
            int comparison = (currentItem.compareTo(newItem));
            if (comparison < 0) {
                //new item is greater, move right if possible
                if (currentItem.next() != null) {
                    currentItem = currentItem.next();
                } else {
                    //There is no next, so insert at end of list
                    currentItem.setNext(newItem);
                    newItem.setPrev(currentItem);
                    return true;
                }
            } else if (comparison > 0) {
                //new Item is less, insert before
                if (currentItem.prev() != null) {
                    currentItem.prev().setNext(newItem);
                    newItem.setPrev(currentItem.prev());
                    newItem.setNext(currentItem);
                    currentItem.setPrev(newItem);
                } else {
                    //the node with a prev is the root
                    newItem.setNext(this.root);
                    this.root.setPrev(newItem);
                    this.root = newItem;
                }
                return true;
            } else {
                //equal
                System.out.println(newItem.getValue() + " is already present at the list");
                return false;
            }
        }
        return false;
    }

    @Override
    public boolean removeItem(ListItem item) {
        if(item != null){
            System.out.println("Deleting item "+item.getValue());
        }
        ListItem currentItem = this.root;
        while(currentItem != null){
            int comparison = currentItem.compareTo(item);
            if(comparison == 0) {
                //found the item to delete
                if(currentItem == this.root){
                    this.root = currentItem.next();
                }else{
                    currentItem.prev().setNext(currentItem.next());
                    if(currentItem.next() != null){
                        currentItem.next().setPrev(currentItem.prev());
                    }
                }
                return true;
            }else if(comparison < 0){
                currentItem = currentItem.next();
            }else{
                //comparison > 0
                //we are at an item greater than the one to be deleted
                //so the item is not in the list
                return false;
            }
        }
        //we have reached the end of the list
        //without finding the item to delete
        return false;
    }

    @Override
    public void traverse(ListItem root) {
        if (root == null) {
            System.out.println("The list is empty");
        } else {
            while (root != null) {
                System.out.println(root.getValue());
                root = root.next();
            }
        }
    }
}

SearchTree

public class SearchTree implements NodeList {
    private ListItem root = null;

    //constructor
    public SearchTree(ListItem root){
        this.root = root;
    }

    @Override
    public ListItem getRoot() {
        return this.root;
    }

    @Override
    public boolean addItem(ListItem newItem) {
        if(this.root == null){
            //the tree was empty, so our item becomes the
            //head of the tree
            this.root = newItem;
            return true;
        }
        //other waise, starting comparing from the head of the tree
        ListItem currentItem = this.root;
        while(currentItem != null){
            int comparison = (currentItem.compareTo(newItem));
            if(comparison < 0){
                //newItem is greater ,move right if possible
                if(currentItem.next() != null){
                    currentItem=currentItem.next();
                }else{
                    //there is no node to the right, so add at this point
                    currentItem.setNext(newItem);
                    return true;
                }
            }else if(comparison > 0){
                //newItem is less, move left is possible
                if(currentItem.prev() != null){
                    currentItem = currentItem.prev();
                }else{
                    //there is no node to the left, so add at this point
                    currentItem.setPrev(newItem);
                    return true;
                }
            }else{
                //equal, so do not add
                System.out.println(newItem.getValue() +" is already existed in ");
                return false;

            }
        }
        //we can not actually get here, but java complains if there's no return
        return false;
    }

    @Override
    public boolean removeItem(ListItem item) {
        if(item !=null){
            System.out.println("Deleting item "+item.getValue());
        }

        ListItem currentItem = this.root;
        ListItem parentItem = currentItem;

        while(currentItem != null){
            int comparison = (currentItem.compareTo(item));
            if(comparison < 0){
                parentItem = currentItem;
                currentItem = currentItem.next();
            }else if(comparison > 0){
                parentItem = currentItem;
                currentItem = currentItem.prev();
            }else{
                //equal, we've found the item so remove it
                performRemove(currentItem, parentItem);
                return true;
            }
        }
        return false;
    }

    private void performRemove(ListItem item, ListItem parent){
        //remove item from the tree
        if(item.next() == null){
            //no right tree, so make parent point to left ree(which may be null)
            if(parent.next() == item){
                //item is rigt child of its parent
                parent.setNext(item.prev());
            }else if(parent.prev() == item){
                //item is left child of its parent
                parent.setPrev(item.prev());
            }else{
                //parent must be item, which means we were looking at the root of the tree
                this.root = item.prev();
            }
        }else if(item.prev()== null){
            //no left tree, so make parent point to right tree(which may be null)
            if(parent.next()==item){
                //item is right child of its parent
                parent.setNext(item.next());
            }else if(parent.prev() == item){
                //item is left child of its parent
                parent.setPrev(item.next());
            }else{
                //again, we are deleting the root
                this.root = item.next();
            }
        }else{
            //neither left nor right are null, deletion is now a lot
            //trickier , From the right sub-tree, find the smallest value
            //ie: the leftmost
            ListItem current=item.next();
            ListItem leftMostParent = item;
            while(current.prev() != null){
                leftMostParent = current;
                current = current.prev();
            }

            //now put the smallest value into our node to be deleted
            item.setValue(current.getValue());
            //and delete the smallest
            if(leftMostParent == item){
                //there was no left most node, so current points to the smallest
                //node (the one that must now be delete)
                item.setNext(current.next());
            }else{
                //set the smallest node's parent to point to
                //the smallest node's right child (which may be null)
                leftMostParent.setPrev(current.next());
            }
        }
    }

    @Override
    public void traverse(ListItem root) {
        if( null){
            traverse(root.prev());
            System.out.println(root.getValue());
            traverse(root.next());
        }
    }
}