Why insertion deletion ArrayList slow compared to LinkedList

Why insertion deletion ArrayList slow compared to LinkedList

Answer: Below are theoretical answer:

• ArrayList is faster than LinkedList if access randomly its elements. To clarify: Random access means it access nth element from the list.

Reason: Internally ArrayList is list of array and so it has direct references to each and every elements in the list so getting nth postion of elements will be constant all time. On the other hand LinkedList needs to traverse through the list from beginning to reach nth element so It won’t be constant all time.

• Deletion process is slow in ArrayList compared to Linked list.

Reason: As we know ArrayList internally maintains list of array so deleting elements from it means its size will be reorganize and new array will be created and elements will be moved to new list. LinkedList is faster because internally its structure is linked together with the references so deletion would be only adjustment of its references.

My Test: I did test of insertion and deletion using JDK 1.7: Result is ArrayList faster than LinkedList as you could see below java program. Probably above theory was correct in early version of java programming where we had very limited memory and CPU.

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

public class ArrayListVsLinkedList {

    public static void main(String[] args) {
    
    System.out.println("Insertion test\n");
    Long startTime = System.currentTimeMillis();
    // Add 10000 elements to ArrayList
    List<String> list = new ArrayList<String>();
    for (int i = 0; i < 100000; i++) {
        list.add("Java");
        list.add("Honk");
        list.add("Test");
        list.add(null);
        list.add(null);
        list.add("Software");
        list.add("Software");
        list.add("IT");
    }
    Long endTime = System.currentTimeMillis();
    Long totalTime = endTime-startTime;
    System.out.println("Total insert Time in milli-seconds"
        + " ArrayList: "+totalTime);
    
    startTime = System.currentTimeMillis();
    LinkedList<String> linkedList = new LinkedList<String>();
    
    for (int i = 0; i < 100000; i++) {
        linkedList.add("Java");
        linkedList.add("Honk");
        linkedList.add("Test");
        linkedList.add(null);
        linkedList.add(null);
        linkedList.add("Software");
        linkedList.add("Software");
        linkedList.add("IT");
    }
    
    endTime = System.currentTimeMillis();
    totalTime = endTime-startTime;
    System.out.println("Total insert Time in milli-seconds"
        + " LinkedList: "+totalTime);

    
    System.out.println("\nDeletion test\n");
    startTime = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {
        if (i%10 ==0) {
        list.remove(i); 
        }
        
    }
    endTime = System.currentTimeMillis();
    totalTime = endTime-startTime;
    System.out.println("Total Time in milli-seconds remove "
        + "random elements ArrayList: "+totalTime);
    
    
    
    startTime = System.currentTimeMillis();
    for (int i = 0; i < linkedList.size(); i++) {
       if (i%10 ==0) {
          linkedList.remove(i); 
       }
       
    }
    endTime = System.currentTimeMillis();
    totalTime = endTime-startTime;
    System.out.println("Total Time in milli-seconds remove "
        + "random elements LinkedList: "+totalTime);
    
    
    
    }

}

Output: