Difference Between ArrayList and LinkedList

The list is an abstract data type available in functional programming languages that stores ordered values. It is analogous to arrays in object-oriented programming languages. Lists allow us to store, manipulate, and retrieve data easily.

Programming languages that support list data types have their ways of creating lists. We can create a list by inserting data items sequentially within a pair of delimiters, like braces ‘{ }’, brackets ‘[ ]’, parentheses ‘( )’, or angular brackets ‘< >’, where items are separated by spaces, commas, or semicolons.

The primary drawback of the traditional array is its fixed size, and we need to define the size of an array before using it. ArrayList and LinkedList both these data structures overcome the problem of an array’s fixed size. They both implement the List interface and allow us to insert objects of any type.

This article will highlight the differences between ArrayList and LinkedList. But before proceeding, we shall make you familiar with ArrayList and LinkedList. So, let us get started.

What is ArrayList?

An ArrayList is a growable array that can store data of different types, and it is a dynamic array whose size increases as we add elements to it. Despite being slower than the traditional array, ArrayList is useful when an application requires performing a lot of manipulations in the array.

Let us see how ArrayList overcomes the problem of an array with an example. Consider an array named ‘studNames’, which stores the name of students, as given below:

String[] studNames = new String[5]
studNames[0] = "John";
studNames[1] = "Oliver";
studNames[2] = "Brown";
studNames[3] = "Sam";
studNames[4] = "George";

In the above example, the array size is fixed. It does not allow inserting more than 5 elements. But this is not the case with ArrayList, as it is a dynamic array. There is no need to define the size initially while creating ArrayList. Let us create an ArrayList and store the same data.

ArrayList<String> studNames = new ArrayList<String>();
studNames.add("John");
studNames.add("Oliver");
studNames.add("Brown");
studNames.add("Sam");
studNames.add("George");

ArrayList lets us add as many elements as we wish. Also, it becomes easier to retrieve and manipulate any element from the ArrayList using its index. It is essential to remember that the first index is always zero. When we print the above ArrayList, it gives the output as:

[John, Oliver, Brown, Sam, George]

Features of ArrayList

• ArrayList can store duplicate values, i.e., we can insert two elements of the same name in ArrayList.
• It can store a null value.
• Sorting an ArrayList in ascending or descending order is simple using the ‘sort’ method present in the Java.util.Collections class.
• ArrayList allows random access, as it works on an index basis.
• It is not synchronized.
• ArrayList in Java can be thought of as Vector in C++.

Hierarchy of ArrayList

The below diagram represents the hierarchy of ArrayList:

This diagram depicts that the ArrayList class extends the AbstractList class, which implements the List interface. Further, the List interface extends the Collection and Iterable interfaces in the given order.

What is LinkedList?

A LinkedList is a linear data structure, where every element is known as a node consisting of the actual data and pointers to the previous and the next nodes. Although Java supports a Singly Linked List, it implements LinkedList as a Doubly-Linked List (DLL) internally. Below is the diagram of a Doubly-Linked List.

Here, the demarcation on the left of each node represents a pointer to the previous node, and on the right represents a pointer to the next node. The left of Item 1 is null, as there is no previous node and the right points to Item 2. Item 2 contains a pointer to its previous node, Item 1, and a pointer to its next node, Item 3. Finally, Item 3 has a pointer to its previous node, Item 2, and the next pointer is null, as it is the last node in a list.

Features of LinkedList

• In LinkedList, we use the get(<index>) method to retrieve elements. Also, we can add and remove as many elements as we need, like ArrayList.
• LinkedList also supports null values and duplicate values.
• It is not synchronized.
• We can use a LinkedList in Java as a stack, queue, and list.

Hierarchy of LinkedList

The below diagram represents the hierarchy of LinkedList:

As shown in the diagram, LinkedList extends the AbstractSequentialList, which implements the List interface, and implements the Deque interface, which extends the Queue interface. Furthermore, the List and Queue interfaces extend the Collection interface, which further extends the Iterable interface.

ArrayList vs LinkedList: A Head-to-Head Comparison

Here are some key differences between ArrayList and LinkedList.

ArrayList or LinkedList — Which One to Use?

When an application or project requires a lot of manipulations, like adding or deleting elements, LinkedList is an ideal data structure over ArrayList. ArrayList would be a great choice when an application or project requires searching and retrieving elements because the time complexity of search operation in ArrayList is O(1). In contrast, it is O(n/2) in LinkedList.

ArrayList and LinkedList Examples in Java

ArrayList

import java.io.*;
import java.util.*;
class students
{
public static void main(String[] args)
{
ArrayList<String> studNames = new ArrayList<String>();
studNames.add("John");
studNames.add("Oliver");
studNames.add("Brown");
studNames.add("Sam");
studNames.add("George");
System.out.println("Initial ArrayList:" +studNames);
studNames.remove(2);
System.out.println("After removing an element from ArrayList:" +studNames);
studNames.add(1, "Harry");
System.out.println("ArrayList after adding an element:" +studNames);
studNames.set(2, "Henry"):
System.out.println("Final ArrayList:" +studNames);
}
}

Output

Initial ArrayList: [John, Oliver, Brown, Sam, George]
After removing an element from ArrayList: [John, Oliver, Sam, George]
ArrayList after adding an element: [John, Harry, Oliver, Sam, George]

Final ArrayList: [John, Harry, Henry, Sam, George]

LinkedList

import java.util.*;
class employees
{
public static void main(String[] args)
{
LinkedList<String> empNames = new LinkedList<String>();
empNames.add("Mary");
empNames.add("Liam");
empNames.add("Charlotte");
empNames.add("Elijah");
empNames.add("Ava");
empNames("Emma");
System.out.println("Initial LinkedList:" +empNames);
empNames.remove(3);
System.out.println("After removing an element from LinkedList:" +empNames);
empNames.add(3, "Anna");
System.out.println("LinkedList after adding an element:" +empNames);
empNames.removeFirst();
empNames.removeLast();
System.out.println(“LinkedList after removing the first and last elements:" +empNames);

empNames.set(3, “Evelyn”);

System.out.println(“Final LinkedList:” +empNames);
}
}

Output

Initial LinkedList: [Mary, Liam, Charlotte, Elijah, Ava, Emma]
After removing an element from LinkedList: [Mary, Liam, Charlotte, Ava, Emma]

LinkedList after adding an element: [Mary, Liam, Charlotte, Anna, Ava, Emma]

LinkedList after removing the first and last elements: [Liam, Charlotte, Anna, Ava]

Final LinkedList: [Liam, Charlotte, Anna, Evelyn]

Conclusion

Both ArrayList and LinkedList overcome the problem of the traditional array, as they are dynamic. As LinkedList implements the Deque interface, it offers more features than ArrayList. ArrayList is faster if you only need to store and retrieve data, whereas LinkedList is faster if there are a lot of manipulations. We hope that this article has helped you to understand the differences between ArrayList and LinkedList. Choosing either ArrayList or LinkedList entirely depends on an application’s requirements.

People are also reading:

• Return a List, not a LinkedList
• Merge Sort for Linked Lists
• Reverse a Linked List
• Clone a Linked list with the Random Pointer
• Find and remove loops in a Linked List
• Java int array
• Populate a Static List in Java
• List in Java
• Python vs Java
• Python List Methods