Last Updated on March 9, 2022 by Ria Pathak
Introduction
One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.
A collection of items stored in contiguous memory spaces is referred to as an array. The array’s limitation, on the other hand, is that its size is predetermined and fixed. This problem can be solved in a variety of ways. The differences between two classes that are used to tackle this problem, ArrayList and LinkedList, are explored in this article.
ArrayList
- The collection framework includes ArrayList.
- It’s part of the java.util package and allows us to create dynamic arrays in Java.
- Though it may be slower than normal arrays, it might be useful in programs that require a lot of array manipulation.
- We can add and remove objects in real-time. It adjusts its size on its own.
The implementation of the ArrayList is demonstrated in the following example.
Code Implementation
import java.io.*;
import java.util.*;
public class PrepBytes {
public static void main(String[] args)
{
ArrayList arrli
= new ArrayList();
for (int i = 1; i <= 5; i+=2)
arrli.add(i);
System.out.println(arrli);
arrli.remove(1);
System.out.println(arrli);
}
}
Output
[1, 3, 5]
[1, 5]
LinkedList
- A LinkedList’s items are not stored at a contiguous memory location, and each element is a distinct object with a data part and an address part.
- Connecting the elements is done through pointers and addresses.
- A node is a term used to describe any element.
- Because of the dynamic nature and simplicity of insertions and deletions in LinkedList, they are preferred over arrays.
The implementation of the LinkedList is shown in the example below.
Code Implementation
import java.util.*;
public class PrepBytes{
public static void main(String args[])
{
LinkedList object
= new LinkedList();
object.add("Coding");
object.add("is");
object.addLast("Fun");
System.out.println(object);
object.remove("is");
System.out.println("Linked list after "
+ "deletion: " + object);
}
}
Output
[Coding, is, Fun]
Linked list after deletion: [Coding, Fun]
Now that you’ve got a good idea of both, let’s look at the distinctions between ArrayList and LinkedList in Java.
| ArrayList | LinkedList |
|---|---|
| The elements of this class are stored in a dynamic array. This class now supports the storage of all types of objects thanks to the addition of generics. | The elements of this class are stored in a doubly-linked list. This class, like the ArrayList, allows for the storage of any type of object. |
| Because of the internal implementation, manipulating an ArrayList takes longer. Internally, the array is scanned, and the memory bits are shifted whenever we remove an element. | Because there is no concept of changing memory bits in a doubly-linked list, manipulating it takes less time than manipulating an ArrayList. The reference link is changed after traversing the list. |
| The List interface is implemented by this class. As a result, this serves as a list. | The List and Deque interfaces are both implemented by this class. As a result, it can be used as both a list and a deque. |
| This class is more useful when the application requires data storage and access. | This class is more useful when the application requires data manipulation. |
Time Complexity
| Operation | ArrayList Time Complexity | LinkedList Time Complexity |
|---|---|---|
| Insert at given index | O(N) | O(N) |
| Insert at last index | O(1) ( If copy array operation is considered then O(N) ) | O(1) |
| Get by index | O(1) | O(N) |
| Search by value | O(N) | O(N) |
| Remove by value | O(N) | O(N) |
| Remove by index | O(N) | O(N) |
As a result, we’ve attempted to illustrate the key distinctions between an ArrayList and a LinkedList in this post. When it comes to coding interviews, the Java Collection Framework is crucial. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.