Understanding the differences between ArrayList and LinkedList

1. Introduction

In this tutorial, We will learn a mostly asked interview question for 2-6 years of experiences java developers. What are the differences between ArrayList and LinkedList? When to use which one ArrayList or LinkedList? What are the advantages of each one?

ArrayList and LinkedList are part of java.util package and introduced in java 1.2 version. They have made internally lots of changes during the new JDK version evolution.

Let us explore some of the aspects of the ArrayList and LinkedList.

Note: ArrayList works on the index-based and Linked list works on Node-based internally but LinkedList can be accessed by index as well.

2. Internal Storing Time

Let us understand how much time takes by each one to add first 1000 integer values.

ArrayList is implemented based on the Array's concept and implemented in such manner that grows dynamically. It always keeps the additional memory and always resizes the array copying all elements into array with the new size calling Arrays.copyOf(elementData, newCapacity); ArrayList default size is 10.

elementData that stores the actual values added to ArrayList.
newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 this means it produces the result as same as oldCapacity/2 but '>>' is most efficient because it works directly on bits.

LinkedList is implemented based on the DoubleLinkedList internally. DoubleLinkedList nodes always have its previous and next node pointer because this does not work on the index based where as ArrayList completely works on Arrays index.

LinkedList does not preserve any default size. Based on the values added it just internally add a new node at the end of the double linked list.


Example:

Adding 1000 values to ArrayList and LinkedList. Both will add the first 1000 interger values but time taken to store them is the matter for larger dataset. Let us see the time taken by both for the same task.

package com.java.w3schools.blog.arraylist;

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

public class DiffArrayListVsLinkedList {

 public static void main(String[] args) {

  List<Integer> arraylist = new ArrayList<Integer>();

  long start = timeNow();

  for (int i = 0; i < 1000; i++) {
   arraylist.add(i);
  }

  long end = timeNow();

  System.out.println("Time(ms) taken by ArrayList for adding : " + timeDiff(start, end));

  List<Integer> linkedlist = new LinkedList<Integer>();

  start = timeNow();

  for (int i = 0; i < 1000; i++) {
   linkedlist.add(i);
  }

  end = timeNow();
  System.out.println("Time(ms) taken by LinkedList for adding : " + timeDiff(start, end));
  System.out.println("arraylist size : " + arraylist.size());
  System.out.println("linkedlist size : " + linkedlist.size());

 }

 private static long timeDiff(long start, long end) {

  return end - start;
 }

 private static long timeNow() {
  return Calendar.getInstance().getTimeInMillis();
 }
}

Output:

Time(ms) taken by ArrayList for adding : 11
Time(ms) taken by LinkedList for adding : 1
arraylist size : 1000
linkedlist size : 1000

LinkedList is faster beacuse it does not resize its size internally whereas ArrayList does resize many times as it ensure always it will have additonal storge by 50%.

Linkedlist Inserts : O(1)
ArrayList Inserts : O(n)

Winner in "Internal Storageing Time" : LinkedList

3. Add and Remove Values in middle Performance

If there is scenario where frequenntly values are getting removed existing values and added with new values. Let us see tjhe exampel program How both classes works internally and how much time it takes?

Adding and removing the values at any given position works differently in ArrayList and LinkedList. In ArrayList if a value is removed at any index then all elements from next index to last index will be shifted to left side which needs aditional resources and time. The same logic has been applied when adding a new value at any index. But in the Linkedlist it just removes node and delinkes from previous, next nodes. After that, points previous node and next node to the new node. This works much faster than ArrayList.

arraylist.add(2, 25000);
linkedlist.add(2, 25000);

Example:

Observe the below program that we are trying to capture the time taken to add new value at index 2 in LinkedList and ArrayList.

List<Integer> arraylist = new ArrayList<Integer>();

// adding values
for (int i = 0; i < 1000; i++) {
 arraylist.add(i);
}

long start = timeNow();
arraylist.add(2, 25000);
long end = timeNow();

System.out.println("Time(ms) taken by ArrayList for adding : " + timeDiff(start, end));

List<Integer> linkedlist = new LinkedList<Integer>();

// adding values
for (int i = 0; i < 1000; i++) {
 linkedlist.add(i);
}

start = timeNow();
linkedlist.add(2, 25000);
end = timeNow();

System.out.println("Time(ms) taken by LinkedList for adding : " + timeDiff(start, end));

Output:

Time taken by ArrayList for adding : 8
Time taken by LinkedList for adding : 0

ArrayList has taken 8 milli seoconds but LinkedList takes no time at all for insertion in middle or at any index.

LinkedList insersion/Deletion : O(1)
ArrayList insersion/Deletion : O(n)

Winner in "Add and Remove Values Performance" : LinkedList

4. Search or Get Value By Index

LinkedList and ArrayList classes have get(int index) method by index. But, ArrayList internally implemented by array so now it can directly pick from array index but where as in LinkedList it maintains internally Node for storage. Each node stores the its previous and next node references. When get() method by index is invokded then it internally traverse through the nodes and get the value from the specified index.

The below code LinkedList internal code.

First condifiton is index < mid index. If yes, run the for loop from index o to index and get next element from first node till for loop ends. If not, else block will be excuted. In the else block, loop traverse from last node to till the index. From each node, it gets the previous node. LinkedList works well if the index is nearer to the first or last index.

 Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

ArrayList time complexicity: O(1)
LinkedList time complexicity: O(n)

Winner: ArrayList

Error:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1000, Size: 1000
 at java.util.ArrayList.rangeCheck(ArrayList.java:657)
 at java.util.ArrayList.get(ArrayList.java:433)
 at com.java.w3schools.blog.arraylist.DiffArrayListVsLinkedListSearch.main(DiffArrayListVsLinkedListSearch.java:20)

Here problem is that list size is 1000 and we are getting the value like get(1000) which is hihger that its index limit. Because index starts from 0 and ends at size - 1. To solve this exception, we need to pass get(999).

5. Memory Utilization

ArrayList creates a new Array internally when it's memory is full. It uses Arrays.copyOf() mehtod to create new array and copy all old values into it. This the only one place where it uses the memory heavily and the old array is eligible for garbage collection beacuse it is not having reference to any live thread.

Where as in LinkedList is implemented basedon the nodes concept where each node stores its previous and next nodes. These nodes are called as neighber nodes and these neighber nodes are very helpful for travervesal through its values. get() method uses the previous and next nodes for traversal. Let us come to the memory aspect, Here it needs additional memory for storing the next and previous nodes of each node. But, when compared to ArrayList, it needs more memory and not garbage collected.

Winner: ArrayList

6. Similarities between ArrayList and LinkedList

There are few similiarites in these two collection API classes.

6.1 List interface

Both classes implementes List interface.

public class ArrayList<E>
  extends AbstractList<E> 
  implements List<E>, RandomAccess, Cloneable, java.io.Serializable


public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
 

6.2 Preserves Insersion Order

Both are good interms of keeping the insertion order in place. That means while looping the ArrayList and LinkedList values result would be as same as how they are inserted into these lists.

In this program, We have used enhanced for loop.

package com.java.w3schools.blog.arraylist;

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

public class DiffArrayListVsLinkedListOrder {

 public static void main(String[] args) throws InterruptedException {

  List<String> coronaUSAStatesLinkedList = new LinkedList<String>();

  coronaUSAStatesLinkedList.add("New York");
  coronaUSAStatesLinkedList.add("California");
  coronaUSAStatesLinkedList.add("New Jersy");
  coronaUSAStatesLinkedList.add("Michigan");
  coronaUSAStatesLinkedList.add("Washington");

  System.out.println("LinkedList USA Corona states are : ");
  for (String coronaState : coronaUSAStatesLinkedList) {
   System.out.println(coronaState);
  }

  List<String> coronaUSAStatesArrayList = new ArrayList<String>();

  coronaUSAStatesArrayList.add("Massachusetts");
  coronaUSAStatesArrayList.add("Florida");
  coronaUSAStatesArrayList.add("Illinois");
  coronaUSAStatesArrayList.add("Louisiana");
  coronaUSAStatesArrayList.add("Pennsylvania");

  System.out.println(" \nArrayList USA Corona states are : ");
  for (String coronaState : coronaUSAStatesArrayList) {
   System.out.println(coronaState);
  }

 }

 private static long timeDiff(long start, long end) {

  return end - start;
 }

 private static long timeNow() {
  return Calendar.getInstance().getTimeInMillis();
 }
}

Output:

LinkedList USA Corona states are : 
New York
California
New Jersy
Michigan
Washington
 
ArrayList USA Corona states are : 
Massachusetts
Florida
Illinois
Louisiana
Pennsylvania

6.3 Non Synchronized

By default, ArrayList and LinkedList are non synchronized. Both does not work in concurrent applications and these two are not thread safe. Collections class is provided with a method to make List classes synchronized and method is synchronizedList() which is static method accessed as Collections.synchronizedList(). This method returns new synchronized list.

6.4 Fail-Fast

Both classes are said as fail fast that means while iterating using Iterator if the original list is modified that will through runtime exception "ConcurrentModificationException".

Iterator it = coronaUSAStatesArrayList.iterator();
  
while(it.hasNext()) {
 System.out.println(it.next());
 coronaUSAStatesArrayList.add("Georgia");
}

Output:

Massachusetts
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
 at java.util.ArrayList$Itr.next(ArrayList.java:859)
 at com.java.w3schools.blog.arraylist.DiffArrayListVsLinkedListOrder.main(DiffArrayListVsLinkedListOrder.java:42)

7. When to use Which one ArrayList or LinkedList

7.1 LinkedList Preference

Linked is preferred when you have more inserts and deletes because it gives good performancne results. LinkedList time complexicity O(1) when compared to ArrayList O(n).

7.2 ArrayList Preference

ArrayList is preferred if there are very less inserts or deletes and more get or search operations. ArrayList search time complexocity is O(1) and LinkedList is O(n).

8. Conclusion

In this article, we have seen major differenes between ArrayList and LinkedList classes. What are the similarities and when to use which one.

GitHub