In this tutorial, we will see the differences between ArrayList and LinkedList along with examples detailing ArrayList vs LinkedList.
Table of Contents
- ArrayList
- LinkedList
- ArrayList vs LinkedList
- Similarities
- Example of ArrayList and LinkedList
- When to use ArrayList and 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 theJava Listinterface. 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 theAbstractListclass and implements theListandDeque 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 nodesand implements a linear data structure. We call eachelement in the list a node. We name thefirstelement in the list asheadand thelastelement as atail.
ArrayList vs LinkedList
Uses dynamic array to store elements | Uses Double LinkedList to store elements |
Performance is slower | Performance is faster |
It can be used to implement only List | It can be used to implement List and Queue |
Provides random access | Does not provide random access |
Occupies less memory since it stores only object | Occupies 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 case | Add 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.
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