Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is ArrayList?
3.
What is LinkedList?
4.
What are the Key Differences Between ArrayList vs LinkedList?
5.
Difference between Arraylist and Linkedlist
6.
Example of ArrayList and LinkedList in Java
6.1.
Working of an ArrayList
6.2.
Example of working of ArrayList
6.2.1.
Explanation 
6.3.
Working of a LinkedList
6.4.
Example of working of Linked List
6.4.1.
Explanation
7.
Points to Remember
8.
When Should We Use ArrayList or LinkedList ?
9.
Frequently Asked Questions
9.1.
What is the difference between ArrayList and LinkedList?
9.2.
What is the advantage of ArrayList vs LinkedList?
9.3.
What is difference between ArrayList and vector and LinkedList in Java?
9.4.
What is the difference between ArrayList and LinkedList memory allocation?
10.
Conclusion
Last Updated: Mar 27, 2024
Medium

Difference between ArrayList and LinkedList

Author Nikunj Goel
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

The Array and LinkedList are popular data structures in Java. And both arraylist and linkedlist are used to store and manage collections of objects. These collections are part of the Java Framework. 

Regardless of the language we code in, one of the first things that we encounter are data structures, which are the different ways we can organize our data; arraysstacks, linked lists, variables, etc., are all different types of data structures. These are just the tip of the iceberg for data structures. 

In this blog, we will check the difference between arraylist and linkedlist.

Difference between ArrayList and LinkedList

What is ArrayList?

An ArrayList is a dynamic array-based data structure in Java that can grow or shrink in size dynamically. It's part of the Java Collections Framework and allows you to store and manipulate a list of elements, providing methods for adding, removing, and accessing elements. Unlike traditional arrays, ArrayLists automatically handle resizing, making them more flexible for many programming tasks.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

What is LinkedList?

A LinkedList is a data structure in which elements are connected through pointers or references. It consists of nodes, each containing data and a reference to the next node in the sequence. There are singly linked lists (each node points to the next) and doubly linked lists (nodes have references to both the next and previous nodes). LinkedLists are efficient for insertions and deletions in the middle but less efficient for random access. They're used in various data structures and algorithms.

What are the Key Differences Between ArrayList vs LinkedList?

The main differences between ArrayList and LinkedList in Java are:

Internal Structure:

  • ArrayList uses an array to store elements.
  • LinkedList uses a doubly linked list structure with nodes containing data and references to the next and previous nodes.
     

Access Time:

  • ArrayList provides faster random access time due to direct array indexing.
  • LinkedList is slower for random access but efficient for insertions and deletions in the middle.
     

Insertions and Deletions:

  • ArrayList is less efficient for insertions and deletions in the middle because elements need to be shifted.
  • LinkedList excels in insertions and deletions at any position due to its structure.
     

Memory Usage:

  • ArrayList may have slightly less memory overhead due to its simple array structure.
  • LinkedList has more memory overhead because of the additional node references.
     

Iterating Through Elements:

  • ArrayList is faster when iterating sequentially through elements.
  • LinkedList is slower due to the need to follow node references.
     

Implementation:

  • ArrayList is a more straightforward implementation.
  • LinkedList involves more complex pointer manipulation.
     

The choice between ArrayList and LinkedList depends on your specific use case. If you need fast random access and are not frequently inserting or removing elements in the middle, ArrayList is a better choice. If you require efficient insertions and deletions or are working with large datasets, LinkedList may be more suitable.

Difference between Arraylist and Linkedlist

Key ArrayList LinkedList
Internal Implementation  Uses an array to store elements  Uses a doubly linked list to store elements
 
Access time  O(1) for random access, O(n) for insertion and deletion  O(n) for random access, O(1) for insertion and deletion
 
Memory usage More memory is used for maintaining the size of the array Less memory is used since only the elements and pointers are stored
Iteration performance Fast, since elements are stored in contiguous memory locations Slower, since elements are not stored in contiguous memory locations
Adding elements Can be slow if the size of the array needs to be increased to accommodate new elements Fast, since only pointers need to be updated
Removing elements Can be slow if elements need to be shifted to fill the gap left by the removed element Fast, since only pointers need to be updated
Thread safety Not inherently thread-safe, but can be made thread-safe using synchronization. Not inherently thread-safe, but can be made thread-safe using synchronization.
Use cases Best suited for scenarios where random access is required and the list will not be modified frequently Best suited for scenarios where insertion and deletion are frequent, and random access is not required.

Example of ArrayList and LinkedList in Java

Working of an ArrayList

An ArrayList is a dynamic array data structure that allows elements to be added or removed, automatically resizing itself, unlike static arrays with fixed sizes. It's part of the Java Collections Framework and provides a way to store elements sequentially, offering fast access to elements via indexes. Internally, when an ArrayList reaches its capacity and an additional element is added, it creates a new, larger array, copies the existing elements into the new array, and discards the old one. This process, known as "resizing," helps ArrayList to adjust its size dynamically, making it a flexible and widely used collection for storing ordered data.

Example of working of ArrayList

import java.util.ArrayList;

public class NinjaArrayList {

    public static void main(String[] args) {


        // Creating an ArrayList of integers
        ArrayList<Integer> NinjaList = new ArrayList<>();


        // Adding elements 
        NinjaList.add(5);
        NinjaList.add(10);
        NinjaList.add(15);
        
        System.out.println("The initial ArrayList\n");
        System.out.println("Array List:"+NinjaList+"\n");
        System.out.println("Size of the ArrayList: " + NinjaList.size());
    
        System.out.println("Iterating over the Array List");


        // Iterating over the ArrayList
        for (int i = 0; i < NinjaList.size(); i++) {
            System.out.println("Number at index " + i + " is " + NinjaList.get(i));
        }
        
        // Modifying the element 
        NinjaList.set(0,8);
        
        // Accessing the element
       System.out.println("Number at index 1 " + NinjaList.get(1)+"\n");
        
        // Removing the element 
        NinjaList.remove(2);
        
        System.out.println("The final ArrayList");
        
        //Printing the final ArrayList
        System.out.println("Array List:"+NinjaList+"\n");
        System.out.println("Size of the ArrayList: " + NinjaList.size());
       
    }
}

 

Output

output

 

Explanation
 

  • In the above code, we have created an ArrayList, which is part of ‘java.util’ package. ArrayList is a dynamic array, which means we have not assigned any fixed size to it. As we add elements to the array, its size increases. 
     
  • For using ArrayList in our program, we have imported the ‘ArrayList’ class and created an ArrayList, and named it ‘NinjaList’ using the line, ArrayList<Integer> NinjaList = new ArrayList<>();
     
  •  Further, we have iterated over the linked list using the for loop.
     
  • Next, we've added elements using the ‘add()’ method. We have used the ‘get()’ method for accessing the elements, which accepts an index as its argument.
     
  • We have used the ‘set()’ method for modifying the element at any specific index, and the ‘remove()’ method is used for removing an element from the ArrayList.  The ‘size()’ method gives the size of the array list.

Working of a LinkedList

A LinkedList in Java is a linear data structure that stores elements in nodes, where each node contains the data and a reference to the next node in the sequence. This allows for efficient insertion and removal of elements, as it only requires updating the node references, without the need to shift elements as in an array-based structure like ArrayList. However, accessing elements in a LinkedList is generally slower, as it requires sequential traversal from the beginning or end of the list to reach the desired element.

Example of working of Linked List

import java.util.LinkedList;

public class NinjaLinkedList {

    public static void main(String[] args) {

        // Creating a LinkedList
        LinkedList<Integer> NumberLinkedList = new LinkedList<>();


        // Adding elements to the LinkedList
        NumberLinkedList.add(5);
        NumberLinkedList.add(10);
        NumberLinkedList.add(15);
        
        System.out.println("The initial LinkedList");
        System.out.println("LinkedList:"+NumberLinkedList+"\n");
        System.out.println("Size of the LinkedList: " + NumberLinkedList.size()+"\n");
        
        System.out.println("Iterating over the LinkedList\n");
        
        for (int value : NumberLinkedList) {

            System.out.println("Element->" + value);

        }
        System.out.println("\n");
        
        // Modifying the element 
        NumberLinkedList.set(0,8);
        
       // Accessing the element
       System.out.println("Number at 1 position is " + NumberLinkedList.get(1));
        
        // Removing the element 
        NumberLinkedList.remove(2);
        System.out.println("Third element removed\n");
        
        System.out.println("The final LinkedList");
        
        // Printing the final LinkedList
        System.out.println("LinkedList:"+NumberLinkedList+"\n");
        System.out.println("Size of the LinkedList: " + NumberLinkedList.size());
      
    }
}

 

Output

output

 

Explanation

  • In the above code, we have used the ‘LinkedList’ class, which is a part of the ‘java.util’ package. It gives the Doubly Linked List implementation.
     
  • To use it, we must import the ‘LinkedList’ class. We have created a LinkedList named ‘NumberLinkedList’ for storing the integers. 
     
  • Next, we've added the elements using the ‘add()’ method. Further, we have iterated over the linked list using the for loop.
     
  •  We can access the elements stored in Linked List using the ‘get()’ method. Similarly, the ‘remove()’ method is used for removing an element in the LinkedList at the specific index.

Points to Remember

The following are some important points to remember regarding an ArrayList and LinkedList.

  • We must opt for LinkedList when the rate of adding and removing the elements is higher as compared to the read scenarios. On the other hand, one can go for ArrayList when the read scenarios have greater frequency than the removal or addition rate.
     
  • ArrayList is considered to be more cache-friendly than the Linked List, as the storage of the elements in ArrayList is more compact.
     
  • LinkedList usually has more memory overhead than ArrayList because there are extra links in Linked List, i.e., the next and the previous links. Therefore the address of the previous and next nodes are stored, which takes up extra space.

When Should We Use ArrayList or LinkedList ?

When deciding between using an ArrayList or a LinkedList in Java, consider the following factors:

Use an ArrayList when:

  • Random Access is Required: You frequently access elements by their index, as ArrayList offers O(1) time complexity for get operations.
  • Adding Elements to the End: You primarily add elements to the end of the list, where ArrayList is efficient.
  • Memory Overhead Concerns: You're concerned about memory overhead, as ArrayList has a lower memory footprint compared to LinkedList.
  • Minimal Insertions and Deletions: Your operations involve minimal insertions and deletions in the middle of the list, as these operations are costly in ArrayList due to the need for shifting elements.
     

Use a LinkedList when:

  • Frequent Insertions and Deletions: You frequently insert or remove elements from the beginning, middle, or end of the list, as LinkedList excels in these operations without the need for element shifting.
  • Implementing Stacks or Queues: You're implementing data structures like stacks or queues, where the LinkedList provides inherent support for operations at the ends.
  • Memory is Less of a Concern: You're less concerned about memory usage, as LinkedList consumes more memory due to the storage of additional pointers for each element.
  • Sequential Access: Your use case involves more sequential access through the list, as LinkedList requires traversal from the beginning or end to access elements.

Frequently Asked Questions

What is the difference between ArrayList and LinkedList?

ArrayList uses an array for storage and provides faster random access but slower insertions. LinkedList employs nodes connected by references, excelling in insertions and deletions but with slower random access.

What is the advantage of ArrayList vs LinkedList?

The advantage of ArrayList is faster random access due to direct indexing, making it more suitable for scenarios where quick element retrieval is critical. In contrast, LinkedList is advantageous for efficient insertions and deletions at any position within the list. The choice between them depends on your specific use case and performance requirements.

What is difference between ArrayList and vector and LinkedList in Java?

ArrayList and Vector:

  • Both are dynamic arrays.
  • ArrayList is not synchronized and more efficient.
  • Vector is synchronized for thread safety but slower.

LinkedList:

  • Uses a doubly linked list.
  • Efficient for insertions/removals.
  • Slower for random access compared to arrays.

What is the difference between ArrayList and LinkedList memory allocation?

The memory allocation for ArrayList is more straightforward, as it uses a single contiguous array. In contrast, LinkedList involves more memory overhead due to the additional node references and non-contiguous storage.

Conclusion

With this discussion, this blog attempted to compare the data structures Linked List vs Arrays, along with the advantages and disadvantages. The Array and LinkedList are popular data structures in Java and both arraylist and linkedlist are used to store and manage collections of objects. These collections are part of the Java Framework. 

Now that you know the data structures well go ahead and attempt some questions based on them on our Coding Ninjas Studio Platform!

Recommended Reading:

Recommended problems:

We hope you found this blog useful. Feel free to let us know your thoughts in the comments section.

Previous article
Linked List in Data Structures
Next article
Merge Sort For Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass