Linkedlist 与 arraylist 的比较 [英] comparison of Linkedlist over arraylist

问题描述

我知道 LinkedList 是作为双链表实现的.它在 add 和 remove 上的性能优于 Arraylist，但在 get 和 set 方法上的性能较差.

I understood that LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods.

这是否意味着我应该选择 LinkedList 而不是 Arraylist 进行插入?

Does that mean I should choose LinkedList over Arraylist for inserting?

我写了一个小测试，发现 ArrayList 插入速度更快.那么链表如何比ArrayList更快?

I wrote a small test and found ArrayList is faster in inserting. Then how does linked list faster than ArrayList?

请参考下面我做的例子.

Please refer the below example which I have done.

    import java.util.Date;
    import java.util.LinkedList;
    import java.util.List;

    public class TestLinkedList {

        public static void main(String[] args) {

            long lStartTime = new Date().getTime();
            System.out.println("lStartTime:: " + lStartTime);
            List<Integer> integerList = new LinkedList<Integer>();
            for (int i = 0; i < 10000000; i++) {
                integerList.add(i);
            }

            long lEndTime = new Date().getTime();
            System.out.println("lEndTime:: " + lEndTime);

            long difference = lEndTime - lStartTime;

            System.out.println("Elapsed milliseconds: " + difference);

        }

    }

推荐答案

Linkedlist 在插入时确实更快，问题出在您的示例上.在您的代码中，您始终通过附加到末尾来插入.对于 ArrayList 和 LinkedList 一样简单.您应该做的是构建一个包含 5000 个项目的列表，然后开始在中间插入.这里数组变得很慢 - 你必须在插入位置之后一直移动数组的其余部分.这将显示差异.分析事情是如何运作的，不难理解为什么.修改后的代码如下:

Linkedlist is indeed faster on insertion, the problem is with your example. In your code you insert by appending to the end all the time. For ArrayList it is as easy as for LinkedList. What you should do is to build a list of say 5000 items and then start inserting in the middle. Here array becomes slow - you have to shift all the time the rest of the array after the insertion position. This is what will show the difference. Analyzing how the things work, it is not difficult to understand why. Here is the modified code:

import java.util.Date;
    import java.util.LinkedList;
    import java.util.ArrayList;
    import java.util.List;

    public class Prob {

        public static void main(String[] args) {

            long lStartTime = new Date().getTime();
            System.out.println("lStartTime:: " + lStartTime);
            List<Integer> integerList = new LinkedList<Integer>();
            for (int i = 0; i < 5000; i++) {
                integerList.add(0, i);
            }
            for (int i = 0; i < 100000; i++) {
                integerList.add(1000, i);
            }

            long lEndTime = new Date().getTime();
            System.out.println("lEndTime:: " + lEndTime);

            long difference = lEndTime - lStartTime;

            System.out.println("Elapsed milliseconds: " + difference);

        }
}

这篇关于Linkedlist 与 arraylist 的比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！