Linked list memory allocation Java

Difference Between ArrayListvs 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 access the elements directly. 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 the circular list) and helps in efficient insertion and deletion from the list.

Head to Head Comparison between ArrayListvs LinkedList (Infographics)

Below are the top 12 comparisons between ArrayList vs LinkedList:

Key differences between ArrayListvs LinkedList

Let us discuss some key differences between ArrayListvs 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.

Popular Course in this category

JavaScript Training Program (39 Courses, 23 Projects, 4 Quizzes)39 Online Courses | 23 Hands-on Projects | 225+ Hours | Verifiable Certificate of Completion | Lifetime Access | 4 Quizzes with Solutions
4.5 (8,163 ratings)

Course Price

View Course

---

Related Courses

Java Training (40 Courses, 29 Projects, 4 Quizzes)Python Training Program (39 Courses, 13+ Projects)HTML Training (12 Courses, 19+ Projects, 4 Quizzes)

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 the 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 the 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:

Thusit is easier to expand the size of the list in caseLinkedListthanArrayList.

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 ArrayListvs LinkedList

The table below summarizes the comparisons between ArrayList vs LinkedList:

Examples of ArrayList and LinkedList

Code:

packageTry;
importjava.util.ArrayList;
importjava.util.LinkedList;
publicclassOffice
{
publicstaticvoidmain(String[]args)
{
ArrayList arr1 =newArrayList();
arr1.add("0.Static Memory Allocation");
arr1.add("1.Faster element access");
arr1.add("2.Inefficient insertion/deletion");
System.out.println("ArrayListobjectproperties :" + arr1);
if(arr1.contains("1.Fasterelement access"))
System.out.println("Present");
else
System.out.println("Not Present");
LinkedList linklist1 =newLinkedList();
linklist1.add("0.Dynamuc Memory Allocation");
linklist1.add("1.Slower element access");
linklist1.add("2.Faster insertion/deletion");
System.out.println("LinkedList objectProperties :" + linklist1);
if(linklist1.contains("1.Slowerelement 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 a heap at run time. But since indexes are used thus, data access works faster in ArrayList. Search operation works similarly in both cases. Thus, 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

1. JPanel in Java
2. Array vs ArrayList
3. Java Vector vs ArrayList
4. LinkedList in Java