Performance comparison between ArrayList and LinkedList in java

Performance comparison between ArrayList and LinkedList in java

Looking at the 1 framework code today, you can see that some of the places where you can use ArrayList are using LinkedList, where you can use the scenario of sequential insertion in a loop.

It is well known that the List interface in java has two implementations, ArrayList and LinkedList, which are implemented by arrays and linked lists introduced in c.

As we learned when we learned about data structures, a linked list structure is more efficient for insertion because you can modify the pointer to the node to do the insertion, unlike an array,

You need to move the array elements back from where they were inserted.

But is this really the case? Let's see what we can conclude from a simple example.

public static void main(String[] args) {
    List<String> arrayList = new ArrayList<String>();
    List<String> linkedList = new LinkedList<String>();
    long time1 = System.currentTimeMillis();
    for(int i = 0; i < 1000000; i++) {
      arrayList.add(new String("abc"));
    }
    long time2 = System.currentTimeMillis();
    for(int i = 0; i < 1000000; i++) {
      linkedList.add(new String("abc"));
    }
    long time3 = System.currentTimeMillis();
    System.out.println("arrayList.insert_time = " + (time2 - time1));
    System.out.println("linkedList.insert_time = " + (time3 - time2));
    long time11 = System.currentTimeMillis();
    for(int i = 0; i < 10000; i++) {
      int random = RandomUtils.nextInt(10000);
      String temp = arrayList.get(random);
    }
    long time12 = System.currentTimeMillis();
    for(int i = 0; i < 10000; i++) {
      int random = RandomUtils.nextInt(10000);
      String temp = linkedList.get(random);
    }
    long time13 = System.currentTimeMillis();
    System.out.println("arrayList.read_time = " + (time12 - time11));
    System.out.println("linkedList.read_time = " + (time13 - time12));
  }

Operation results:

arrayList.insert_time = 188
linkedList.insert_time = 250
arrayList.read_time = 16
linkedList.read_time = 234

The results show that, in any case, ArrayList is more efficient. Arrays are 14 times more efficient than linked lists, especially for random reads.

The insertion operation, which takes about the same amount of time, is still a little bit more efficient.

It's not hard to think about why.

When List does not store much, the last element of List is written. ArrayList and LinkedList take about the same amount of time.

But when the number of elements in the List storage is large, by array structure ArrayList inserted at the end of the day can pass an array subscript access to quickly, but LinkedList will need access to each node to insert again, until you find the last element in the steps of time consuming is huge, so the list number, the greater the LinkedList are more.

Of course, for scenarios that require random insertion, LinkedList is better than ArrayList at this point.

Thank you for reading, I hope to help you, thank you for your support of this site!