相比于單項(xiàng)鏈表，雙向鏈表有一個(gè)前驅(qū)指針，指示當(dāng)前節(jié)點(diǎn)的直接前驅(qū)， 這樣在查找前驅(qū)時(shí)更加方面，時(shí)間復(fù)雜度O（1）， 而單鏈表要查找前驅(qū)則需要重新從頭遍歷直至i-1位置找到前驅(qū)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O（n）。

雙向鏈表單個(gè)節(jié)點(diǎn)的結(jié)構(gòu)如下圖所示；

雙向鏈表節(jié)點(diǎn)

當(dāng)雙向鏈表為空表是，僅有一個(gè)頭節(jié)點(diǎn)，且頭節(jié)點(diǎn)的前驅(qū)和后繼指針都指向其自身；

空表head.png

在非空表中，每個(gè)節(jié)點(diǎn)都有自己的前驅(qū)和后繼，最后一個(gè)節(jié)點(diǎn)的后繼為頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的前驅(qū)為最后一個(gè)節(jié)點(diǎn)；

非空表.png

根據(jù)以上邏輯，用java實(shí)現(xiàn)雙鏈表如下；

/**
 * 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;
}