双向链表（java实现）

相比于单项链表，双向链表有一个前驱指针，指示当前节点的直接前驱， 这样在查找前驱时更加方面，时间复杂度O（1）， 而单链表要查找前驱则需要重新从头遍历直至i-1位置找到前驱节点，时间复杂度为O（n）。

双向链表单个节点的结构如下图所示；

双向链表节点

当双向链表为空表是，仅有一个头节点，且头节点的前驱和后继指针都指向其自身；

空表head.png

在非空表中，每个节点都有自己的前驱和后继，最后一个节点的后继为头节点，头节点的前驱为最后一个节点；

非空表.png

根据以上逻辑，用java实现双链表如下；

/**
 * circular list.
 * @param <T> element type
 */
public class CircularNodeList<T extends Comparable> {
    private int size;
    private Node2<T> head = new Node2<>();

    /**
     * constructor. create an empty list.
     */
    public CircularNodeList() {
        size = 0;
        head.next = head;
        head.previous = head;
    }

    /**
     * identify if list is empty.
     * @return <code>true</code> if empty
     */
    public boolean isEmpty() {
        return head.next == head && head.previous == head;
    }

    /**
     * find element node by specific position.
     * @param position position specific
     * @return the node
     */
    public Node2<T> find(int position) {
        if (position < 1 || position > size) {
            throw new IndexOutOfBoundsException("position should between 1 to " + size);
        }
        Node2<T> current = head;
        int idx = 0;

        while (idx < position) {
            current = current.next;
            idx++;
        }
        
        if (current != head) {
            return current;
        }
        return null;
    }

    /**
     * insert at list tail.
     * @param data data of the node to be insert
     */
    public void insert(T data) {
        insert(data, size + 1);
    }

    /**
     * insert new node at specific position.
     * @param data new node data
     * @param position specific position
     */
    public void insert(T data, int position) {
        Node2<T> newNode = new Node2<>();
        newNode.data = data;

        // if it is to be insert at list tail
        if (position == size + 1) {
            newNode.previous = head.previous.next;
            head.previous.next = newNode;
            newNode.next = head;
            head.previous = newNode;
            size++;
            return;
        }
        // if it is to be insert in the existing list.
        Node2<T> node = find(position);
        if (node != null) {
            node.previous.next = newNode;
            newNode.previous = node.previous;
            node.previous = newNode;
            newNode.next = node;
            size++;
        }
    }

    /**
     * delete node at specific position from list
     * @param position specific position
     * @return the data deleted
     */
    public T delete(int position) {
        T data = null;
        if (position < 1 || position > size) {
            throw new IndexOutOfBoundsException("position should between 1 to " + size);
        }
        Node2<T> node = find(position);
        if (node != null) {
            node.previous.next = node.next;
            node.next.previous = node.previous;
            size--;
            data = node.data;
        }
        return data;
    }

    /**
     * get the prior of the specific position node.
     * @param position specific position
     * @return the prior of the specific node
     */
    public Node2<T> getPrior(int position) {
        Node2<T> node = find(position);
        return node.previous;
    }

    /**
     * get the next of the specific position node.
     * @param position specific position 
     * @return the next of th specific node
     */
    public Node2<T> getNext(int position) {
        Node2<T> node = find(position);
        return node.next;
    }

    public int getSize() {
        return this.size;
    }
 
}

class Node2<T> {
    T data;
    Node2<T> next;
    Node2<T> previous;
}