Difference between ArrayList and LinkedList
ArrayList and LinkedList both implements List interface and maintains insertion order. Both are non synchronized classes.
However, there are many differences between ArrayList and LinkedList classes that are given below.
| 1) ArrayList internally uses a dynamic array to store the elements. | LinkedList internally uses a doubly linked list to store the elements. |
| 2) Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory. | Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory. |
| 3) An ArrayList class can act as a list only because it implements List only. | LinkedList class can act as a list and queue both because it implements List and Deque interfaces. |
| 4) ArrayList is better for storing and accessing data. | LinkedList is better for manipulating data. |
Example of ArrayList and LinkedList in Java
Let's see a simple example where we are using ArrayList and LinkedList both.
Test it NowOutput:
ArrayList vs LinkedList in Java
An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. However, the limitation of the array is that the size of the array is predefined and fixed. There are multiple ways to solve this problem. In this article, the difference between two classes that are implemented to solve this problem named ArrayList and LinkedList is discussed.
ArrayList is a part of the collection framework. It is present in the java.util package and provides us dynamic arrays in Java. Though, it may be slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed. We can dynamically add and remove items. It automatically resizes itself. The following is an example to demonstrate the implementation of the ArrayList.
Example
|
// Java program to Illustrate Working of an ArrayList
// Importing required classes
import java.io.*;
import java.util.*;
// Main class
class GFG {
// Main driver method
public static void main(String[] args)
{
// Creating an ArrayList of Integer type
ArrayList<Integer> arrli
= new ArrayList<Integer>();
// Appending the new elements
// at the end of the list
// using add () method via for loops
for (int i = 1; i <= 5; i++)
arrli.add(i);
// Printing the ArrayList
System.out.println(arrli);
// Removing an element at index 3
// from the ArrayList
// using remove() method
arrli.remove(3);
// Printing the ArrayList after
// removing the element
System.out.println(arrli);
}
}
|
[1, 2, 3, 4, 5] [1, 2, 3, 5]
LinkedList is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. The following is an example to demonstrate the implementation of the LinkedList.
Note: This class implements the LinkedList Data Structure.
Example
|
// Java program to Demonstrate Working of a LinkedList
// Importing required classes
import java.util.*;
// Main class
class GFG {
// main driver method
public static void main(String args[])
{
// Creating an object of the
// class linked list
LinkedList<String> object
= new LinkedList<String>();
// Adding the elements to the object created
// using add() and addLast() method
// Custom input elements
object.add("A");
object.add("B");
object.addLast("C");
// Print the current LinkedList
System.out.println(object);
// Removing elements from the List object
// using remove() and removeFirst() method
object.remove("B");
object.removeFirst();
System.out.println("Linked list after "
+ "deletion: " + object);
}
}
|
Now after having an adequate understanding of both of them let us do discuss the differences between ArrayList and LinkedList in Java
| This class uses a dynamic array to store the elements in it. With the introduction of generics, this class supports the storage of all types of objects. | This class uses a doubly linked list to store the elements in it. Similar to the ArrayList, this class also supports the storage of all types of objects. |
| Manipulating ArrayList takes more time due to the internal implementation. Whenever we remove an element, internally, the array is traversed and the memory bits are shifted. | Manipulating LinkedList takes less time compared to ArrayList because, in a doubly-linked list, there is no concept of shifting the memory bits. The list is traversed and the reference link is changed. |
| This class implements a List interface. Therefore, this acts as a list. | This class implements both the List interface and the Deque interface. Therefore, it can act as a list and a deque. |
| This class works better when the application demands storing the data and accessing it. | This class works better when the application demands manipulation of the stored data. |
ArrayList vs LinkedList
The main difference between ArrayList and LinkedList is that ArrayList falls under the category of collection framework of dynamic arrays distinct to standard arrays whereas LinkedList exercises LinkedList Data Structure within its class with variations in every element embraced with a data and address wedge.
2) Both ArrayList and LinkedList are not synchronized, which means you can not share them between multiple threads without external synchronization. See here to know How to make ArrayList synchronized in Java.
3) ArrayList and LinkedList are ordered collection e.g. they maintain insertion order of elements i.e. the first element will be added to the first position.
4) ArrayList and LinkedList also allow duplicates and null, unlike any other List implementation e.g. Vector.
5) An iterator of both LinkedList and ArrayList are fail-fast which means they will throw ConcurrentModificationException if a collection is modified structurally once the Iterator is created. They are different than CopyOnWriteArrayList whose Iterator is fail-safe.
Difference between LinkedList and ArrayList in Java
Now let's see some differences between ArrayList and LinkedList and when to use ArrayList and LinkedList in Java.1. Underlying Data Structure
The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList. This will lead to further differences in performance.
2. LinkedList implements Deque
Another difference between ArrayList and LinkedList is that apart from the List interface, LinkedList also implements theDeque interface, which provides first in first out operations for add() and poll() and several other Deque functions.
3. Adding elements in ArrayList
Adding an element in ArrayList is O(1) operation if it doesn't trigger re-size of Array, in which case it becomes O(log(n)), On the other hand, appending an element in LinkedList is O(1) operation, as it doesn't require any navigation.
4. Removing an element from a position
In order to remove an element from a particular index e.g. by calling remove(index), ArrayList performs a copy operation which makes it close to O(n) while LinkedList needs to traverse to that point which also makes it O(n/2), as it can traverse from either direction based upon proximity.
5. Iterating over ArrayList or LinkedList
Iteration is the O(n) operation for both LinkedList and ArrayList where n is a number of an element.
6. Retrieving element from a position
The get(index) operation is O(1) in ArrayList while its O(n/2) in LinkedList, as it needs to traverse till that entry. Though, in Big O notation O(n/2) is just O(n) because we ignore constants there.
7. Memory
LinkedList uses a wrapper object, Entry, which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array.
From all the above differences between ArrayList vs LinkedList, It looks like ArrayList is the better choice than LinkedList in almost all cases, except when you do a frequent add() operation than remove(), or get().
Further Learning
Java In-Depth: Become a Complete Java Engineer
Algorithms and Data Structures - Part 1 and 2
- How to sort a Map by keys and values in Java? (tutorial)
- Top 10 Courses to learn Java for Beginners (best courses)
- How to sort an ArrayList in ascending and descending order in Java? (tutorial)
- 10 Free courses to learn Java in-depth (courses)
- The difference between HashMap and ConcurrentHashMap in Java? (answer)
- 10 courses to learn Data Structure in-depth (courses)
- The difference between HashMap and LinkedHashMap in Java? (answer)
- Difference between ArrayList and HashSet in Java? (answer)
- Top 5 Courses to learn Java Collections and Stream (courses)
- What is the difference between TreeMap and TreeSet in Java? (answer)
- The difference between HashSet and TreeSet in Java? (answer)
- 7 Best Courses to learn Data STructure and Algorithms (best courses)
- 20+ basic algorithms interview questions for programmers (questions)
- Top 5 Courses to become full-stack Java developer (courses)
- The difference between Hashtable and HashMap in Java? (answer)
- 50+ Core Java Interview Questions and Answers (questions)