Collections: java.util.ArrayList vs java.util.LinkedList - Adding Elements Comparison

adevedo's picture
0
No votes yet

The Java collections framework (JCF) is a set of classes and interfaces that implement commonly reusable collection data structures. Although it is a framework, it works in a manner of a library. The JCF provides both interfaces that define various collections and classes that implement them. Choosing the right collection for your requirments depends on many factors, how much memory will the selected collection will consume, how much time does it takes to loop on all elements of the collection, how much time deos it takes to get an element by index from the collection, how much time does it takes to add elements to the collection and many many other factors, In this article we establish a comparison between 2 of the most famous collections from the perspective of "Time consumed for adding elements", the linked list (LinkedList) and the array list (ArrayList) and invistigate in both from inside and find why both take that time.

Tests will be done using core I7 1.6 laptop with 8 GB of Ram

Test 1 - Adding 1000000 Integer to ArrayList Object:

  1. for(int t = 0; t < 11; ++t) {
  2.         List<Integer> list = new ArrayList<Integer>();
  3.         Date b = new Date();
  4.         for(int i = 0; i < 1000000; ++i)
  5.                 list.add(i);
  6.         Date a = new Date();
  7.         System.out.println(a.getTime() - b.getTime());
  8. }

When running the following code, the following will be printed on the screen:

  1. 83 // Will be Ignored
  2. 28
  3. 24
  4. 16
  5. 48
  6. 12
  7. 15
  8. 17
  9. 15
  10. 17
  11. 22

I am going to ignore the 1st result because it was affected by class loading in memory by the JVM (Date class, LinkedList class...etc)

The avarage will be 21.4 milliseconds

Test 2 - Adding 10000000 Integer to ArrayList Object:

Using the same code but with modifing the loop end to be 10000000, the result will be:

  1. 1321 // Will be Ignored
  2. 961
  3. 1497
  4. 369
  5. 625
  6. 1140
  7. 416
  8. 745
  9. 583
  10. 617
  11. 1482

Again, I am going to ignore the 1st result...so the avarage will be 843.5 milliseconds

No lets change the code to be working on LinkedList instead of ArrayList:

  1. for(int t = 0; t < 11; ++t) {
  2.         List<Integer> list = new LinkedList<Integer>();
  3.         Date b = new Date();
  4.         for(int i = 0; i < 1000000; ++i)
  5.                 list.add(i);
  6.         Date a = new Date();
  7.         System.out.println(a.getTime() - b.getTime());
  8. }

On 1000000, the result will be:

  1. 236 // Will be Ignored
  2. 395
  3. 25
  4. 86
  5. 521
  6. 16
  7. 16
  8. 262
  9. 20
  10. 19
  11. 190

And the avarage will be 155 milliseconds

On 10000000, the result will be:

  1. 5037 // Will be Ignored
  2. 3821
  3. 4301
  4. 3254
  5. 4659
  6. 4836
  7. 1485
  8. 5056
  9. 3889
  10. 2375
  11. 4573

And the avarage will be 3824.9 milliseconds

As a summary, ArrayList with 1000000 took 21.4 milliseconds, LinkedList took 155 milliseconds, ArrayList with 10000000 took 843.5 milliseconds, LinkedList took 3824.9 milliseconds.

It seems from the above that the ArrayList is much more faster than LinkedList from the side of adding new elements to the collection. Now lets find why is that ?

ArrayList is based on primative array object, so - most of the time - adding new elements costs the following line of code "data[currentSize] = newElement" which costs nothing.
For Linked List, adding new element costs the following:

  • Creating new Entry object with the element as entry data and the next attribute points to the head [dummy] next attribute and previous attribute points to the previous of the head next attribute
  • Setting the next attribute of the new element previous attribute points to the new element
  • Setting the previous attribute of the new element next attribute points to the new element

Which costs a day!

And thats the main reason for why ArrayList is faster than LinkedList when comming to add new element to the collection.

Only one thing is missing here, as the ArrayList is based on primative array, and as primative array size is fixed and never get change after creation, how the ArrayList is able to accommodate new elements with a fixed size primative array (i.e. List internal primative array was of size 10, how to add 11 element to the ArrayList), the answer is in the following lines...

ArrayList uses an expansion algorithm for its internal primative array applied when adding new elements to the list, from the implementation code of the ArrayList in JDK1.6, the method "add" is implemented in that way:

  1. public boolean add(E e) {
  2.         ensureCapacity(size + 1);
  3.         elementData[size++] = e;
  4.         return true;
  5. }

The method add only do 2 things, ensure that the internal array size can hold the new element, and then add the new element to the array. The method ensureCapacity implemented as follows:

  1. public void ensureCapacity(int minCapacity) {
  2.         modCount++;
  3.         int oldCapacity = elementData.length;
  4.         if (minCapacity > oldCapacity) {
  5.             Object oldData[] = elementData;
  6.             int newCapacity = (oldCapacity * 3)/2 + 1;
  7.         if (newCapacity < minCapacity)
  8.                         newCapacity = minCapacity;
  9.         elementData = Arrays.copyOf(elementData, newCapacity);
  10.         }
  11. }

This method checks for the current max size of the internal array, if it is larger than the number of currently added elements to the list, then no expansion will be done, but if it is equals the array size and the array is fully reserved by current elements, then the ArrayList will expand its internal storage (primative array):

  • at first the list will calculate the new array size "newCapacity = (oldCapacity * 3)/2 + 1"
  • it will create a new array of size newCapacity and copy all data (references/primative data) from the old array to the new array, creating the new array is a created with java instructions, but the copying process is done with native code, with System.arraycopy method.
  • then it will update the old array reference to point to the new array object

Ok, now lets find how many expansions were done when adding 10000000 element to the ArrayList (with default initialization) and what was the final size of the ArrayList internal storage, lets use the following code to simulate the case:

  1. // ArrayList default constructor initialize the list with array of 10
  2. int currentArraySize = 10;
  3. int currentElements = 0;
  4. for(int i = 0; i < 10000000; i++) {
  5.         // ensureCapacity(size + 1) ... if (minCapacity > oldCapacity)
  6.         if((currentElements + 1) > currentArraySize) {
  7.                 int newCapacity = (currentArraySize * 3)/2 + 1;
  8.                 System.out.println("On Adding Element #" +
  9.                                                         i + " : Copying Array of size [" +
  10.                                                         currentArraySize +
  11.                                                         "] to Array of size [" +
  12.                                                         newCapacity + "]");
  13.                 currentArraySize = newCapacity;
  14.         }
  15.         currentElements++;
  16.         // New Element will be added to the array at index i
  17. }

The Output will be - the 4th column represent the time taken to perform the copy operation extracted from another test:

Adding Element # Copy Array of Size To New Array of Size Time Taken
10 10 16 0
16 16 25 0
25 25 38 0
38 38 58 0
58 58 88 0
88 88 133 0
133 133 200 0
200 200 301 0
301 301 452 0
452 452 679 0
679 679 1019 1
1019 1019 1529 0
1529 1529 2294 0
2294 2294 3442 0
3442 3442 5164 0
5164 5164 7747 0
7747 7747 11621 0
11621 11621 17432 0
17432 17432 26149 0
26149 26149 39224 1
39224 39224 58837 0
58837 58837 88256 0
88256 88256 132385 1
132385 132385 132385 0
198578 198578 132385 1
297868 297868 132385 1
446803 446803 132385 1
670205 670205 132385 2
1005308 1005308 132385 3
1507963 1507963 132385 4
2261945 2261945 132385 98
3392918 3392918 132385 6
5089378 5089378 132385 9
7634068 7634068 132385 19

As the LinkedList structure is based on linked nodes, it has no expansion algorithm, it just replace the head pointers to the new element.

Thats all now from the perspective of "Time consumed for adding elements", it seems that the ArrayList rocks all the time, in next articles we will discuss other methods in both Collections.

Comments

hosamaly's picture

May I suggest using `System.nanoTime()` instead of `new Date().getTime()`? It should be much more accurate. You could also move the time calculation outside the loop, and do the averaging outside. It should give you the same results. Your code is also measuring the time needed for boxing a million integers. Since you're using integers larger than 127, almost every integer in your loop is created from scratch, without caching. This could represent a significant portion of the measured time. Additionally, it should be noted that this performance comparison is subject to the condition that elements are only *appended* to the list, and never inserted (or deleted) in the beginning or middle. (P.S: it's "primitive", not "primative"...)
adevedo's picture

Thanks, You are totally correct about your notes, but here I am not talking about measuring the required time to add 1000000 element to a list and linked list, I am just doing a comparison (which is faster), so as all the "extra added time" are fixed for both tests, on the linked list and array list, it won't affect the results reached, as you know also these numbers get affected by the OS I am running on and the state of the OS when the tests run, too many factors affect the resulted numbers, but the comparison results still correct as all these extra factors are fixed on both sides.

Add new comment

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
Image CAPTCHA
Enter the characters shown in the image.
By submitting this form, you accept the Mollom privacy policy.