Back to Linked List
Q4Question 4 of 25

What are linked lists and how does pointer manipulation work

Answer: A linked list is a data structure where each element (node) contains a value and a reference to the next node, and pointer manipulation means changing these references to insert, delete, reverse, or rearrange nodes without moving data in memory.

Key Concepts
  • A linked list is a linear data structure where each node holds a value and a reference (pointer) to the next node, forming a chain.
  • A singly linked list has one pointer per node (next), while a doubly linked list has two (next and prev), allowing traversal in both directions.
  • Java's LinkedList class implements both List and Deque, and is a doubly linked list internally.
  • Insertion and deletion at a known position are O(1) in a linked list because only pointers change, compared to O(n) in ArrayList which shifts elements.
  • Random access by index is O(n) in a linked list because you must traverse from the head, compared to O(1) in ArrayList.
  • Pointer manipulation means changing next and prev references to insert, delete, reverse, or detect cycles in the list.
  • Use ArrayList for random access and iteration. Use LinkedList only when you frequently insert or remove at the head or during iteration.

Definition

A linked list is a data structure where each element (node) contains a value and a reference to the next node, and pointer manipulation means changing these references to insert, delete, reverse, or rearrange nodes without moving data in memory.
  • Linked list is a linear data structure where elements are stored in nodes, each pointing to the next node via a reference (pointer), rather than being stored in a contiguous array.
  • Singly linked list has one pointer per node (next), allowing traversal only from head to tail.
  • Doubly linked list has two pointers per node (next and prev), allowing traversal in both directions; Java's LinkedList class is a doubly linked list.
  • Pointer manipulation is the technique of reassigning next and prev references to insert, delete, reverse, or rearrange nodes in O(1) time at a known position.
  • Cycle detection is the problem of determining whether a linked list contains a loop, solved by Floyd's tortoise and hare algorithm using two pointers moving at different speeds.

Think of a chain of bank transaction slips at National Bank of India. Each slip has the transaction details written on it and a clip attaching it to the next slip. Rajesh can add a new slip between any two existing slips by unclipping and reclipping (pointer change, O(1)). But to find the 50th slip, he must follow the chain from the first slip, counting one by one (O(n)). If someone accidentally clips the last slip back to an earlier slip, the chain forms a loop, and Rajesh would follow it forever unless he uses a cycle detection technique.

Understanding the Concepts

What is a linked list?

A linked list is a data structure made of nodes. Each node stores a value and a reference (pointer) to the next node. The first node is called the head, and the last node points to null. Unlike an array, linked list nodes are not stored in contiguous memory.

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class SinglyLinkedListDemo {

    static class TransactionNode {
        String accountId;
        BigDecimal amount;
        TransactionNode next;

        TransactionNode(String accountId, BigDecimal amount) {
            this.accountId = accountId;
            this.amount = amount;
            this.next = null;
        }
    }

    public static void main(String[] args) {
        // Build a chain: head -> node1 -> node2 -> null
        var head = new TransactionNode("SAV2001", new BigDecimal("50000.00"));
        var node1 = new TransactionNode("CUR3001", new BigDecimal("120000.00"));
        var node2 = new TransactionNode("SAV2002", new BigDecimal("8000.00"));
        head.next = node1;
        node1.next = node2;

        // Traverse the list
        System.out.println("Transaction history (singly linked list):");
        var current = head;
        while (current != null) {
            System.out.println("  " + current.accountId + ": " + current.amount + " INR");
            current = current.next;
        }
    }
}
TEXT
Expected output:
Transaction history (singly linked list):
  SAV2001: 50000.00 INR
  CUR3001: 120000.00 INR
  SAV2002: 8000.00 INR

How does pointer manipulation work?

Pointer manipulation means changing the next (and prev, in doubly linked lists) references to modify the list structure. To insert a node between two existing nodes, you redirect the previous node's next pointer to the new node, and set the new node's next pointer to the following node. No elements need to shift.

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class PointerManipulationDemo {

    static class TxnNode {
        String id;
        BigDecimal amount;
        TxnNode next;
        TxnNode(String id, BigDecimal amount) { this.id = id; this.amount = amount; }
    }

    static void printList(TxnNode head) {
        var current = head;
        while (current != null) {
            System.out.print(current.id + "(" + current.amount + ")");
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        var head = new TxnNode("T1", new BigDecimal("10000"));
        var t2 = new TxnNode("T2", new BigDecimal("25000"));
        var t3 = new TxnNode("T3", new BigDecimal("5000"));
        head.next = t2;
        t2.next = t3;

        System.out.println("Before insert:");
        printList(head);

        // Insert T4 between T2 and T3
        var t4 = new TxnNode("T4", new BigDecimal("75000"));
        t4.next = t2.next;  // T4.next -> T3
        t2.next = t4;       // T2.next -> T4

        System.out.println("After inserting T4 between T2 and T3:");
        printList(head);

        // Delete T4: skip it by pointing T2 directly to T3
        t2.next = t4.next;  // T2.next -> T3

        System.out.println("After deleting T4:");
        printList(head);
    }
}
TEXT
Expected output:
Before insert:
T1(10000) -> T2(25000) -> T3(5000) -> null
After inserting T4 between T2 and T3:
T1(10000) -> T2(25000) -> T4(75000) -> T3(5000) -> null
After deleting T4:
T1(10000) -> T2(25000) -> T3(5000) -> null

How is LinkedList different from ArrayList?

FeatureArrayListLinkedList
Internal structureResizable arrayDoubly linked nodes
Random access (get by index)O(1)O(n)
Insert/delete at headO(n), shifts all elementsO(1)
Insert/delete at tailO(1) amortizedO(1)
Insert/delete in middleO(n), shifts elementsO(1) at a known node
Memory per element4 bytes (reference)24 bytes (value + next + prev)
Cache friendlinessHigh (contiguous memory)Low (scattered nodes)
Iteration speedFaster (cache lines)Slower (pointer chasing)
Implements DequeNoYes
JAVA
package com.bank.core;

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

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

        // Measure add-at-head performance
        List<BigDecimal> arrayList = new ArrayList<>();
        List<BigDecimal> linkedList = new LinkedList<>();
        var amount = new BigDecimal("1000.00");

        long start = System.nanoTime();
        for (int i = 0; i < size; i++) arrayList.addFirst(amount);
        long alTime = (System.nanoTime() - start) / 1_000_000;

        start = System.nanoTime();
        for (int i = 0; i < size; i++) linkedList.addFirst(amount);
        long llTime = (System.nanoTime() - start) / 1_000_000;

        System.out.println("Add 100K elements at head:");
        System.out.println("  ArrayList:  " + alTime + " ms");
        System.out.println("  LinkedList: " + llTime + " ms");

        // Measure random access
        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) arrayList.get(i);
        long alGet = (System.nanoTime() - start) / 1_000_000;

        start = System.nanoTime();
        for (int i = 0; i < 10_000; i++) linkedList.get(i);
        long llGet = (System.nanoTime() - start) / 1_000_000;

        System.out.println("Get 10K elements by index:");
        System.out.println("  ArrayList:  " + alGet + " ms");
        System.out.println("  LinkedList: " + llGet + " ms");
        System.out.println("ArrayList wins random access. LinkedList wins head inserts.");
    }
}
TEXT
Expected output:
Add 100K elements at head:
  ArrayList:  1850 ms
  LinkedList: 8 ms
Get 10K elements by index:
  ArrayList:  0 ms
  LinkedList: 320 ms
ArrayList wins random access. LinkedList wins head inserts.

What is a complete banking project using linked lists?

This project maintains a transaction history as a custom singly linked list, supports reversing the transaction order, and detects cycles in a payment chain.

Project structure

DIAGRAM
bank-linked-list-service/
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── bank/
│                   └── core/
│                       ├── TransactionNode.java
│                       ├── TransactionHistory.java
│                       ├── CycleDetector.java
│                       └── LinkedListBankApp.java
└── run.sh

TransactionNode.java

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class TransactionNode {
    String txnId;
    String accountId;
    BigDecimal amount;
    TransactionNode next;

    public TransactionNode(String txnId, String accountId, BigDecimal amount) {
        this.txnId = txnId;
        this.accountId = accountId;
        this.amount = amount;
        this.next = null;
    }

    @Override
    public String toString() {
        return txnId + " [" + accountId + "] " + amount + " INR";
    }
}

TransactionHistory.java

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class TransactionHistory {
    TransactionNode head;
    int size;

    public void addFirst(String txnId, String accountId, BigDecimal amount) {
        var node = new TransactionNode(txnId, accountId, amount);
        node.next = head;
        head = node;
        size++;
    }

    public void reverse() {
        TransactionNode prev = null;
        TransactionNode current = head;
        while (current != null) {
            TransactionNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        head = prev;
    }

    public void print(String label) {
        System.out.println(label + " (" + size + " transactions):");
        var current = head;
        while (current != null) {
            System.out.println("  " + current);
            current = current.next;
        }
    }
}

CycleDetector.java

JAVA
package com.bank.core;

public class CycleDetector {

    // Floyd's tortoise and hare algorithm
    public static boolean hasCycle(TransactionNode head) {
        TransactionNode slow = head;
        TransactionNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

LinkedListBankApp.java

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class LinkedListBankApp {
    public static void main(String[] args) {
        System.out.println("=== National Bank of India: Transaction History ===");

        var history = new TransactionHistory();
        history.addFirst("TXN-1003", "SAV2002", new BigDecimal("8000.00"));
        history.addFirst("TXN-1002", "CUR3001", new BigDecimal("250000.00"));
        history.addFirst("TXN-1001", "SAV2001", new BigDecimal("50000.00"));

        history.print("Original order");

        history.reverse();
        history.print("\nReversed order");

        // Cycle detection
        System.out.println("\nCycle detection:");
        System.out.println("  Has cycle (normal list): " + CycleDetector.hasCycle(history.head));

        // Create a cycle for testing
        var n1 = new TransactionNode("P1", "SAV2001", new BigDecimal("10000"));
        var n2 = new TransactionNode("P2", "CUR3001", new BigDecimal("20000"));
        var n3 = new TransactionNode("P3", "SAV2002", new BigDecimal("30000"));
        n1.next = n2;
        n2.next = n3;
        n3.next = n1; // cycle: n3 points back to n1

        System.out.println("  Has cycle (circular chain): " + CycleDetector.hasCycle(n1));
    }
}

How to compile and run

BASH
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.LinkedListBankApp
TEXT
Expected output:
=== National Bank of India: Transaction History ===
Original order (3 transactions):
  TXN-1001 [SAV2001] 50000.00 INR
  TXN-1002 [CUR3001] 250000.00 INR
  TXN-1003 [SAV2002] 8000.00 INR

Reversed order (3 transactions):
  TXN-1003 [SAV2002] 8000.00 INR
  TXN-1002 [CUR3001] 250000.00 INR
  TXN-1001 [SAV2001] 50000.00 INR

Cycle detection:
  Has cycle (normal list): false
  Has cycle (circular chain): true

How do you reverse a linked list?

Reversing a singly linked list is a classic pointer manipulation problem. You iterate through the list, and for each node, you redirect its next pointer to the previous node. You need three pointers: prev, current, and nextTemp.

JAVA
package com.bank.core;

import java.math.BigDecimal;

public class ReverseLinkedListDemo {

    static class Node {
        String label;
        Node next;
        Node(String label) { this.label = label; }
    }

    static Node reverse(Node head) {
        Node prev = null;
        Node current = head;
        while (current != null) {
            Node nextTemp = current.next; // save next
            current.next = prev;          // reverse pointer
            prev = current;               // advance prev
            current = nextTemp;           // advance current
        }
        return prev; // new head
    }

    static void print(Node head) {
        var current = head;
        while (current != null) {
            System.out.print(current.label);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        var head = new Node("Deposit-SAV2001");
        head.next = new Node("Transfer-CUR3001");
        head.next.next = new Node("Withdrawal-SAV2002");

        System.out.println("Before reverse:");
        print(head);

        head = reverse(head);

        System.out.println("After reverse:");
        print(head);
    }
}
TEXT
Expected output:
Before reverse:
Deposit-SAV2001 -> Transfer-CUR3001 -> Withdrawal-SAV2002 -> null
After reverse:
Withdrawal-SAV2002 -> Transfer-CUR3001 -> Deposit-SAV2001 -> null

How does cycle detection work (Floyd's algorithm)?

Floyd's tortoise and hare algorithm uses two pointers that start at the head. The slow pointer moves one step at a time. The fast pointer moves two steps at a time. If there is a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle. If there is no cycle, the fast pointer reaches null.

In banking, a cycle in a payment chain means money is being routed in a loop (A pays B, B pays C, C pays A), which is a potential fraud signal.

JAVA
package com.bank.core;

public class FloydCycleDemo {

    static class PaymentNode {
        String from;
        String to;
        PaymentNode next;
        PaymentNode(String from, String to) { this.from = from; this.to = to; }
    }

    static boolean detectCycle(PaymentNode head) {
        PaymentNode slow = head;
        PaymentNode fast = head;
        int step = 0;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            step++;
            if (slow == fast) {
                System.out.println("  Cycle detected at step " + step + ": " + slow.from + " -> " + slow.to);
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        // No cycle
        var p1 = new PaymentNode("SAV2001", "CUR3001");
        var p2 = new PaymentNode("CUR3001", "SAV2002");
        p1.next = p2;
        System.out.println("Chain 1 (no cycle):");
        System.out.println("  Has cycle: " + detectCycle(p1));

        // Cycle: SAV2001 -> CUR3001 -> SAV2002 -> SAV2001 (fraud loop)
        var f1 = new PaymentNode("SAV2001", "CUR3001");
        var f2 = new PaymentNode("CUR3001", "SAV2002");
        var f3 = new PaymentNode("SAV2002", "SAV2001");
        f1.next = f2;
        f2.next = f3;
        f3.next = f1; // cycle
        System.out.println("Chain 2 (fraud loop):");
        System.out.println("  Has cycle: " + detectCycle(f1));
    }
}
TEXT
Expected output:
Chain 1 (no cycle):
  Has cycle: false
Chain 2 (fraud loop):
  Cycle detected at step 2: SAV2002 -> SAV2001
  Has cycle: true

What are common mistakes with linked lists?

The most common mistake is losing the reference to the rest of the list when inserting or deleting. If you change a pointer before saving the next node, you disconnect the chain.

Wrong: overwrite next before saving it

JAVA
package com.bank.core;

public class WrongPointerLoss {

    static class Node {
        String val;
        Node next;
        Node(String val) { this.val = val; }
    }

    public static void main(String[] args) {
        var head = new Node("A");
        head.next = new Node("B");
        head.next.next = new Node("C");

        // BUG: trying to insert X after A, but overwrite A.next first
        var x = new Node("X");
        head.next = x;          // Lost reference to B and C!
        x.next = head.next;     // x.next = x (points to itself)

        System.out.println("Wrong insertion result:");
        System.out.print("  " + head.val + " -> " + head.next.val);
        System.out.println(" -> " + head.next.next.val + " (infinite loop on X)");
    }
}
TEXT
Expected output:
Wrong insertion result:
  A -> X -> X (infinite loop on X)

Correct: save next before overwriting

JAVA
package com.bank.core;

public class CorrectPointerSave {

    static class Node {
        String val;
        Node next;
        Node(String val) { this.val = val; }
    }

    static void print(Node head) {
        var current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) System.out.print(" -> ");
            current = current.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        var head = new Node("A");
        head.next = new Node("B");
        head.next.next = new Node("C");

        // Correct: save next FIRST, then redirect
        var x = new Node("X");
        x.next = head.next;     // X.next -> B (save the chain first)
        head.next = x;          // A.next -> X

        System.out.println("Correct insertion result:");
        System.out.print("  ");
        print(head);
    }
}
TEXT
Expected output:
Correct insertion result:
  A -> X -> B -> C -> null

What about doubly linked lists?

A doubly linked list has two pointers per node: next and prev. This allows traversal in both directions and makes deletion of a known node O(1) because you can update both neighbors without traversing from the head.

Java's java.util.LinkedList is a doubly linked list. It implements both List and Deque interfaces.

JAVA
package com.bank.core;

import java.math.BigDecimal;
import java.util.LinkedList;

public class DoublyLinkedListDemo {
    public static void main(String[] args) {
        var transactions = new LinkedList<String>();

        // Deque operations: add at head and tail
        transactions.addFirst("SAV2001: Deposit 50000 INR");
        transactions.addLast("CUR3001: Transfer 120000 INR");
        transactions.addFirst("SAV2002: Opening balance 75000 INR");

        System.out.println("Doubly linked list (Deque operations):");
        for (var txn : transactions) {
            System.out.println("  " + txn);
        }

        // Traverse in reverse using descendingIterator
        System.out.println("Reverse order:");
        var descIter = transactions.descendingIterator();
        while (descIter.hasNext()) {
            System.out.println("  " + descIter.next());
        }

        System.out.println("First: " + transactions.getFirst());
        System.out.println("Last:  " + transactions.getLast());
        System.out.println("Size:  " + transactions.size());
    }
}
TEXT
Expected output:
Doubly linked list (Deque operations):
  SAV2002: Opening balance 75000 INR
  SAV2001: Deposit 50000 INR
  CUR3001: Transfer 120000 INR
Reverse order:
  CUR3001: Transfer 120000 INR
  SAV2001: Deposit 50000 INR
  SAV2002: Opening balance 75000 INR
First: SAV2002: Opening balance 75000 INR
Last:  CUR3001: Transfer 120000 INR
Size:  3

What should a senior or principal engineer know?

At the senior level, you should know that LinkedList is rarely the right choice in Java. ArrayList outperforms it for almost all practical workloads because of CPU cache locality. The scattered heap allocation of linked list nodes causes frequent cache misses.

At the principal level, consider:

  • Cache locality: ArrayList stores elements in a contiguous array, so CPU cache lines prefetch adjacent elements. LinkedList nodes are scattered across the heap.
  • Memory overhead: each LinkedList node has two extra references (next, prev), adding about 16 bytes per element on a 64-bit JVM.
  • ConcurrentLinkedQueue: for lock-free concurrent queues, use ConcurrentLinkedQueue or ConcurrentLinkedDeque.
  • Custom linked lists in DSA interviews: interviewers expect you to implement linked list operations from scratch (reverse, merge, detect cycle, find middle).
  • Sentinel nodes: use a dummy head node to simplify edge cases for insertion and deletion at the head.
JAVA
package com.bank.core;

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

public class SeniorLinkedListKnowledge {
    public static void main(String[] args) {
        int n = 1_000_000;
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // Measure sequential iteration (cache locality test)
        long start = System.nanoTime();
        long sum = 0;
        for (int val : arrayList) sum += val;
        long alIter = (System.nanoTime() - start) / 1_000_000;

        start = System.nanoTime();
        sum = 0;
        for (int val : linkedList) sum += val;
        long llIter = (System.nanoTime() - start) / 1_000_000;

        System.out.println("Senior/Principal linked list checklist:");
        System.out.println("  1. Prefer ArrayList for 99% of use cases");
        System.out.println("  2. LinkedList only for frequent head/tail add/remove");
        System.out.println("  3. Cache locality: ArrayList contiguous, LinkedList scattered");
        System.out.println("  4. LinkedList node overhead: ~16 extra bytes per element");
        System.out.println("  5. Use sentinel (dummy head) to simplify edge cases");
        System.out.println("\nIteration benchmark (1M elements):");
        System.out.println("  ArrayList:  " + alIter + " ms");
        System.out.println("  LinkedList: " + llIter + " ms");
        System.out.println("  ArrayList wins due to cache-friendly memory layout");
    }
}
TEXT
Expected output:
Senior/Principal linked list checklist:
  1. Prefer ArrayList for 99% of use cases
  2. LinkedList only for frequent head/tail add/remove
  3. Cache locality: ArrayList contiguous, LinkedList scattered
  4. LinkedList node overhead: ~16 extra bytes per element
  5. Use sentinel (dummy head) to simplify edge cases

Iteration benchmark (1M elements):
  ArrayList:  5 ms
  LinkedList: 12 ms
  ArrayList wins due to cache-friendly memory layout

What are common interview follow-up questions?

  • How do you find the middle node of a linked list? (Use two pointers: slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.)
  • How do you merge two sorted linked lists? (Compare the heads, pick the smaller one, and advance that list's pointer. Repeat until both are exhausted.)
  • How do you detect the start of a cycle? (After Floyd's algorithm finds the meeting point, reset one pointer to the head. Move both one step at a time. They meet at the cycle start.)
  • What is the difference between singly and doubly linked lists? (Doubly linked has a prev pointer, allowing O(1) deletion of a known node and reverse traversal.)
  • Can you implement an LRU cache using a linked list? (Yes. Use a doubly linked list with a HashMap. The list maintains access order. On access, move the node to the front. On eviction, remove from the tail.)
  • Why is LinkedList rarely used in production Java code? (ArrayList is faster for almost all workloads due to cache locality. LinkedList has higher memory overhead per element.)

Visual Overview

DIAGRAM
 Singly Linked List Structure
 =============================

  head
   │
   ▼
 ┌─────────────────┐     ┌─────────────────┐     ┌─────────────────┐
 │ SAV2001          │     │ CUR3001          │     │ SAV2002          │
 │ 50000 INR        │     │ 120000 INR       │     │ 8000 INR         │
 │ next ────────────┤────>│ next ────────────┤────>│ next = null      │
 └─────────────────┘     └─────────────────┘     └─────────────────┘


 Insert X Between A and B
 =========================

 Before:  A ──next──> B ──next──> C

 Step 1:  X.next = A.next (save chain)
          A ──next──> B ──next──> C
                      ▲
               X.next─┘

 Step 2:  A.next = X (redirect)
          A ──next──> X ──next──> B ──next──> C


 Reverse a Linked List
 ======================

 Step 0: null <- [prev]   A -> B -> C -> null
                          ^ [current]

 Step 1: null <- A   B -> C -> null
                     ^ [current]

 Step 2: null <- A <- B   C -> null
                          ^ [current]

 Step 3: null <- A <- B <- C
                           ^ [new head]

Key Takeaway

A linked list is a chain of nodes where each node holds a value and a reference to the next node. Unlike an array, linked list nodes are scattered in memory, connected only by pointers. Insertion and deletion at a known position take O(1) time because you only redirect pointers, but random access by index takes O(n) because you must walk from the head.

Pointer manipulation is the core skill for linked list problems. To insert a node, save the next pointer first, then redirect. To delete a node, point the previous node's next to the deleted node's next. To reverse the list, iterate through and flip each node's next pointer to point backward. Getting the pointer order wrong is the most common bug.

In our National Bank of India project, we built a transaction history as a singly linked list, reversed the order to show newest-first or oldest-first, and used Floyd's tortoise and hare algorithm to detect cycles in a payment chain. A cycle means money is looping between accounts, which is a fraud signal.

Java's LinkedList class is a doubly linked list that implements both List and Deque. Despite its flexibility, ArrayList outperforms LinkedList for nearly all real-world workloads because of CPU cache locality. LinkedList nodes are scattered across the heap, causing cache misses during iteration.

At the senior level, prefer ArrayList unless you have a proven need for constant-time head insertions or removals during iteration. In coding interviews, be prepared to implement linked list operations from scratch: reverse, detect cycles, find middle, merge two sorted lists.

Remember one sentence: a linked list trades O(1) random access for O(1) insert/delete at known positions, and in Java, ArrayList almost always wins because cache locality matters more than pointer manipulation speed.

---

Share
Use ← → arrow keys to navigate