Java  

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.

Membership not found