数组与链表插入操作比较

Question

以前在网络上看资料说链表类型的数据结构相比数组来说，更加适合进行插入操作，因为只要移动指针就行了。

跟着bobo老师学完自己编写链表后，反倒对插入操作产生了第一个问题：链表虽然在指定位置插入元素时只要改变插入位置前后元素的指针关系，但是每次找到插入位置时其实还是一个o(n)级别的操作。所以相比与数组而言其优势在哪？

第二个问题，是因为链表指针移动相对比数组插入元素后的赋值操作更加快速吗？

而后，我对两种数据结构做了一下插入操作的对比。测试数据我又有点看不懂了。如下：

第三个问题，为何链表会慢这么多？

不知道是我代码写的有问题还是这就是正常现象。测试代码如下：

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

        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);

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

        long end2 = System.nanoTime();
        double time2 = (end2 - start2) / 1000000000.0;
        System.out.println("linked time: " + time2);

    }

Answer 1

liuyubobobo 2018-11-23 04:33:18

大赞实验精神！

1.

“链表比动态数组更适合插入（或者删除）”，这个说法是有条件的！关键在于：链表可以快速的在链表头和链表尾进行插入和删除操作！这是和数组比有优势的地方。如果在链表中间做插入，链表没有任何优势！都是O(n)的。不过，其实大量算法任务，只需要对一个线性表的头尾进行插入删除操作，但数组只能方便的在一段做插入删除：）

关于数组和链表的比较，可以参考这个问答：http://coding.imooc.com/learn/questiondetail/57677.html

2.

你的测试完全没有问题。当数据量变大的时候，链表的性能会很差。这是因为，链表的插入操作，每一次都伴随着内存操作（new），这是很耗时的！而与此同时，在每次插入的时候，如果没有尾指针每次都要遍历到相应的地方，这个遍历过程每次都伴随着寻址过程。而对于数组，一方面，虽然有扩容，但是一次可以处理一大片内存。想想看，5万的数据，扩容次数不会超过20次，也就是只需要有20次new操作，再加上数组支持随机访问，找到待插入的位置，包括后续挪动元素，访址速度是极快的。这些问题导致了你的测试结果。

所以，实际在使用链表的时候，近乎一定会使用带头尾指针的双向量表。维护头尾指针保证了快速在线性表两侧进行插入和删除操作。再次强调：可以快速的在线性表两侧动态维护数据（而不仅仅是一侧），是链表最大的优势：）

继续加油！

• 提问者 PerryMore #1

  感谢bobo老师，您链接里的那个回答链表的优势总结得太赞了，解决了好多疑惑！再次感谢