Java，添加时间LinkedList与ArrayList [英] Java, Adding time LinkedList vs ArrayList

问题描述

仅将整数添加到Arraylist和Linkedlist的最后一个位置，为什么在arrayList中添加比在链表中更快？我编译了很多次，为什么添加arraylist更快，为什么呢？

据我所知，ArrayList复制2 ^ n + 1大小的数组。而链表仅更改节点

  class Test1 {
 
 public static void main（String [] args ）{
 ArrayList< Integer> arrayList = new ArrayList<>（）; 
 LinkedList< Integer> linkedList =新的LinkedList<>（）; 
 
 addToList（arrayList）; 
 System.out.println（ -----------------）; 
 addToList（linkedList）; 
 
} 
 
 public static void addToList（List list）{
 long start = System.currentTimeMillis（）; 
 for（int i = 0; i< 5_000_000; i ++）{
 list.add（i）; 
} 
 long end = System.currentTimeMillis（）; 
 System.out.println（end-start）; 
 
} 
 
} 
  

解决方案

当您添加到 ArrayList 时，只需将整数存储在支持数组中。每隔一段时间，当后备阵列填满时，您必须分配一个新阵列并将所有旧项目复制到新阵列中。给定500万个整数，您必须进行大约20次分配和复制（取决于列表的初始大小）。

要添加到链表，每次添加都需要您：

1. 为新链表列表节点分配内存并初始化它。


2. 将新节点链接到列表的末尾。

所有这些额外的工作，对于和 LinkedList 是通过 add 方法在后台完成的。 / p>



500万个链表节点分配和链接的开销高于500万个 ArrayList 插入的开销，甚至当您计算 ArrayList 填满时必须执行的20个左右的分配复制操作时。

因此，尽管每个操作都需要恒定的时间（尽管在 ArrayList 情况下它实际上是摊销的恒定时间），但附加到li nked list高于附加到 ArrayList 的常量。

just adding Integer numbers to Arraylist and Linkedlist, to the last position, why adding in arrayList is faster then the linkedlist? I compiled many many times, and adding in arraylist is faster, why?

As I know, ArrayList copies an array by 2^n+1 size. while linkedlist changes only the Node

class Test1 {

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    LinkedList<Integer> linkedList = new LinkedList<>();

    addToList(arrayList);
    System.out.println("-----------------");
    addToList(linkedList);

}

public static void addToList(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < 5_000_000; i++) {
        list.add(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(end - start);

}

}

解决方案

When you add to an ArrayList, you just have to store the integer in the backing array. Every once in a while, when the backing array fills up, you have to allocate a new array and copy all the old items to the new array. Given 5 million integers, you'll have to do that allocate-and-copy about 20 times (depends on the initial size of the list).

To add to a linked list, every addition requires that you:

1. Allocate memory for and initialize a new linked list node.
2. Link the new node to the end of the list.

All that extra work, for both the ArrayList and the LinkedList is done behind the scenes, by the add method.

The overhead for 5 million linked list node allocations and links is higher than the overhead for 5 million ArrayList insertions, even when you count the 20 or so allocate-and-copy operations that the ArrayList has to make when it fills up.

So, whereas each operation takes constant time (although in the ArrayList case it's really amortized constant time), the constant for appending to a linked list is higher than the constant for appending to an ArrayList.

这篇关于Java，添加时间LinkedList与ArrayList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！