What is the difference between ArrayList and LinkedList in Java?

📚 Introduction

Java provides several classes to store and manipulate lists of data. Two of the most commonly used are ArrayList and LinkedList. Both implement the List interface but differ significantly in their internal workings and performance characteristics.

Understanding when to use ArrayList vs LinkedList is essential to writing optimized and maintainable Java applications.

🧱 Underlying Data Structure

ArrayList

Internally backed by a dynamic array.
When the array fills up, a new larger array is created, and elements are copied.

List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");
System.out.println(arrayList); // [Java, Python]

LinkedList

Internally implemented as a doubly linked list.
Each element (node) contains a reference to the previous and next element.

List<String> linkedList = new LinkedList<>();
linkedList.add("Java");
linkedList.add("Python");
System.out.println(linkedList); // [Java, Python]

🧠 Memory Usage

ArrayList

Consumes less memory per element since it only stores data.
May waste memory if capacity is over-allocated.

LinkedList

Each node stores data along with two pointers (next and previous), so memory usage is higher per element.

🚀 Performance: Add, Remove, Access

Add Elements

ArrayList

Adding at the end is fast (amortized O(1)), unless resizing is required.
Adding in the middle or beginning is costly (O(n)) because it shifts elements.

List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add(0, "Python"); // shifts Java to index 1

LinkedList

Adding at the beginning or middle is O(1) if the node position is known.
However, finding the node takes O(n), so insertion overall is still O(n).

List<String> linkedList = new LinkedList<>();
linkedList.addFirst("Python");
linkedList.addLast("Java");

Remove Elements

ArrayList

Removing elements (especially not from the end) requires shifting.

arrayList.remove(0); // shifts all remaining elements

LinkedList

Can remove first or last node in O(1), but random removal still O(n).

linkedList.removeFirst();
linkedList.removeLast();

Access Elements (Random Access)

ArrayList

Directly accesses elements by index — O(1) time.

String lang = arrayList.get(1);

LinkedList

Sequentially traverses from the head or tail — O(n) time.

String lang = linkedList.get(1); // Not efficient for large lists

🧪 Iteration Performance

Both classes support iterators, but:

ArrayList is faster for random access via index-based loops.
LinkedList performs better when using iterators for sequential access, especially if you use ListIterator.

for (String lang : arrayList) {
    System.out.println(lang);
}

🔄 Use Cases

When to Use ArrayList:

Frequent random access of elements.
Rare insertions/deletions in the middle.
Memory efficiency is a concern.

When to Use LinkedList:

Frequent insertions/deletions at the start/middle.
Not concerned with memory usage.
Operations primarily use iterators.

📝 Summary

Feature	ArrayList	LinkedList
Underlying	Dynamic array	Doubly linked list
Memory	Less memory per element	More memory (pointers)
Access time	Fast (O(1))	Slow (O(n))
Add/Remove	Fast at end, slow in middle/start	Fast at start/end, slow random
Iteration	Faster with index-based loop	Better with iterator
Use case	Random read-heavy applications	Write-intensive apps, queues

Choosing between ArrayList and LinkedList depends on your use case. Use ArrayList for fast reads and LinkedList for frequent insertions or deletions.