比较 <code>LinkedList</code> 和 <code>ArrayList</code>

29 浏览
0 Comments

比较 <code>LinkedList</code> 和 <code>ArrayList</code>

这个问题已经有了答案：

何时在Java中使用LinkedList而不是ArrayList？

我知道LinkedList是实现为双向链表。它在添加和删除方面的性能比ArrayList更好，但在获取和设置方法方面则更差。

这是否意味着我应该在插入时选择LinkedList而不是ArrayList？

我写了一个小测试，发现ArrayList在插入方面更快。那么链表如何比ArrayList更快呢？

请参考我下面的示例。

    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 integerList = new LinkedList();
            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);
        }
    }

admin 更改状态以发布 2023年5月21日
0

2 答案

0 Comments

LinkedList 的确在插入时更快，问题在于您的示例。在您的代码中，您始终将元素追加到末尾进行插入。对于 ArrayList，它和 LinkedList 一样容易。您应该先构建一个包含5000个项目的列表，然后开始在中间进行插入。这时数组会变慢 - 您必须不断移动插入位置之后的所有其他元素。这就是差异所在。分析事物的工作原理并不难理解其原因。以下是修改后的代码：

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 integerList = new LinkedList();
            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);
        }
}

0
0 Comments

LinkedList 在插入方面并不比 ArrayList 更快。 ArrayList 由一个数组支持，所以插入元素很简单。而向 LinkedList 中插入元素则涉及创建一个新的 Entry 实例，这会更慢。

唯一情况下 ArrayList 插入可能较慢的是，当插入导致 ArrayList 的容量增加时，需要创建一个新数组并将旧数组复制到其中。

0