双链表java实现（二）

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package arthur.datastruct.programe;


import java.util.NoSuchElementException;


/**
 *
 * @author dell
 */
public class MyLinkedList {


    private int size;
    private Node<Object> head;//链表头节点
    private Node<Object> tail;//链表尾节点


    public MyLinkedList(int size, Node<Object> head, Node<Object> tail) {
        this.size = size;
        this.head = head;
    }


    public MyLinkedList() {
        this.clear();
    }


    /**
     * 清空链表，注意清空链表的时候只剩下首尾两个相连的空节点
     */
    public void clear() {
        this.head = new Node<Object>(null, null, null);
        this.tail = new Node<Object>(null, head, null);
        this.size = 0;
        this.head.next = this.tail;
    }


   
    /**
     * 获得第index个节点
     * @param index
     * @return 
     */
    public Node<Object> get(int index) {


        return this.getNode(index);
    }


    public Object getValueOfIndex(int index) {
        return this.getNode(index).data;
    }


    /**
     * 删除节点的时候，让removeNode的后继节点的前驱指向removeNode的前驱，
     * removeNode几点的后继指向removeNode的后继即可实现删除操作
     * @param removeNode
     * @return 
     */
    private Object remove(Node<Object> removeNode) {
        if (null == removeNode) {
            throw new NoSuchElementException();
        }
        removeNode.next.pre = removeNode.pre;
        removeNode.pre.next = removeNode.next;
        this.size--;
        return removeNode.data;
    }


    /**
     * 删除第index个节点，注意在删除最后一个结点的时候判断条件是index == size-1
     * 而不是index==size
     * @param index
     * @return 
     */
    public Node<Object> remove(int index) {
        Node<Object> node = this.get(index);
        if(index == this.size-1){
            this.tail = node.pre;
            this.size--;
        }else{
             this.remove(node);
        }
       
        return node;
    }


    /**
     * get the length of list
     * @return size
     */
    public int size() {
        return size;
    }


    /**
     * whether the list is impty or not
     * @return 
     */
    public boolean isEmpty() {
        return 0 == size;
    }


    public Node<Object> getHead() {
        return head;
    }


    public void setHead(Node<Object> head) {
        this.head = head;
    }


    public Node<Object> getTail() {
        return tail;
    }


    public void setTail(Node<Object> tail) {
        this.tail = tail;
    }


    /**
     * 添加节点，
     * @return 
     */
    private boolean addFirst(Node<Object> node) {
        if (null == node) {
            throw new NullPointerException();
        }
        if (0 == size) {
            node.pre = head;
            head.next = node;
        } else {
            node.pre = tail;
            tail.next = node;
        }
        tail = node;//让尾结点指向刚添加的那个点，这一点至关重要
        this.size++;
        return true;
    }


    private void add(Node<Object> node) {
        this.addFirst(node);
    }


    /**
     * 添加值为Object的结点，注意要把结点封装到内部类Node里面
     * @param object 
     */
    public void add(Object object) {
        this.add(new Node(object, null, null));
    }


    /**
     * 获得第index个结点
     * @param index
     * @return 
     */
    private Node<Object> getNode(int index) {
        Node<Object> node = null;
        if (index < 0 || index > this.size()) {
            throw new IndexOutOfBoundsException();
        }
        //折半的形式查找，如果index不大于二分之一的链表长度，从头开始遍历
        if (index <= this.size() >> 1) {
            node = this.head.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {//如果index大于二分之一的链表长度，从尾部开始遍历
            node = this.tail;
            for (int i = size() - 1; i > index; i--) {
                node = tail.pre;
            }
        }


        return node;
    }


    /**
     * 在第index位置加入结点
     * @param index
     * @param node 
     */
    private void add(int index, Node<Object> node) {


        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException();
        }


        if (index == size()) {//如果index等于size，即在尾部加入
            this.add(node);
        } else if (0 == index) {//如果0==index在首部加入
            node.pre = head;
            node.next = head.next;
            head.next = node;
            head.next.pre = node;
        } else {//在链表中间插入
            //获得index之前的那个结点
            Node<Object> nodeBeforeIndex = this.get(index - 1);
            node.pre = nodeBeforeIndex;
            node.next = nodeBeforeIndex.next;
            nodeBeforeIndex.next = node;
            nodeBeforeIndex.next.pre = node;
        }


        this.size++;
    }


    /**
     * 在第index位置插入值为Object的结点
     * @param index
     * @param object 
     */
    public void add(int index, Object object) {
        this.add(index, new Node(object, null, null));
    }
    
    /**
     * 结点类，为内部类
     * @param <Object> 
     */
     private class Node<Object> {


        public Object data;//节点数据
        public Node<Object> pre;//前驱节点
        public Node<Object> next;//后继节点


        public Node(Object data, Node<Object> pre, Node<Object> next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }


        public Node() {
        }


        public String toString() {
            return data + "";
        }
    }


}