ArrayList vs LinkedList


JavaViews 2102

In this tutorial, we will see the differences between ArrayList and LinkedList along with examples detailing ArrayList vs LinkedList.

ArrayList

ArrayList in Java is the most commonly used data structure for creating a dynamic size array. It extends the Abstract class and implements the Java List interface. The main difference between array and ArrayList is that the array is static(we cannot add or remove elements) while ArrayList is dynamic(we can add, remove or modify elements)

LinkedList

Java LinkedList is a doubly-linked list that can store any type of data. It extends the AbstractList class and implements the List and Deque interfaces. It is a doubly-linked list since it contains a link to the previous node as well as the next successive node. LinkedList contains a collection of nodes and implements a linear data structure. We call each element in the list a node. We name the first element in the list as head and the last element as a tail.

ArrayList vs LinkedList

ArrayListLinkedList
Uses dynamic array to store elementsUses Double LinkedList to store elements
Performance is slowerPerformance is faster
It can be used to implement only ListIt can be used to implement List and Queue
Provides random accessDoes not provide random access
Occupies less memory since it stores only objectOccupies more memory since it stores both object and reference of the object
get(int index) gives performance of O(1)get(int index) gives performance of O(n)
Removal operation performance in worst case is O(n) and best case is O(1)Removal operation gives performance of O(1)
Add method gives performance of O(n) in worst caseAdd method gives performance of O(1)

Similarities

Now, that we know the differences, let us see the similarities

  • Both the classes implement the List interface
  • Maintains insertion order which means it displays the elements in the same order it inserts.
  • Both classes are non-synchronized.
  • The iterator and listiterator are fail-fast which means it throws ConcurrentModificationException if the list is modified after it creates the iterator.

Example of ArrayList and LinkedList

In this example, we create an ArrayList of String type to store city names and create a LinkedList of String type to store state names.

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

public class ListDiffDemo {

  public static void main(String[] args) {
    ArrayList<String> cities = new ArrayList<String>();
    cities.add("Chennai");
    cities.add("Bangalore");
    cities.add("Mumbai");
    cities.add("Kolkata");
    cities.add(3, "Delhi");
    
    System.out.println("Elements in ArrayList: " + cities);
    
    
    List<String> states = new LinkedList<String>();
    states.add("Tamil Nadu");
    states.add("Karnataka");
    states.add("Maharashtra");
    states.add("West Bengal");
    states.add(3, "Delhi");

    System.out.println("Elements in LinkedList" + states);
    
  }

}

Elements in ArrayList: [Chennai, Bangalore, Mumbai, Delhi, Kolkata]
Elements in LinkedList[Tamil Nadu, Karnataka, Maharashtra, Delhi, West Bengal]

When to use ArrayList and LinkedList

  • It is always a good option to use LinkedList for frequent insertion and deletion operation since the performance is faster which is O(1) when comparing with ArrayList which is O(n).
  • ArrayList is the best operation for searching elements since performance is O(1) while comparing with LinkedList that has O(n). This is because it uses the concept of an array for searching elements based on the index while LinkedList traverses through every element.

 

References

Translate »