When do you use ArrayList vs LinkedList?

• ArrayList stores elements in a contiguous Object[] array; get(i) is O(1) direct array access, add() at end is amortized O(1), but insert/remove in the middle is O(n) because elements must be shifted
• LinkedList stores each element in a Node object with prev and next pointers; addFirst/addLast/removeFirst/removeLast are O(1), but get(i) is O(n) because it must traverse nodes from head or tail
• In practice, ArrayList wins 95% of the time because CPU cache locality (contiguous memory) makes it faster even for operations where LinkedList has better theoretical complexity
• LinkedList implements both List and Deque; ArrayList implements only List and RandomAccess

What is the difference between ArrayList and LinkedList?

Both implement the List interface, but their internal structures are completely different, which gives them different performance characteristics.

ArrayList uses a dynamic array. It stores all elements in a single contiguous block of memory. When you call get(5), it computes the memory address directly: baseAddress + 5 * referenceSize. This is O(1).

LinkedList uses doubly-linked nodes. Each element is wrapped in a Node object that holds the element, a pointer to the previous node, and a pointer to the next node. When you call get(5), it starts at the head (or tail, whichever is closer) and follows pointers one by one. This is O(n).

| Operation | ArrayList | LinkedList | Winner |
|---|---|---|---|
| get(index) | O(1) | O(n) | ArrayList |
| add(end) | O(1) amortized | O(1) | Tie |
| add(0, elem) | O(n) – shifts all | O(1) | LinkedList |
| add(middle) | O(n) – shifts half | O(n) find + O(1) link | Depends |
| remove(index) | O(n) – shifts | O(n) find + O(1) unlink | Depends |
| remove via Iterator | O(n) – shifts | O(1) | LinkedList |
| contains(elem) | O(n) | O(n) | Tie |
| Memory per element | ~4 bytes | ~40 bytes | ArrayList |
| Cache locality | Excellent | Poor | ArrayList |

package com.bank.demo;

import java.math.BigDecimal;
import java.util.*;

public class ArrayListVsLinkedListDemo {
    public static void main(String[] args) {
        // ArrayList – contiguous array, fast random access
        List<String> transactionLog = new ArrayList<>();
        transactionLog.add("TXN-001: Deposit 50000");
        transactionLog.add("TXN-002: Withdraw 10000");
        transactionLog.add("TXN-003: Transfer 25000");
        String entry = transactionLog.get(1); // O(1) – direct array access
        System.out.println("ArrayList get(1): " + entry);

        // LinkedList – linked nodes, fast add/remove at ends
        LinkedList<String> processingQueue = new LinkedList<>();
        processingQueue.addLast("TXN-001");
        processingQueue.addLast("TXN-002");
        processingQueue.addLast("TXN-003");
        String first = processingQueue.removeFirst(); // O(1) – update head pointer
        System.out.println("LinkedList removeFirst: " + first);
    }
}

ArrayList get(1): TXN-002: Withdraw 10000
LinkedList removeFirst: TXN-001

Why does ArrayList win in practice despite worse theoretical complexity for some operations?

The answer is CPU cache locality. Modern CPUs do not read one byte at a time from memory. They read entire cache lines (typically 64 bytes) at once. When data is stored in a contiguous block (like an array), reading one element prefetches several nearby elements into the CPU cache. The next access is a cache hit – extremely fast.

LinkedList nodes are scattered across the heap. Each node is a separate object allocated at an unpredictable memory location. Following a pointer from one node to the next almost always causes a cache miss. The CPU must go to main memory (100+ nanoseconds) instead of the L1 cache (1-2 nanoseconds).

This means that even an O(n) operation on ArrayList (like shifting elements during add(0, elem)) is often faster than the theoretically O(1) operation on LinkedList because System.arraycopy() moves a contiguous block of memory using CPU-optimized instructions (essentially a single memcpy call), while LinkedList's pointer chasing causes repeated cache misses.

package com.bank.demo;

import java.util.*;

public class CacheLocalityBenchmark {
    public static void main(String[] args) {
        int size = 100_000;

        // ArrayList – iterate through contiguous memory
        List<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < size; i++) arrayList.add(i);

        long start = System.nanoTime();
        long sum = 0;
        for (int val : arrayList) sum += val;
        long arrayTime = System.nanoTime() - start;

        // LinkedList – iterate through scattered nodes
        List<Integer> linkedList = new LinkedList<>(arrayList);

        start = System.nanoTime();
        sum = 0;
        for (int val : linkedList) sum += val;
        long linkedTime = System.nanoTime() - start;

        System.out.println("ArrayList iteration:  " + arrayTime / 1_000_000 + " ms");
        System.out.println("LinkedList iteration: " + linkedTime / 1_000_000 + " ms");
        System.out.println("LinkedList is ~" + linkedTime / Math.max(arrayTime, 1) + "x slower");
    }
}

ArrayList iteration:  2 ms
LinkedList iteration: 8 ms
LinkedList is ~4x slower

When should you use ArrayList?

Use ArrayList when any of these are true – which is the vast majority of cases:

• You need random access by index: get(i), set(i, value).
• You iterate over the list frequently.
• You mostly add elements at the end.
• You need a general-purpose list and do not know the access pattern yet.

Banking examples where ArrayList is the right choice:

• Transaction history for an account (ordered, paginated, index-based access)
• List of EMI payments (sequential access, same structure repeats)
• Search results sorted by relevance (random access for pagination)
• Batch of account records loaded from a database query

package com.bank.service;

import java.math.BigDecimal;
import java.time.LocalDate;
import java.util.*;

public class TransactionHistoryService {
    record Transaction(String id, BigDecimal amount, LocalDate date, String type) {}

    private final List<Transaction> transactions = new ArrayList<>();

    public void addTransaction(String id, BigDecimal amount, String type) {
        transactions.add(new Transaction(id, amount, LocalDate.now(), type));
    }

    public List<Transaction> getPage(int page, int pageSize) {
        int from = page * pageSize;
        int to = Math.min(from + pageSize, transactions.size());
        if (from >= transactions.size()) return List.of();
        return new ArrayList<>(transactions.subList(from, to)); // O(1) index access
    }

    public Transaction getLatest() {
        return transactions.get(transactions.size() - 1); // O(1)
    }

    public static void main(String[] args) {
        TransactionHistoryService service = new TransactionHistoryService();
        service.addTransaction("TXN-001", new BigDecimal("50000"), "DEPOSIT");
        service.addTransaction("TXN-002", new BigDecimal("10000"), "WITHDRAW");
        service.addTransaction("TXN-003", new BigDecimal("25000"), "TRANSFER");

        System.out.println("Latest: " + service.getLatest());
        System.out.println("Page 0: " + service.getPage(0, 2));
    }
}

Latest: Transaction[id=TXN-003, amount=25000, date=2024-11-02, type=TRANSFER]
Page 0: [Transaction[id=TXN-001, amount=50000, date=2024-11-02, type=DEPOSIT], Transaction[id=TXN-002, amount=10000, date=2024-11-02, type=WITHDRAW]]

When should you use LinkedList?

LinkedList has only two legitimate use cases in modern Java:

1. You need O(1) insert/remove at the current iterator position during traversal. When you have a ListIterator positioned at an element, add() and remove() are O(1) on LinkedList (just rewire pointers) but O(n) on ArrayList (must shift all subsequent elements).

2. You need both List and Deque interfaces on the same object. LinkedList implements both. However, ArrayDeque is faster for pure Deque operations.

package com.bank.service;

import java.util.*;

public class LinkedListIteratorAdvantage {
    public static void main(String[] args) {
        // Scenario: remove all flagged transactions during a single traversal
        LinkedList<String> transactions = new LinkedList<>(List.of(
            "TXN-001: OK",
            "TXN-002: FLAGGED",
            "TXN-003: OK",
            "TXN-004: FLAGGED",
            "TXN-005: OK"
        ));

        // ListIterator remove is O(1) on LinkedList
        ListIterator<String> it = transactions.listIterator();
        while (it.hasNext()) {
            String txn = it.next();
            if (txn.contains("FLAGGED")) {
                it.remove(); // O(1) – just rewire prev/next pointers
            }
        }
        System.out.println("After cleanup: " + transactions);

        // Insert audit entries during traversal
        it = transactions.listIterator();
        while (it.hasNext()) {
            String txn = it.next();
            it.add("AUDIT: verified " + txn); // O(1) – insert after current
        }
        System.out.println("After audit: " + transactions);
    }
}

After cleanup: [TXN-001: OK, TXN-003: OK, TXN-005: OK]
After audit: [TXN-001: OK, AUDIT: verified TXN-001: OK, TXN-003: OK, AUDIT: verified TXN-003: OK, TXN-005: OK, AUDIT: verified TXN-005: OK]

How is ArrayList different from LinkedList in memory usage?

ArrayList stores element references in a contiguous array. Each reference is 4 bytes (compressed oops) or 8 bytes (64-bit without compressed oops). For 1 million elements, that is about 4 MB of references plus the array object overhead.

• LinkedList wraps each element in a Node object. Each node has:
• Object header: 16 bytes (on 64-bit JVM with compressed oops)
• item reference: 4 bytes
• next reference: 4 bytes
• prev reference: 4 bytes
• Padding: 4 bytes (to align to 8-byte boundary)

Total per node: about 32-40 bytes. For 1 million elements, that is 32-40 MB – roughly 8-10 times more than ArrayList.

package com.bank.demo;

import java.util.*;

public class MemoryComparisonDemo {
    public static void main(String[] args) {
        int size = 1_000_000;

        // Approximate memory usage
        // ArrayList: 4 bytes * size + array overhead = ~4 MB
        long arrayListMemory = 4L * size + 16; // array header
        System.out.println("ArrayList approx: " + arrayListMemory / 1024 / 1024 + " MB");

        // LinkedList: ~40 bytes * size (Node objects)
        long linkedListMemory = 40L * size;
        System.out.println("LinkedList approx: " + linkedListMemory / 1024 / 1024 + " MB");

        System.out.println("LinkedList uses ~" + (linkedListMemory / arrayListMemory) + "x more memory");
    }
}

ArrayList approx: 3 MB
LinkedList approx: 38 MB
LinkedList uses ~9x more memory

What about ArrayDeque as an alternative to LinkedList?

For queue (FIFO) and stack (LIFO) operations, ArrayDeque outperforms LinkedList in almost every benchmark. ArrayDeque is backed by a resizable circular array, so it has the same cache locality advantage as ArrayList.

The Java documentation itself says: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue."

| Operation | LinkedList (Deque) | ArrayDeque | Winner |
|---|---|---|---|
| offerFirst / offerLast | O(1) | O(1) amortized | ArrayDeque (cache) |
| pollFirst / pollLast | O(1) | O(1) | ArrayDeque (cache) |
| peekFirst / peekLast | O(1) | O(1) | ArrayDeque (cache) |
| Memory per element | ~40 bytes | ~4 bytes | ArrayDeque |
| Allows null | Yes | No | LinkedList |
| Implements List | Yes | No | LinkedList |

package com.bank.service;

import java.util.*;

public class DequeComparisonDemo {
    public static void main(String[] args) {
        // Transaction processing queue – use ArrayDeque, not LinkedList
        Deque<String> queue = new ArrayDeque<>();
        queue.offerLast("TXN-001: Deposit 50000");
        queue.offerLast("TXN-002: Withdraw 10000");
        queue.offerLast("TXN-003: Transfer 25000");

        // Process FIFO
        while (!queue.isEmpty()) {
            String txn = queue.pollFirst();
            System.out.println("Processing: " + txn);
        }

        // Stack behavior – use ArrayDeque, not Stack (legacy)
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Action 1: opened account");
        undoStack.push("Action 2: deposited 50000");
        undoStack.push("Action 3: set up auto-pay");

        System.out.println("Undo: " + undoStack.pop()); // LIFO
    }
}

Processing: TXN-001: Deposit 50000
Processing: TXN-002: Withdraw 10000
Processing: TXN-003: Transfer 25000
Undo: Action 3: set up auto-pay

What are common mistakes when choosing between ArrayList and LinkedList?

Mistake 1: Using LinkedList for random access

// WRONG – O(n) for every get() call
LinkedList<String> accounts = new LinkedList<>();
for (int i = 0; i < 10000; i++) accounts.add("ACC" + i);

for (int i = 0; i < accounts.size(); i++) {
    String acc = accounts.get(i); // O(i) traversal each time!
    // Total: O(n^2) – disastrous for large lists
}

// CORRECT – use ArrayList for index-based access
ArrayList<String> accounts2 = new ArrayList<>();
for (int i = 0; i < 10000; i++) accounts2.add("ACC" + i);
for (int i = 0; i < accounts2.size(); i++) {
    String acc = accounts2.get(i); // O(1) each time. Total: O(n)
}

Mistake 2: Using LinkedList as a queue instead of ArrayDeque

// SUBOPTIMAL – LinkedList has cache misses
Queue<String> queue1 = new LinkedList<>();

// BETTER – ArrayDeque is faster and uses less memory
Queue<String> queue2 = new ArrayDeque<>();

Mistake 3: Assuming LinkedList add(middle) is always O(1)

// LinkedList.add(index, element) is NOT O(1)!
LinkedList<String> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) list.add("ACC" + i);
list.add(5000, "NEW"); // O(n) – must traverse to position 5000 first!
// Only O(1) when you already have a ListIterator at the position

What about thread safety?

Neither ArrayList nor LinkedList is thread-safe. For concurrent access:

• Read-heavy: CopyOnWriteArrayList – reads are lock-free, writes copy the entire array.
• Write-heavy: Collections.synchronizedList(new ArrayList<>()) – every operation is synchronized.
• Queue behavior: ConcurrentLinkedQueue or LinkedBlockingQueue – designed for producer-consumer patterns.

Never use a plain ArrayList or LinkedList with multiple threads without external synchronization.

What should a senior engineer know?

- RandomAccess marker interface. ArrayList implements RandomAccess, a marker interface that tells algorithms to use index-based access. Collections.binarySearch() checks for this: if the list implements RandomAccess, it uses index access (O(log n) for ArrayList). If not (LinkedList), it uses an iterator-based approach. You can check: if (list instanceof RandomAccess) to choose the optimal algorithm.

- ArrayList.trimToSize(). After bulk loading, call trimToSize() to shrink the internal array to match the actual size. This reclaims wasted memory. Useful after loading 2 million account records where the internal array might have 3 million slots.

- Serialization difference. ArrayList serializes only the actual elements (not empty array slots). LinkedList serializes each node. For the same data, ArrayList's serialized form is smaller and faster to deserialize.

- Structural modification count (modCount). Both maintain a modCount field that increments on every structural change (add, remove). Iterators check this value to detect concurrent modification and throw ConcurrentModificationException. This is why you cannot modify a list while iterating with a for-each loop.

- Null elements. Both allow null elements. But be careful: contains(null), indexOf(null), and remove(null) all work but can cause subtle bugs if you mix null and non-null elements.

What are common interview follow-up questions?

• "What is the internal data structure of ArrayList?" – dynamic array (Object[]).
• "What is the growth strategy of ArrayList?" – 1.5x (old + old >> 1).
• "Why is LinkedList slower than ArrayList for iteration?" – cache misses from scattered heap nodes.
• "When is LinkedList genuinely faster?" – ListIterator-based insert/remove during traversal.
• "What is ArrayDeque and why is it better than LinkedList for queues?" – contiguous circular array, better cache locality.