双向链表的Java实现

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双链表的重要性质就是可以根据任意节点快速获取其前后节点，
所以提供了getPrevNode()和getNextNode()方法；

还有就是，双链表遍历节点时，无需实现任何接口，直接利用节点间的关系即可完成遍历。

public class DoubleLinkedList<T> {

    private int size;//链表大小
    //由于是双向，头尾任意选择一端即可
    private Node<T> head;//链表的头节点
    private Node<T> tail;//链表的尾节点

    /**
     * 内部类：节点
     * @param <T>
     */
    public static class Node<T>{
        private Node prev;
        private Node next;
        private T data;

        public Node(T data){
            this.data = data;
        }

        private Node(){}
    }

    /**
     * 添加到链尾
     * @param data
     */
    public void add(T data){
        add(size, data);
    }

    /**
     * 添加到任意index处
     * @param index
     * @param data
     */
    public void add(int index, T data){
        Node<T> node = new Node<>(data);
        if(isEmpty()){//链表为空
            head = node;
            tail = node;
        }else {
            if(index > size - 1){//索引超出当前链表大小，则添加到链尾
                Node<T> temp = tail;
                tail = node;
                temp.next = tail;
                tail.prev = temp;
            }else {//原index位置处有值，索引位置大于index的元素向链尾移动(实际并不是移动，只是看上去)
                Node<T> origin = getNode(index);
                Node<T> prev = origin.prev;
                prev.next = node;
                node.prev = prev;
                node.next = origin;
                origin.prev = node;
            }
        }

        size++;
    }

    /**
     * 更新index位置处元素的值
     * @param index
     * @param data
     */
    public void set(int index, T data){
        if(index > size - 1 || index < 0){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        getNode(index).data = data;
    }

    /**
     * 删除index位置处的元素
     * @param index
     */
    public void delete(int index){
        if(index > size - 1 || index < 0){
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if(index == 0){//删除链头
            head = head.next;
            head.prev = null;
        }else if(index == size -1){//删除链尾
            tail = tail.prev;
            tail.next = null;
        }else {//普通节点
            Node<T> node = getNode(index);
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            node.prev = null;
            node.next = null;
        }
        size--;
    }

    /**
     * 获取index位置处的元素的值
     * @param index
     * @return
     */
    public T getValue(int index){
        return getNode(index) == null ? null : getNode(index).data;
    }

    public T getValue(Node<T> node){
        return node == null ? null : node.data;
    }

    /**
     * 获取节点node的上一个节点
     * @param node
     * @return
     */
    public Node<T> getPrevNode(Node<T> node){
        return node == null ? null : node.prev;
    }

    /**
     * 获取节点node的下一个节点
     * @param node
     * @return
     */
    public Node<T> getNextNode(Node<T> node){
        return node == null ? null : node.next;
    }

    public Node<T> getHeadNode(){
        return head;
    }

    public Node<T> getTailNode(){
        return tail;
    }

    /**
     * 获取index位置处的元素
     * @param index
     * @return
     */
    public Node<T> getNode(int index){

        if (isEmpty() && (index > size - 1)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> result = head;
        int n = 0;
        while (n < index) {//注意这里是 n < index， 而不是n <= index
            result = result.next;
            n++;
        }
        return result;
    }

    /**
     * 获取值为data的元素在链表中的位置（第一次出现的位置，可能含有多个）
     * @param data
     * @return
     */
    public int indexOf(T data){
        if(isEmpty() || data == null){
            return -1;
        }

        int n = 0;
        Node<T> node = head;
        while (n < size){
            if(data.equals(node.data)){
                return n;
            }
            n++;
        }

        return -1;
    }

    /**
     * 判断是否有值为data的元素
     * @param data
     * @return
     */
    public boolean containValue(T data){
        return indexOf(data) != -1;
    }

    /**
     * 获取链表的大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


}