Difference Between ArrayList vs LinkedList
ArrayList vs LinkedList both are a part of the collection framework where both are present in java.util package. ArrayList is used to store the homogeneous elements at contiguous memory locations according to the indexes. These indexes can be used to directly access the elements. LinkedList type of collection is used to store any type of elements at any of the available memory locations using nodes. These nodes store the pointer that points to the next node and previous node(in case of circular list) in the list and helps in efficient insertion and deletion from the list.
Head to Head Comparison between ArrayList vs LinkedList (Infographics)
Below are the top 12 comparisons between ArrayList vs LinkedList:
Key differences between ArrayList vs LinkedList
Let us discuss some key differences between ArrayList vs LinkedList in the following points:
1. Type of Elements: ArrayList is used to store homogeneous elements but LinkedList can be used to store heterogeneous elements also.
2. Insertion: Insertion operation comprises of the addition of an element in the existing list. In the case of ArrayList, when one element needs to be added at the particular index of the list, it is comprised of 2 methods- expansion of the array size with a new size and copying the elements to the newer array at an updated location. The time complexity of this is O(n).
In the case of LinkedList, insertion operation is more efficient as memory is variable and allocated dynamically and no shifting of the element is required, instead only pointers need to be updated. Thus time complexity is O(1) for insertion operation.
4.5 (5,408 ratings)
View Course
Thus in case insertion or deletion operation needs to be performed often thus one must choose LinkedList.
3. Data Access: In case one needs to access an element at a location, ArrayList is more efficient in this case since it uses indexes to store the elements and can be easily accessed using the particular index. Whereas in case of LinkedList needs to traverse the complete list to access the element.
Example: Accessing the fourth element in ArrayList A we just need to mention A[3] as the index in case of an array starts with 0.
4. Deletion: In case of Deletion also, ArrayList takes more time since it needs to copy the elements to the new array at updated locations thus have time complexity of O(n). In case we use LinkedList, deletion can be performed with O(1) of time complexity as the memory of the node needs to deallocated and pointers of the previous and next node needs to update only. Thus it is more efficient in this case.
5. Memory Allocation: Memory to ArrayList is allocated at the compile time itself, thus it is compulsory to specify the size of the list before execution. This is known as Static memory allocation. Also, the memory allocated is contiguous.
Example: Consider below ArrayList A and the memory address of its elements.
Whereas in the case of LinkedList, memory is allocated run time also known as dynamic memory allocation. Also, the memory location where the elements in LinkedList need not be contiguous.
Example:
Thus it is easier to expand the size of the list in case LinkedList than ArrayList.
6. Memory Storage Type: Since memory is allocated to the ArrayList at the compile time thus Stack memory is used. Whereas in the case of LinkedList memory is allocated from heap memory that is used to allocate memory to the variables at run time.
Comparison Table of ArrayList vs LinkedList
The table below summarizes the comparisons between ArrayList vs LinkedList:
| ArrayList | LinkedList |
| ArrayList is a class in a collection framework that uses a dynamic array to store the elements inside it. | LinkedList class of collection framework uses doubly LinkedList to store the elements. |
| Insertion operation performed is slow as each insertion made at an index requires shift of the latter element in the list by expanding the array-size and copy the elements to the new indexes, thus have time complexity O(n). | Insertion operation is fast as only next and previous pointer updation is required, thus have complexity O(1). |
| It can only be used to implement the list since it implements only the List interface. | It can be used to implement List as well as queue since it implements List as well as Deque interface. |
| Data access and storage is very efficient since it stores the elements according to the indexes. | Since each data access requires a complete traversal of the list thus is comparatively slow. |
| Deletion operation is also not very efficient because it also requires to resize of the array and copying elements thus have time complexity O(n). | Deletion operation is more efficient comparatively since it requires the only updation of pointers of the previous and next node thus have complexity O(1). |
| ArrayList can be used to store similar types of data. | Any type of data can be stored using LinkedList. |
| ArrayList stores the elements according to the indexes thus less memory overhead is involved. | LinkedList involves more memory overhead since |
| Memory for the ArrayList is allocated at compile time only. Thus it is known as Static Memory Allocation. | Memory is allocated to the LinkedList during run-time thus known as dynamic memory allocation. |
| ArrayList can be one dimensional, two-dimensional or multi-dimensional. | LinkedList can be either singly LinkedList, doubly or circular LinkedList. |
| Memory to the ArrayList is allocated at Stack memory location | Memory to the LinkedList is allocated in the heap memory section. |
| The size of ArrayList needs to be declared before execution. | The size of the LinkedList is variable thus need not be declared. |
| Inefficient memory utilization. | Good memory utilization. |
Examples of ArrayList and LinkedList
Code:
package Try;
import java.util.ArrayList;
import java.util.LinkedList;
public class Office
{
public static void main(String[] args)
{
ArrayList<String> arr1 = new ArrayList<String>();
arr1.add("0.Static Memory Allocation");
arr1.add("1.Faster element access");
arr1.add("2.Inefficient insertion/deletion");
System.out.println("ArrayList object properties :" + arr1);
if (arr1.contains("1.Faster element access"))
System.out.println("Present");
else
System.out.println("Not Present");
LinkedList<String> linklist1 = new LinkedList();
linklist1.add("0.Dynamuc Memory Allocation");
linklist1.add("1.Slower element access");
linklist1.add("2.Faster insertion/deletion");
System.out.println("LinkedList object Properties :" + linklist1);
if (linklist1.contains("1.Slower element access"))
System.out.println("Present");
else
System.out.println("Not Present");
}
}
Output:
Conclusion
Size of ArrayList needs to be declared at compile time and uses stack memory thus insertion and deletion operation inefficient than LinkedList where memory is allocated in heap at run time. But since indexes are used thus data access works faster in ArrayList. Search operation works similarly in both cases. Thus the use of any of these depends on our needs that which operation will be performed more often.
Recommended Articles
This is a guide to ArrayList vs LinkedList. Here we discuss the ArrayList vs LinkedList key differences with infographics and comparison table. You may also have a look at the following articles to learn more –
