双向链表与数组插入操作的对比

Question

在之前的问题：单向链表与数组的插入操作对比中，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);

    }

Answer 1

liuyubobobo 2018-11-27 00:26:14

大赞实践精神！也感谢分享：）

印象里之前回答过你，对于链表来说，最大的开销在对内存的不断操作上。当数据规模达到一定程度，对内存的不断操作将大大拖慢性能：）请参考这里的第2点：http://coding.imooc.com/learn/questiondetail/89595.html

加油！：）

• 提问者 PerryMore #1

  感谢bobo老师，也就是说，我的计算机对这个数据的规模应该是在“千”这个级别才能体现出双向链表的优势？我可以这样理解吗？

• liuyubobobo 回复 提问者 PerryMore #2

  可以！：）

• 提问者 PerryMore 回复 liuyubobobo #3

  我看过老师说过一个大概的级别数是百万级别，我的却是千级别，是因为我实现的双链表某些地方还有重要的优化点呢还是因为我计算机性能比较差呢（囧）？

点开查看后面5条评论