Understanding the Difference Between ArrayList and LinkedList in Java
Basics of SQL
12 Hrs. duration
12 Modules
2600+ Learners
Start Learning
ArrayList and LinkedList are the classes of the List Interface in Java. A list is an ordered collection known as a sequence. A list can be implemented by the user to insert the data at any position while also allowing duplicate elements. The list is a part of the Java Collections Framework. The List interface in Java has two methods to efficiently add and delete the list elements at any position.
ArrayList and LinkedList, being a member of the List interface in Java, share common methods and functionalities for storing and manipulating ordered collections of list elements. It’s important to keep in mind that their use cases, performance, and internal implementation vary. We shall examine the distinctions between Java’s LinkedList and ArrayList in this article. The two will be compared through a Java code performance test that converts an ArrayList to a LinkedList and vice versa in this blog.
Let’s now first see what an ArrayList is in Java.
What is ArrayList in Java?
ArrayList is a type of resizable array that is a part of the List interface in Java. Being a member of the List interface, it gives various methods to array size that are used internally to store the list. ArrayList in Java is the same as Vector in C++, but ArrayList is unsynchronized. When you frequently need random access to elements, an array list is a great option since it offers constant-time performance for element random access.
ArrayList is a class that creates an Object or instance of the class. Each ArrayList instance has a capacity (size) to store the elements in the list. The capacity of ArrayList grows automatically. ArrayList is an asynchronous class like LinkedList and is a part of the Java Collections Framework.
Syntax of ArrayList in Java:
//import statement
java.util.ArrayList
//creation of an ArrayList instance of type String
ArrayList<String> list1 = new ArrayList<>();
//creation of an ArrayList instance of type Integer
ArrayList<Integer> list2 = new ArrayList<>();
Explanation:
Here we are first importing the ArrayList class from the java.util and then creating two instances of the ArrayList class as list1 of type String and list2 of the type Integer. But here, we use the wrapper classes to use the String and Integer type of primitive types.
ArrayList Constructors
ArrayList(): With this constructor, an empty array list with ten entries can be created.
ArrayList(Collection c): Using this constructor, an array list with the components of the given collection can be created.
ArrayList(int initialCapacity)- This constructor allows the creation of an empty array list but with an initial capacity specified by the user in the params.
ArrayList Methods
size()- It returns the number of elements available in the array list.
clear()- It removes all the given array list elements.
add(element)- The add() method appends an element to the end of the list of arrays.
add(int index, E element)- This method uses the index value supplied in as one of its parameters to insert an element at the designated location in the array list.
contains()- If the given element is present in the array list, this method returns a boolean value indicating that it is.
get(int index)- This method returns the element from the array list to the user.
toArray()- It returns an array of elements from first to last.
set(int index, E element)- This method replaces an element at the specified position in the array list by passing the index value and the new element in the parameters of the method.
remove(int index)- This method removes an element from the array list at the index value that is supplied in the method parameters.
indexOf()- This function returns the element’s index in the list where it first appears; if there is no element, it returns -1.
isEmpty- If there are no elements in the array list, this method returns true.
Code Example: The below example shows the usage of the add() method of ArrayList in Java.
import java.util.ArrayList;
public class TestingHeroVide {
public static void main(String[] args) {
//creating an ArrayList instance
ArrayList<String> list = new ArrayList<>();
//adding data to the ArrayList
list.add("Java");
list.add("CPP");
list.add("JavaScript");
//printing the ArrayList elements
System.out.println("The ArrayList element is: " + list.get(0));
// get() is used to access the list of items
System.out.println("The ArrayList element is: " + list.get(2));
System.out.println("The ArrayList element is: " + list.get(1));
}
}
Explanation:
In this example, we have added the list elements using the add() method of ArrayList in Java. The get() method is used to fetch or access the list elements using the index. In the print statements, we are displaying all the list elements.
Output:
The ArrayList element is: Java
The ArrayList element is: JavaScript
The ArrayList element is: CPP
Code Example: The below example shows the usage of the indexOf() and isEmpty() methods of ArrayList in Java.
import java.util.ArrayList;
public class TestingHeroVide {
public static void main(String[] args) {
// creating an ArrayList instance
ArrayList<String> list = new ArrayList<>();
// adding data to the ArrayList
list.add("Java");
list.add("CPP");
list.add("Go");
list.add("JavaScript");
// Finding the index of an element in the ArrayList using the indexOf() method
System.out.println("The ArrayList element is: " + list.indexOf("Java"));
System.out.println("The ArrayList element is: " + list.indexOf("CPP"));
System.out.println("The ArrayList element is: " + list.indexOf("JavaScript"));
// check if list is empty or not
System.out.println("Is the arraylist empty? " + list.isEmpty());
}
}
Explanation:
In this example, we are finding and displaying the indexes of different list elements using the indexOf() method of ArrayList in Java. The isEmpty() method is used to check whether the list is empty or not and return the true or false. It is returning false in our case, as the list is not empty.
Output:
The ArrayList element is: 0
The ArrayList element is: 1
The ArrayList element is: 3
Is the arraylist empty? false
Code Example: The below example shows the usage of the set() and remove() methods of ArrayList in Java.
import java.util.ArrayList;
public class TestingHeroVide {
public static void main(String[] args) {
// creating an ArrayList instance
ArrayList<String> list = new ArrayList<>();
// adding data to the ArrayList
list.add("Java language");
list.add("CPP");
list.add("Go");
list.add("JavaScript");
list.add("Python");
// using the set() method to replace an element
System.out.println("The changed element is: " + list.set(1, "C++"));
System.out.println("The changed element is: " + list.set(3, "React"));
//print all elements before removal
System.out.println("Elements before removal: " + list);
// remove() method for removing a list element
list.remove(4);
//print all elements
System.out.println("Elements after removal: " + list);
}
}
Explanation:
In this example, we have replaced some list item values using the set() method of ArrayList in Java. The set() method takes index and “valueToUpdate” as parameters. The remove() method is used to remove an element from the list using the index number and finally, we are printing the before and after removal list elements.
Output:
The changed element is: CPP
The changed element is: JavaScript
Elements before removal: [Java language, C++, Go, React, Python]
Elements after removal: [Java language, C++, Go, React]
What is LinkedList in Java?
Java’s LinkedList implements the List and Deque interface as a doubly-linked list. Because it must search the list for elements, it has slower random access but enables quick insertions and removals at any point in the list. LinkedList is a class that creates an Object or instance of the class.
Each LinkedList instance has a capacity (size) to store the elements in the list. The capacity of LinkedList grows automatically. Additionally, LinkedLists are unsynchronized, meaning that external synchronisation is required whenever several threads use the same list object concurrently and at least one of the threads makes structural changes to the list. Another component of the Java Collections Framework is LinkedList.
Syntax of LinkedList in Java:
//import statement
java.util.LinkedList<strong> </strong>
//creation of a LinkedList instance of type String
LinkedList<String> list1 = new LinkedList<>();
//creation of a LinkedList instance of type Integer
LinkedList<Integer> list2 = new LinkedList<>();
Explanation:
Here we are first importing the LinkedList class from the java.util and then creating two instances of the LinkedList class as list1 (type String) and list2 (type Integer) respectively.
LinkedList Constructors
LinkedList(): An empty linked list with a 10-item initial capacity is created by the LinkedList constructor.
LinkedList(Collection c): Using this constructor, the members of the given collection are assembled into a linked list.
LinkedList Methods
size(): It returns the number of elements available in the linked list.
clear(): It removes all the given linked list elements.
addFirst(E element): Using this function, an element is added to the beginning of the linked list.
addLast(E element): This function extends the linked list’s end with an element.
contains(): If the given element is present in the linked list, this method returns a boolean value indicating that it is.
removeFirst(): This function removes the first entry from the linked list and returns it.
removeLast(): This function removes the final element from the linked list and returns it.
remove(int index): This function removes the element from the linked list by using the index of the specified element’s location.
indexOf(): This function gives the index of the initial instance of the element of the linked list.
toArray()- It returns an array of elements from first to last.
Code Example: The below example shows the usage of the addFirst() and addLast() methods of LinkedList in Java.
import java.util.LinkedList;
public class TestingHeroVide {
public static void main(String[] args) {
// creating a LinkedList instance
LinkedList<String> list = new LinkedList<>();
// adding data to the LinkedList
list.addFirst("Java");
list.addFirst("CPP");
list.addLast("Go");
list.addLast("Python");
//print all elements
System.out.println("LinkedList element at first and last: " + list);
}
}
Explanation:
In this example, we have created an instance of LinkedList to store list elements. The elements are added to the beginning and end of the list using the addFirst() and addLast() methods of the LinkedList class.
Output:
LinkedList element at first and last: [CPP, Java, Go, Python]
Code Example: The below example shows the usage of the indexOf() and contains() methods of LinkedList in Java.
import java.util.LinkedList;
public class TestingHeroVide {
public static void main(String[] args) {
// creating a LinkedList instance
LinkedList<String> list = new LinkedList<>();
// adding data to the LinkedList
list.addFirst("Java");
list.addFirst("CPP");
list.addLast("Go");
list.addLast("Python");
//print all elements
System.out.println("The index of Java is: " + list.indexOf(list.getFirst()));
System.out.println("The index of Python is: " + list.indexOf(list.getLast()));
//contains method usage
System.out.println("Does the list contain Java? " + list.contains("Go"));
}
}
Explanation:
In this example, we constructed a LinkedList object and used the addFirst() and addLast() methods to add some members. The indexOf() method is used to determine the index of the list’s first and last elements. It is also possible to determine if a given element exists in the list by using the contains() method.
Output:
The index of Java is: 0
The index of Python is: 3
Does the list contain Java? true
Performance Test between ArrayList and LinkedList in Java
To have a better understanding of the performance of ArrayList and LinkedList and see which comes out faster, we have to do a performance test. We will use the system nano timings to differentiate between both based on 3 factors. Let’s see an example now:
Code Example:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
public class TestingHeroVide {
private static final int testIterationLimit = 10000;
private static final Random rng = new Random();
public static void main(String[] args) {
addElToList();
accessFromList();
removeFromList();
}
private static void addElToList() {
// creating the lists instances
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// adding elements to the array list
long arrStart = System.nanoTime();
for (int i = 0; i < testIterationLimit; i++) {
arrayList.add(rng.nextInt());
}
// adding elements to the linked list
long llStart = System.nanoTime();
for (int i = 0; i < testIterationLimit; i++) {
linkedList.add(rng.nextInt());
}
// getting the time after adding elements to the list
long arrEnd = System.nanoTime();
System.out.println("ArrayList add timing is: " + (arrEnd - arrStart) + " ns");
// getting the time after adding elements to the list
long llEnd = System.nanoTime();
System.out.println("LinkedList add timing is: " + (llEnd - llStart) + " ns");
}
private static void accessFromList() {
// Creating the lists instances
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
//Adding elements to both lists
for (int i = 0; i < testIterationLimit; i++) {
int value = rng.nextInt();
arrayList.add(value);
linkedList.add(value);
}
// getting the time after adding elements to the array list
long arrStart = System.nanoTime();
for (int i = 0; i < testIterationLimit; i++) {
arrayList.get(i);
}
long arrEnd = System.nanoTime();
System.out.println("ArrayList access timing is: " + (arrEnd - arrStart) + " ns");
// getting the time after adding elements to the linked list
long llStart = System.nanoTime();
for (int i = 0; i < testIterationLimit; i++) {
linkedList.get(i);
}
long llEnd = System.nanoTime();
System.out.println("LinkedList access timing is: " + (llEnd - llStart) + " ns");
}
private static void removeFromList() {
// creating the list instances
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
//Adding elements to both lists
for (int i = 0; i < testIterationLimit; i++) {
int value = rng.nextInt();
arrayList.add(value);
linkedList.add(value);
}
// getting the time after adding elements to the array list
long arrStart = System.nanoTime();
for (int i = 0; i < testIterationLimit / 2; i++) {
arrayList.remove(arrayList.size() / 2);
}
long arrEnd = System.nanoTime();
System.out.println("ArrayList remove timing is: " + (arrEnd - arrStart) + " ns");
// getting the time after adding elements to the linked list
long llStart = System.nanoTime();
for (int i = 0; i < testIterationLimit / 2; i++) {
linkedList.remove(linkedList.size() / 2);
}
long llEnd = System.nanoTime();
System.out.println("LinkedList remove timing is: " + (llEnd - llStart) + " ns");
}
}
Output:
ArrayList add timing is: 15754300 ns
LinkedList add timing is: 52523400 ns
ArrayList access timing is: 2217300 ns
LinkedList access timing is: 174634999 ns
ArrayList remove timing is: 34592300 ns
LinkedList remove timing is: 95646500 ns
Explanation:
So in this example, we have performed a performance test for both ArrayList and LinkedList. The code includes the performance test of adding the elements to the lists, accessing the elements from the lists, and also removing an element from the lists.
We have created the addElToList() function that measures the time taken to add 10000 elements to ArrayList and LinkedList and uses the system.nanoTime() to get the precise timing in nanoseconds. Running this, we found that ArrayList performs faster than LinkedList to add elements.
The accessFromList() function is also created to measure the time taken to access an element by its index from the ArrayList and LinkedList and it uses the system.nanoTime() to get the precise timing in nanoseconds. Running this, we found that LinkedList performs faster as compared to ArrayList.
The removeFromList() function is lastly created to measure the time taken to remove an element from the middle of the ArrayList and LinkedList and it also uses the system.nanoTime() to get the precise timing in nanoseconds. Running this, we found that ArrayList performs faster than LinkedList to add elements. But this can change the timing if the deletion operation uses different positions.
Conversion From ArrayList to LinkedList
You can also convert an ArrayList to a LinkedList. Let’s see how:
import java.util.ArrayList;
import java.util.LinkedList;;
public class TestingHeroVide {
public static void main(String[] args) {
//creating an ArrayList instance
ArrayList<Integer> list = new ArrayList<>();
//adding data to the ArrayList
list.add(111);
list.add(112);
list.add(113);
list.add(114);
list.add(115);
//converting the ArrayList to LinkedList
LinkedList<Integer> llNumbers = new LinkedList<>(list);
//printing the linkedlist elements
System.out.println(“The LinkedList converted from ArrayList is: ” + llNumbers.get(0));
System.out.println(“The LinkedList converted from ArrayList is: ” + llNumbers.get(2));
System.out.println(“The LinkedList converted from ArrayList is: ” + llNumbers.get(4));
}
}
Explanation:
In this example, we convert an ArrayList class to a LinkedList class by passing the list object to the constructor. The resulting print statement displays the converted list of items with the relevant content in it.
Output:
The LinkedList converted from ArrayList is: 111
The LinkedList converted from ArrayList is: 113
The LinkedList converted from ArrayList is: 115
Conversion From LinkedList to ArrayList
You can also convert a LinkedList to an ArrayList. Let’s see how:
import java.util.ArrayList;
import java.util.LinkedList;;
public class TestingHeroVide {
public static void main(String[] args) {
//creating a LinkedList instance
LinkedList<String> list = new LinkedList<>();
//adding data to the ArrayList
list.add(“Hello World from Java”);
list.add(“Hello World from CPP”);
list.add(“Hello World from JavaScript”);
list.add(“Hello World from Python”);
list.add(“Hello World from Go”);
//converting the LinkedList ArrayList
ArrayList<String> listNames = new ArrayList<>(list);
//printing the ArrayList elements
System.out.println(“The ArrayList converted from LinkedList is: ” + listNames.get(0));
System.out.println(“The ArrayList converted from LinkedList is: ” + listNames.get(2));
System.out.println(“The ArrayList converted from LinkedList is: ” + listNames.get(4));
}
}
Explanation:
In this example, we convert a LinkedList class to an ArrayList class by passing the list object to the constructor. The resulting print statement displays the converted list of items with the relevant content in it.
Output:
The ArrayList converted from LinkedList is: Hello World from Java
The ArrayList converted from LinkedList is: Hello World from JavaScript
The ArrayList converted from LinkedList is: Hello World from Go
Difference Between ArrayList and LinkedList in Java
Some of the key differences between the ArrayList and LinkedList classes in Java are given below:
Parameters
ArrayList
LinkedList
Data Structure
ArrayList uses a dynamic array.
A doubly linked list is used in the LinkedList class.
Performance
Relatively faster in some scenarios, but depends on the performance test.
It also depends on the performance test of different operations like add, remove, access, etc.
Synchronisation
It is not thread-safe.
It is also not thread-safe.
Null values
Null values are allowed.
Null values are also allowed.
Cache
Better cache locality in ArrayList.
Worse cache locality in LinkedList.
Memory Overhead
There is less memory overhead.
There is more memory overhead.
Pointers
No pointers
There are pointers in LinkedList.
Memory usage
ArrayList requires less memory as it uses the contiguous block of memory.
It requires more memory as it uses the storage for the pointers.
Add Time Complexity
O(N) worst case
O(1) first position
Access Time Complexity
O(1)
O(N)
Remove Time Complexity
O(N)
O(1) first removal
Syntax
ArrayList<String> list = new ArrayList<>();
LinkedList<String> list = new LinkedList<>();
Conclusion
In this blog, we saw the differences between ArrayList and LinkedList in Java. We have learned the implementation of ArrayList and LinkedList with various examples using their constructors and methods. We also did a performance test between ArrayList and LinkedList to see which is more efficient.
Upon completing this test, we found that ArrayList performed well in random access and sequential processes, whereas LinkedList also shows itself well in scenarios where there are frequent insertions or deletions of elements in the list. Understanding the implementation and performance characteristics of ArrayList and LinkedList can help you make a great decision on choosing the right class as per different scenarios. It will also help you optimise the code for better performance.
Deploying Applications Over the Cloud Using Jenkins
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
