What is the internal implementation of ArrayList and LinkedList?

ArrayList and LinkedList are both List implementations in Java, but they use different internal data structures. ArrayList is implemented using a dynamic array, while LinkedList is implemented as a doubly linked list. These differences directly affect their performance characteristics and use cases.

Key Points: • ArrayList uses a dynamically resizable array internally. • LinkedList uses a doubly linked list structure. • ArrayList provides fast random access using indexes. • LinkedList provides efficient insertion and deletion operations. • The choice between them depends on access and modification requirements.

Internal Implementation of ArrayList

ArrayList stores elements in a dynamic array called elementData.

Simplified Internal Structure:

[element1][element2][element3][element4]

Characteristics:

• Elements are stored in contiguous memory locations. • Supports fast index-based access. • Automatically grows when capacity is exceeded. • Resizing involves creating a larger array and copying existing elements.

Access Time:

get(index) → O(1)

Insertion/Deletion in Middle:

O(n)

because elements need to be shifted.

Example:

Index: 0 1 2 Data: Java Spring Hibernate

Accessing:

list.get(2)

Directly retrieves "Hibernate".

Internal Implementation of LinkedList

LinkedList is implemented as a doubly linked list.

Each node contains:

• Data • Reference to previous node • Reference to next node

Simplified Structure:

null <- [Java] <-> [Spring] <-> [Hibernate] -> null

Characteristics:

• Elements are not stored in contiguous memory. • Each node maintains links to neighboring nodes. • Efficient insertion and deletion. • Slower random access because traversal is required.

Access Time:

get(index) → O(n)

Insertion/Deletion at Beginning or End:

O(1)

Example: Suppose we need to add a new element between Java and Spring.

ArrayList:

Java, Spring, Hibernate

Insert "Microservices"

Elements must be shifted.

LinkedList:

Java <-> Spring <-> Hibernate

Only node references are updated.

No element shifting is required.

Code Example:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Demo {

    public static void main(String[] args) {

        List<String> arrayList =
                new ArrayList<>();

        arrayList.add("Java");
        arrayList.add("Spring");

        List<String> linkedList =
                new LinkedList<>();

        linkedList.add("Java");
        linkedList.add("Spring");

        System.out.println(arrayList);
        System.out.println(linkedList);
    }
}

Output:

[Java, Spring] [Java, Spring]

Performance Comparison:

Operation ArrayList LinkedList

Random Access O(1) O(n)

Insert at End           O(1)*          O(1)

Insert in Middle        O(n)           O(1)**

Delete in Middle        O(n)           O(1)**

Memory Usage Lower Higher

* Amortized O(1)
** After locating the node

When to Use ArrayList?

• Frequent read operations • Index-based access required • Fewer insertions and deletions

Examples:

• Product lists • Employee records • Search results

When to Use LinkedList?

• Frequent insertions and deletions • Queue and deque implementations • Dynamic data modifications

Examples:

• Task scheduling • Browser history • Undo/redo functionality

Interview Tip: A concise interview answer is:

"ArrayList is internally implemented using a dynamic array, which provides O(1) random access but requires shifting elements during insertions and deletions. LinkedList is implemented as a doubly linked list, where each node stores references to the previous and next nodes, making insertions and deletions efficient but random access slower at O(n)."