在之前的问题：单向链表与数组的插入操作对比中，bobo老师解答了这个问题时，刚好给了这个问题另一个解答的链接关于链表，这个问题中总结了链表的优势，其中第四点如下：

对于java.util.LinkedList底层的循环双链表来说，在指定位置插入元素，或者删除指定位置的元素，实际最多只需要遍历n/2个元素就好了。虽然复杂度依然是O(n)的，但当元素个数没有超过一定限制的时候（不同计算机不一样，大概100万级别），平均比动态数组的O(n)快。

于是我去实现了一个双向链表（但是有可能有问题，不能保证就是波波老师提到的双向链表的实现），实验的结果如下：

1万数据量
array time: 0.047144803
two way linked time: 0.13551119

3万数据量
array time: 0.680139719
two way linked time: 2.778740039

5万数据量
array time: 1.651763787
two way linked time: 7.275409638

我的双向链表代码如下（删除功能暂时还没有实现）：

public class TowWayLinkedList<E> {
    private class Node {
        public E e;
        public Node pre, next;

        public Node(E e) {
            this(e, null, null);
        }

        public Node(E e, Node pre) {
            this(e, pre, null);
        }

        public Node(E e, Node pre, Node next) {
            this.e = e;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyHead;
    private Node dummyTail;
    private int size;

    public TowWayLinkedList() {
        dummyHead = new Node(null);
        dummyTail = new Node(null);

        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;

        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }

    public void add(int index, E e) {

        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index is illegal");
        }

        Node cur;
        if (index <= size / 2) {
            cur = dummyHead;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }

        } else {
            cur = dummyTail.pre;
            for (int i = size; i > index; i--) {
                cur = cur.pre;
            }

        }

        Node node = new Node(e, cur, cur.next);
        cur.next.pre = node;
        cur.next = node;

        size++;

    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format(Locale.getDefault(), "linked size: %d个元素
", size));

        Node curNode = dummyHead.next;
        while (curNode != dummyTail) {
            sb.append(curNode.e).append("->");
            curNode = curNode.next;
        }
        sb.append("NULL");

        return sb.toString();
    }
}

实验结果还是没有达到预期效果…这是我代码问题还是说其他原因呢？按理说，每次确实会省掉一半的寻址过程。可是双向循环链表还是没有跑赢数组。这是啥原因呢？

求bobo老师解答！

补充测试代码

    public static void main(String[] args) {
        int opCount = 3000;

        Array<Integer> array = new Array<>();
        Random random = new Random();
        Random randomIndex = new Random();

        long start1 = System.nanoTime();
        for (int i = 0; i < opCount; i++) {
            array.add(randomIndex.nextInt(array.getSize() + 1), random.nextInt(10000));
        }
        long end1 = System.nanoTime();

        double time1 = (end1 - start1) / 1000000000.0;
        System.out.println("array time: " + time1);

        TowWayLinkedList<Integer> towWayLinkedList = new TowWayLinkedList<>();
        long start3 = System.nanoTime();
        for (int i = 0; i < opCount; i++) {
            towWayLinkedList.add(randomIndex.nextInt(towWayLinkedList.getSize() + 1), random.nextInt(10000));
        }

        long end3 = System.nanoTime();
        double time3 = (end3 - start3) / (1000 * 1000 * 1000.0);
        System.out.println("two way linked time: " + time3);

    }