Java数据结构（四）：线性表之双向链表

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

具体代码可参见：BidirectionalLinkedList.java

package datastructure.linear.linked;

import datastructure.exception.StructureException;
import datastructure.linear.AbstractList;

/**
 * @Description 双向链表实现
 * @author mastery
 * @Date 2015年6月30日下午9:11:51
 */
public class BidirectionalLinkedList<T> extends AbstractList<T> {

    class Node<T1> {
        /**
         * 数据域
         */
        T1 element;

        /**
         * 指向前驱结点的指针
         */
        Node<T1> prior;

        /**
         * 指向后继结点的指针
         */
        Node<T1> next;

        public Node(Node<T1> next) {
            super();
            this.prior = next;
            this.next = next;
        }

        public Node(T1 element, Node<T1> prior, Node<T1> next) {
            super();
            this.element = element;
            this.prior = prior;
            this.next = next;
        }

    }

    private Node<T> head;

    private Node<T> currentNode;

    public BidirectionalLinkedList() {
        head = currentNode = new Node<T>(null);
        size = 0;
    }

    /**
     * 得到当前下标对应的结点
     * 
     * @param index
     * @throws StructureException
     */
    public void indexNodeToCurrent(int index) throws StructureException {
        currentNode = head;
        if (index < -1 || index > size - 1) {
            throw new StructureException("index参数异常！");
        }
        if (index == -1) {
            return;
        }
        currentNode = head.next;
        int j = 0;
        while (currentNode != null && j < index) {
            currentNode = currentNode.next;
            j++;
        }
    }

    @Override
    public void insert(int index, T t) throws StructureException {
        if (index < 0 || index > size) {
            throw new StructureException("index参数异常！");
        }
        // 得到当前下标的上一个结点
        indexNodeToCurrent(index - 1);
        Node<T> insertNode = new Node<T>(t, currentNode, currentNode.next);
        if (currentNode.next != null) {
            // 将新元素生成结点插入到当前结点下
            currentNode.next.prior = insertNode;
        }
        currentNode.next = insertNode;
        size++;
    }

    @Override
    public void delete(int index) throws StructureException {
        if (isEmpty()) {
            throw new StructureException("链表为空");
        }
        if (index < 0 || index > size) {
            throw new StructureException("index参数异常");
        }
        indexNodeToCurrent(index - 1);
        Node<T> twoNextNode = currentNode.next.next;
        if (twoNextNode != null) {
            twoNextNode.prior = currentNode;
        }
        currentNode.next = twoNextNode;
        size--;
    }

    @Override
    public T get(int index) throws StructureException {
        if (isEmpty()) {
            throw new StructureException("链表为空");
        }
        if (index < 0 || index > size) {
            throw new StructureException("index参数异常！");
        }
        indexNodeToCurrent(index);
        return currentNode.element;
    }

}