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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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); endTime = System.currentTimeMillis(); System.out.println("Time taken to Search # 2000 in LinkedList :: " + (endTime - startTime)); // 2. Add an element using add() startTime = System.currentTimeMillis(); arrayList.add("First Element"); endTime = System.currentTimeMillis(); System.out.println("Time taken to Add element in ArrayList :: " + (endTime - startTime)); startTime = System.currentTimeMillis(); linkedList.add("First Element"); endTime = System.currentTimeMillis(); System.out.println("Time taken to Add element in LinkedList :: " + (endTime - startTime)); // 3. Remove an element using add() startTime = System.currentTimeMillis(); arrayList.remove("String20000"); endTime = System.currentTimeMillis(); System.out.println("Time taken to Remove element from ArrayList :: " + (endTime - startTime)); startTime = System.currentTimeMillis(); linkedList.remove("String20000"); endTime = System.currentTimeMillis(); System.out.println("Time taken to Remove element from LinkedList :: " + (endTime - startTime)); } } |
Output
1 2 3 4 5 6 | Time taken to Search # 2000 in ArrayList :: 0 Time taken to Search # 2000 in LinkedList :: 9 Time taken to Add element in ArrayList :: 0 Time taken to Add element in LinkedList :: 0 Time taken to Remove element from ArrayList :: 0 Time taken to Remove element from LinkedList :: 15 |