Difference between ArrayList and LinkedList

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; arrays, stacks, 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.

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.

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

ArrayList

Code

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

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.

Linked List

Code

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

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.

Check this out, Interface in Java

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.