Difference Between ArrayList and LinkedList in Java

Both ArrayList and LinkedList implement the List interface, but what's the difference then? The main difference between ArrayList and LinkedList is in ArrayList which is implemented using an extensible array. As more items are added to the ArrayList, its size increases dynamically. Its elements can be accessed directly using the get() and set() methods, since ArrayList is essentially an array.

LinkedList is implemented as a linked list, these add and remove performances are better than those of ArrayList, but they are bad for the get() and set() methods.

In this article, we'll look at some differences between LinkedList and ArrayList and try to understand when and where to use LinkedList instead of ArrayList.

ArrayList vs LinkedList

All the differences between LinkedList and ArrayList have a source which is the difference between an array and a LinkedList (linked list).

1) Since the Searching in ArrayList is based on the element's index so it's very fast. The get(index) has a complexity of O(1), but removal is expensive because you have to offset all the elements. In the case of LinkedList, it does not have direct access to the items, you have to go through the entire list to retrieve an item, its complexity is equal to O(n).

2) Insertions are easy in LinkedList compared to ArrayList because there is no risk when resizing and adding the item to LinkedList and its complexity is equal to O(1), while ArrayList shifts all elements with a complexity of O(n) in the worst case.

3) Deletion is like insertion, better in LikedList than in ArrayList.

4) LinkedList has more memory than ArrayList because in ArrayList each index is linked to the current object, but in the case of LinkedList, each node is linked with the element and address of the next and previous node.

When to use LinkedList and ArraList in Java

Obviously, LinkedList is not popular like ArrayList, but is still a good choice in some cases:

1) Your application does not need random access, Because this operation consists of going through the entire list in this case.

2) Your application has more insertion and removal than recovery. Both of these operations are faster in LikedList.

Use ArrayList in Java in these situations when you need unsynchronized access. ArrayList is fast and easy to use.

Example of ArrayList

ArrayList< String> al = new ArrayList< String> (); 
al.add("a"); 
al.add("c"); 
al.add("e"); 
al.add("z"); 
al.add("t"); 
al.add("m"); 

for(String s: e){
 System.out.println(e); 
}

Example of LinkedList

LinkedList< Integer> llist = new LinkedList< Integer> (); 
llist.add(8); 
llist.add(9); 
llist.add(5); 
llist.add(2); 
llist.add(6); 
 
Iterator< Integer> it = llist.iterator(); 
while(it.hasNext()){
 System.out.println(it.next()); 
}

Performance of ArrayList and LinkedList

The time complexity of both lists:

Operation	ArrayList	LinkedList
get()	O(1)	O(n)
add()	O(1)	O(1)
remove()	O(n)	O(1)

- ArrayList has a time compatibility of O(n) for both the add() and remove() operations, but O(1) for the operation at the end of the list or for retrieving an item with the get() method.

- LinkedList has a complexity of O(n) for the get() operation, but O(n) for the remove operation remove().

This code tests performance based on the time it takes to perform a number of operations:

import java.util.ArrayList; 
import java.util.LinkedList; 

public class ArrayListVsLinkedList {

 public static void main(String[] args) {
 ArrayList< Integer> alist = new ArrayList< Integer> (); 
 LinkedList< Integer> llist = new LinkedList< Integer> (); 
 
 /******************************/
 /* The add() method */
 /******************************/
 
 // ArrayList
 long tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 999999; i++) {
 alist.add(i); 
 }
 long tpsfin = System.currentTimeMillis(); 
 long duration = tpsfin - tpsdebut; 
 System.out.println("ArrayList add: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 999999; i++) {
 llist.add(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("LinkedList add: " + duration); 
 
 /******************************/
 /* The get() method */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 99999; i++) {
 alist.get(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("ArrayList get: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 99999; i++) {
 llist.get(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("LinkedList get: " + duration); 
 
 /******************************/
 /* The remove() method */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 9999; i >=0; i--) {
 alist.remove(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("ArrayList remove: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 9999; i >=0; i--) {
 llist.remove(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 duration = tpsfin - tpsdebut; 
 System.out.println("LinkedList remove: " + duration); 
 }
}

Result:

ArrayList add: 398
LinkedList add: 987
ArrayList get: 180
LinkedList get: 43276
ArrayList remove: 8721
LinkedList remove:  233

performance and difference ArrayList vs LinkedList

The major difference is in the get() and remove() methods. It is clear that LinkedList is very time-consuming when retrieving data because it goes through the entire list every time it wants to access an item. ArrayList has direct access. In contrast, ArrayList consumes a lot of time for the remove().