Difference between ArrayList and LinkedList

In this post we will see Difference between ArrayList and LinkedList in java along with examples.

Implementation

a. ArrayList implements the List Interface , LinkedList implements the List and Deque Interface

b. ArrayList uses a dyanmic array to store elements, whereas LinkedList uses doubly linked list to store elements.

Memory Overhead

Since LinkedList uses doubly linked list, memory overhead is more in case of LinkedList to store the reference of next and previous of each element.

Performance

a. Search
Since ArrayList uses indexes to store its elements ,Searching an element using index is faster in ArrayList as compared to LinkedList
ArrayList uses O(1) time to search while LinkedList uses O(n)

b. Inserting an Element
Adding an element is faster in LinkedList as it only has to move the next and previous references of one of elements.
Adding an element is slower in ArrayList as it has to resize/reindex all the elements.

c. Deleting an Element
Removing an element is faster in LinkedList as it only has to move the next and previous references of one of elements.
Removing an element is slower in ArrayList as it has to resize/reindex all the elements.

4. Sorting
Sorting elements is faster in ArrayList due to the fact that it has to only reindex itself. In LinkedList each element has to changes its next and previous references.

When to use ArrayList

When you are going to mostly perform searching and sorting of a large size data, then go for ArrayList

When to use LinkedList

When you are going to mostly perform addition or deletion of data on a already large list, then go for LinkedList.

Example: Performance difference between ArrayList and LinkedList

package com.kscodes.sampleproject;

import java.util.ArrayList;

import java.util.LinkedList;

public class PerformanceDiffLists {

public static void main(String[] args) {

// Lets have a ArrayList and LinkedList

ArrayList<String> arrayList = new ArrayList<>(200000);

LinkedList<String> linkedList = new LinkedList<>();

// Add more than 100000 elements to each lists

for (int i = 0; i < 1000000; i++) {

arrayList.add("String" + i);

linkedList.add("String" + i);

}

// Start performance test

// 1. Search an element using get(index)

long startTime = System.currentTimeMillis();

String searchedInArrayList = arrayList.get(200000);

long endTime = System.currentTimeMillis();

System.out.println("Time taken to Search # 2000 in ArrayList :: "

+ (endTime - startTime));

startTime = System.currentTimeMillis();

String searchedInLinkedList = linkedList.get(200000);