Difference between ArrayList and LinkedList in Java

In this guide, you will learn difference between ArrayList and LinkedList in Java. ArrayList and LinkedList both implements List interface and their methods and results are almost identical. However there are few differences between them which make one better over another on case to case basis.

ArrayList Vs LinkedList

ArrayList	LinkedList
ArrayList class inherits the features of list as it implements the List interface.	LinkedList class has the features of list and queue both as it implements both List and Dequeue interfaces.
ArrayList data structure is similar to array as the ArrayList elements are stored in contiguous locations.	LinkedList elements are not stored in contagious locations. This is because LinkedList consists of nodes where each node has data field and reference to the next node in the list.
ArrayList default capacity is 10. If more than 10 elements are added to the ArrayList, its capacity gets doubled to accommodate new elements.	LinkedList default capacity is zero. When LinkedList is created its an empty list without any initial capacity.
ArrayList uses dynamic array to store the elements.	LinkedList uses concept of doubly linked list to store the elements.
ArrayList gives better performance for add and search operations.	LinkedList gives better performance for data deletion.
Memory consumption is low in ArrayList as it stores only the elements data in contiguous locations.	Memory consumption is high in LinkedList as it maintains element data and two pointers for neighbour nodes, hence the memory consumption is high in LinkedList.

Performance difference between ArrayList and LinkedList for various operations

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbour elements in the list. Hence removal only requires change in the pointer location in the two neighbour nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. This is because every time you add an element, Java ensures that it can fit the element so it grows the ArrayList. If the ArrayList grows faster, there will be a lot of array copying taking place. In worst-case the array must be resized and copied.

There are few similarities between these classes which are as follows:

1. Both ArrayList and LinkedList are implementation of List interface.
2. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
3. Both of these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
4. The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).

When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there are frequent addition and deletion in application then LinkedList is a best choice.

2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

Example of ArrayList and LinkedList in Java

In this example, we are demonstrating the use of ArrayList and LinkedList in Java. Here we have initialized an arraylist arrList and a linkedlist linkList. We have added few elements to both arrList and linkList. In the end, elements of both the lists are printed.

import java.util.*;
class JavaExample{
  public static void main(String args[]){

    //ArrayList
    ArrayList<String> arrList=new ArrayList<>();
    arrList.add("Apple");
    arrList.add("Orange");
    arrList.add("Banana");
    arrList.add("Mango");

    //LinkedList
    LinkedList<String> linkList=new LinkedList<>();
    linkList.add("Beans");
    linkList.add("Tomato");
    linkList.add("Lemon");
    linkList.add("Potato");

    //printing elements
    System.out.println("ArrayList elements: "+ arrList);
    System.out.println("LinkedList elements: "+ linkList);
  }
}

Output:

Recommended guides:

• ArrayList vs Vector
• ArrayList vs HashMap