EDUCBA

EDUCBA

MENUMENU
  • Blog
  • Free Courses
  • All Courses
  • All in One Bundle
  • Login
Home Software Development Software Development Tutorials Top Differences Tutorial ArrayList vs LinkedList

ArrayList vs LinkedList

Savi Jagga
Article bySavi Jagga
Priya Pedamkar
Reviewed byPriya Pedamkar

Updated March 28, 2023

ArrayList vs LinkedList

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 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.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Head to Head Comparison between ArrayList vs LinkedList  (Infographics)

Below are the top 12 comparisons between ArrayList vs LinkedList:

ArrayList-vs-LinkedList-info

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.

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.

Memory Address Example3

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:

ArrayList vs LinkedList 2

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 its elements. 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 a 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 and the 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 resizing the array and copying elements, thus having 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 the 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:

Object Properties Example

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
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
All in One Software Development Bundle5000+ Hours of HD Videos | 149 Learning Paths | 1050+ Courses | Verifiable Certificate of Completion | Lifetime Access
Financial Analyst Masters Training Program2000+ Hours of HD Videos | 43 Learning Paths | 550+ Courses | Verifiable Certificate of Completion | Lifetime Access
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more