Java数组实现双向链表

package com.luna.util;

/**
 * 定义双向链表结构对象：考虑到双向链表可以存储基本数据类型、字符串、对象故节点封装用泛型参数；考虑到双向链表数据结构的隐私和安全性，
 * 链表的所有属性和节点内部定义类均用private修饰；数组的特点是：数据是一次性开辟连续的存储空间；随机访问速度快；双向链表：双向链表
 * (双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双
 * 向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
 * 1.定义双向链表的两个私有基本属性：链表头结点和链表的容量；
 * 2.用私有内部类定义双向链表的节点结构；
 * 3.定义链表初始化构造函数；
 * 4.定义链表的基本操作：获取链表节点数方法；判断链表是否为空方法；获取指定位置的节点对象；获取指定位置的节点值；获取第一个节点的值；
 * 获取最后一个节点的值；将节点插入到指定位置；将节点插入到第一个节点处；将节点追加到链表末尾；删除给定位置的链表节点；删除第一个节点；
 * 删除最后一个节点。
 *
 */
public class ArryToDoubleLinked<T> {

    // 定义链表表头节点
    private DNode<T> mHead;
    // 链表节点个数
    private int mCount;

    // 双向链表结构体
    private class DNode<T> {
        public DNode prev;
        public DNode next;
        public T value;

        public DNode(T value, DNode prev, DNode next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

    // 构造函数
    public ArryToDoubleLinked() {
        // 初始化链表初始信息节点
        mHead = new DNode<T>(null, null, null);
        mHead.prev = mHead.next = mHead;
        // 初始化链表节点数为0
        mCount = 0;
    }

    // 返回节点数目
    public int size() {
        return mCount;
    }

    // 返回链表是否为空
    public boolean isEmpty() {
        return mCount == 0;
    }

    // 获取第index位置的节点
    private DNode<T> getNode(int index) {
        if (index < 0 || index >= mCount)
            throw new IndexOutOfBoundsException();
        // 如果待取的数据节点小于等于链表长度的一半时正向查找
        if (index <= mCount / 2) {
            DNode<T> node = mHead.next;
            for (int i = 0; i < index; i++)
                node = node.next;
            return node;
        }

        // 反向查找
        DNode<T> rnode = mHead.prev;
        int rindex = mCount - index - 1;
        for (int j = 0; j < rindex; j++)
            rnode = rnode.prev;
        return rnode;
    }

    // 获取第index位置的节点的值
    public T get(int index) {
        return getNode(index).value;
    }

    // 获取第1个节点的值
    public T getFirst() {
        return getNode(0).value;
    }

    // 获取最后一个节点的值
    public T getLast() {
        return getNode(mCount - 1).value;
    }

    // 将节点插入到第index位置之前
    public void insert(int index, T t) {
        if (index == 0) {
            DNode<T> node = new DNode<T>(t, mHead, mHead.next);
            mHead.next.prev = node;
            mHead.next = node;
            mCount++;
            return;
        }

        DNode<T> inode = getNode(index);
        DNode<T> tnode = new DNode<T>(t, inode.prev, inode);
        inode.prev.next = tnode;
        inode.next = tnode;
        mCount++;
        return;
    }

    // 将节点插入第一个节点处。
    public void insertFirst(T t) {
        insert(0, t);
    }

    // 将节点追加到链表的末尾
    public void appendLast(T t) {
        DNode<T> node = new DNode<T>(t, mHead.prev, mHead);
        mHead.prev.next = node;
        mHead.prev = node;
        mCount++;
    }

    // 删除index位置的节点
    public void del(int index) {
        DNode<T> inode = getNode(index);
        inode.prev.next = inode.next;
        inode.next.prev = inode.prev;
        inode = null;
        mCount--;
    }

    // 删除第一个节点
    public void deleteFirst() {
        del(0);
    }

    // 删除最后一个节点
    public void deleteLast() {
        del(mCount - 1);
    }

    public static void main(String[] args) {
        doubleLinkedTest();
    }

    /**
     * 双向链表测试方法
     */
    private static void doubleLinkedTest() {
        String[] testArr = {"ten", "twenty", "thirty", "forty"};
        System.out.println("\n----string_test----");
        // 创建双向链表
        ArryToDoubleLinked<String> ArryToDoubleLinked = new ArryToDoubleLinked<String>();
        ArryToDoubleLinked.insert(0, testArr[1]);   //  将testArr中第2个元素插入到第一个位置
        ArryToDoubleLinked.appendLast(testArr[0]);        //  将testArr中第1个元素追加到链表末尾
        ArryToDoubleLinked.insertFirst(testArr[2]);       //  将testArr中第3个元素插入到第一个位置
        // 双向链表的节点个数
        System.out.printf("size()=%d\n", ArryToDoubleLinked.size());
        // 循环遍历打印出双向链表全部的节点
        for (int i = 0; i < ArryToDoubleLinked.size(); i++)
            System.out.println("dlink(" + i + ")=" + ArryToDoubleLinked.get(i));
    }
}