Definition
- Node – the building block; each node stores a piece of data and a
nextreference pointing to the following node in the chain. - Head – a reference to the first node in the list; this is the only entry point for traversal.
- Tail – the last node whose
nextreference isnull, signaling the end of the chain. - Non-contiguous storage – unlike an array, nodes live anywhere on the heap and are connected only by their
nextpointers. - Singly vs doubly – a singly linked list has only a
nextpointer; a doubly linked list adds aprevpointer for backward traversal.
Imagine the National Bank of India keeps a chain of pending loan applications for Rajesh. Each application slip has the loan details plus an arrow pointing to the next slip. The slips are scattered in different drawers across the office, but each one tells the clerk exactly where the next one is. The clerk starts from the first slip (the head) and follows arrows until a slip's arrow points to nothing, which marks the end of the pending queue.
Understanding the Concepts
What is a linked list?
A linked list is a linear data structure made of nodes. Each node is a small object with two parts: the data it carries and a next reference to the following node. The list itself usually holds only a head reference that points to the first node. To reach any node you start at the head and follow next references one by one. The final node's next is null, which signals the end of the chain.
In a banking system, you can think of each node as a pending loan application. Rajesh submits five loan applications, and each application points to the next one in the queue.
package com.bank.model;
import java.math.BigDecimal;
public class LoanApplicationNode {
String applicationId;
BigDecimal loanAmount;
LoanApplicationNode next;
public LoanApplicationNode(String applicationId, BigDecimal loanAmount) {
this.applicationId = applicationId;
this.loanAmount = loanAmount;
this.next = null;
}
}
How is a linked list different from an array?
The defining contrast is memory layout. An array stores elements in one continuous block, so element i is found instantly by computing an address offset, giving O(1) random access. A linked list stores nodes anywhere on the heap, so to reach the fifth node you must walk through the first four, giving O(n) access.
The trade-off is that inserting or deleting at the front of a linked list is O(1) because you just re-point a reference, whereas inserting at the front of an array is O(n) because every element must shift right.
| Feature | Array | Linked List |
|---|---|---|
| Memory layout | Contiguous block | Scattered on heap |
| Access by index | O(1) | O(n) |
| Insert at head | O(n) shift | O(1) re-point |
| Insert at tail | O(1) amortized | O(n) walk or O(1) with tail ref |
| Cache locality | Excellent | Poor |
| Memory overhead | None per element | One pointer per node |
package com.bank.core;
import java.math.BigDecimal;
import com.bank.model.LoanApplicationNode;
public class LinkedListVsArray {
public static void main(String[] args) {
// Array: O(1) access by index
BigDecimal[] amounts = {new BigDecimal("50000"), new BigDecimal("100000")};
System.out.println("Array index 1: " + amounts[1]);
// Linked list: must walk from head
LoanApplicationNode head = new LoanApplicationNode("LOAN-001", new BigDecimal("50000"));
head.next = new LoanApplicationNode("LOAN-002", new BigDecimal("100000"));
LoanApplicationNode current = head;
current = current.next; // walk one step to reach second node
System.out.println("Linked list node 2: " + current.loanAmount);
}
}
Array index 1: 100000
Linked list node 2: 100000
How do you build a simple singly linked list?
You create a node class and a list class that holds the head reference. The list provides methods to add nodes at the head, at the tail, and to print the chain.
package com.bank.core;
import java.math.BigDecimal;
public class LoanApplicationList {
private LoanApplicationNode head;
private int size;
public void addFirst(String id, BigDecimal amount) {
LoanApplicationNode node = new LoanApplicationNode(id, amount);
node.next = head;
head = node;
size++;
}
public void addLast(String id, BigDecimal amount) {
LoanApplicationNode node = new LoanApplicationNode(id, amount);
if (head == null) {
head = node;
} else {
LoanApplicationNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
size++;
}
public void printAll() {
LoanApplicationNode current = head;
while (current != null) {
System.out.println(current.applicationId + " : " + current.loanAmount);
current = current.next;
}
}
public static void main(String[] args) {
LoanApplicationList list = new LoanApplicationList();
list.addLast("LOAN-001", new BigDecimal("50000"));
list.addLast("LOAN-002", new BigDecimal("200000"));
list.addFirst("LOAN-003", new BigDecimal("75000"));
list.printAll();
}
}
LOAN-003 : 75000
LOAN-001 : 50000
LOAN-002 : 200000
What is a doubly linked list?
A doubly linked list adds a prev pointer to each node so you can traverse in both directions. Java's java.util.LinkedList is actually a doubly linked list internally. The trade-off is that each node uses more memory for the extra pointer, but you gain the ability to remove a node in O(1) when you already have a reference to it, because you can reach both neighbors.
package com.bank.model;
import java.math.BigDecimal;
public class DoublyLinkedLoanNode {
String applicationId;
BigDecimal loanAmount;
DoublyLinkedLoanNode prev;
DoublyLinkedLoanNode next;
public DoublyLinkedLoanNode(String applicationId, BigDecimal loanAmount) {
this.applicationId = applicationId;
this.loanAmount = loanAmount;
}
}
package com.bank.core;
import com.bank.model.DoublyLinkedLoanNode;
import java.math.BigDecimal;
public class DoublyLinkedDemo {
public static void main(String[] args) {
DoublyLinkedLoanNode a = new DoublyLinkedLoanNode("LOAN-001", new BigDecimal("50000"));
DoublyLinkedLoanNode b = new DoublyLinkedLoanNode("LOAN-002", new BigDecimal("100000"));
DoublyLinkedLoanNode c = new DoublyLinkedLoanNode("LOAN-003", new BigDecimal("200000"));
a.next = b; b.prev = a;
b.next = c; c.prev = b;
// Traverse forward
System.out.println("Forward:");
DoublyLinkedLoanNode current = a;
while (current != null) {
System.out.println(" " + current.applicationId);
current = current.next;
}
// Traverse backward from last node
System.out.println("Backward:");
current = c;
while (current != null) {
System.out.println(" " + current.applicationId);
current = current.prev;
}
}
}
Forward:
LOAN-001
LOAN-002
LOAN-003
Backward:
LOAN-003
LOAN-002
LOAN-001
What about cache locality and performance?
Linked lists have poor cache locality because nodes are scattered across the heap. Modern CPUs load memory in cache lines, so accessing contiguous array elements is fast because neighboring elements are already in the cache. With a linked list, each next dereference can jump to a completely different memory region, causing a cache miss.
For pure iteration, an ArrayList is usually faster than a LinkedList in practice despite the same O(n) big-O, because of this cache behavior. Use a linked list when you need frequent O(1) insertions and deletions at known positions, not when you need fast sequential reads.
package com.bank.core;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class CacheLocalityDemo {
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);
}
long start = System.nanoTime();
long sum1 = 0;
for (int val : arrayList) sum1 += val;
long arrayTime = System.nanoTime() - start;
start = System.nanoTime();
long sum2 = 0;
for (int val : linkedList) sum2 += 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");
}
}
ArrayList iteration: 5 ms
LinkedList iteration: 12 ms
What are common mistakes with linked lists?
The most common mistake is losing the head reference. If you reassign head during a traversal instead of using a separate current pointer, you lose access to the beginning of the list permanently.
// WRONG: moves head itself, losing the start of the list
while (head != null) {
System.out.println(head.applicationId);
head = head.next; // head is now lost!
}
// After this loop, head is null and the list is unreachable
// CORRECT: uses a separate pointer, head stays intact
LoanApplicationNode current = head;
while (current != null) {
System.out.println(current.applicationId);
current = current.next;
}
// head still points to the first node
Another common mistake is forgetting to handle the empty list case. When head is null, calling head.next throws a NullPointerException.
// WRONG: crashes on empty list
public BigDecimal getFirstAmount() {
return head.loanAmount; // NullPointerException if head is null
}
// CORRECT: guard against null head
public BigDecimal getFirstAmount() {
if (head == null) {
throw new IllegalStateException("No pending loan applications");
}
return head.loanAmount;
}
When should you use a linked list?
Use a linked list when you need frequent insertions and deletions at the front or at known positions in constant time. Queues and deques are natural fits. Do not use a linked list when you need fast random access by index or when you iterate sequentially over large datasets, because an array or ArrayList will outperform it due to cache locality.
In banking, a linked list works well for a pending-transaction queue where new transactions arrive at the front, processed transactions are removed from the front, and you rarely need to jump to the middle.
package com.bank.service;
import java.math.BigDecimal;
import com.bank.model.LoanApplicationNode;
public class PendingLoanQueue {
private LoanApplicationNode head;
public void enqueue(String id, BigDecimal amount) {
LoanApplicationNode node = new LoanApplicationNode(id, amount);
node.next = head;
head = node; // O(1) insert at front
}
public LoanApplicationNode dequeue() {
if (head == null) return null;
LoanApplicationNode removed = head;
head = head.next; // O(1) remove from front
removed.next = null;
return removed;
}
}
What should a senior engineer know?
A senior engineer should understand that java.util.LinkedList implements both List and Deque interfaces, making it usable as a list, a queue, or a double-ended queue. However, in almost all practical situations, ArrayList is preferred for List operations because of cache locality.
The real power of linked list knowledge is in coding interviews and in understanding the internals of data structures like LinkedHashMap, ConcurrentLinkedQueue, and skip lists. Knowing how to reverse a list, detect a cycle, merge sorted lists, and find the middle node with the fast-slow pointer technique are the core interview skills.
package com.bank.core;
import java.util.LinkedList;
import java.util.Deque;
public class JavaLinkedListDemo {
public static void main(String[] args) {
// java.util.LinkedList as a Deque
Deque<String> approvalQueue = new LinkedList<>();
approvalQueue.offerLast("LOAN-001");
approvalQueue.offerLast("LOAN-002");
approvalQueue.offerFirst("LOAN-PRIORITY"); // priority insert at front
System.out.println("Process: " + approvalQueue.pollFirst()); // LOAN-PRIORITY
System.out.println("Process: " + approvalQueue.pollFirst()); // LOAN-001
System.out.println("Process: " + approvalQueue.pollFirst()); // LOAN-002
}
}
Process: LOAN-PRIORITY
Process: LOAN-001
Process: LOAN-002
What are common interview follow-up questions?
Interviewers often follow up "What is a linked list?" with these questions:
- How do you reverse a singly linked list in place?
- How do you detect a cycle using Floyd's slow-fast pointer?
- How do you find the middle node in one pass?
- How do you merge two sorted linked lists?
- What is the difference between
ArrayListandLinkedListin Java? - When would you choose a linked list over an array in production?
Visual Overview
Singly Linked List
┌──────────┐ ┌──────────┐ ┌──────────┐
│ LOAN-001 │───>│ LOAN-002 │───>│ LOAN-003 │───> null
│ 50,000 │ │ 100,000 │ │ 200,000 │
└──────────┘ └──────────┘ └──────────┘
▲
│
head
Doubly Linked List
┌──────────┐ ┌──────────┐ ┌──────────┐
null <─│ LOAN-001 │<──>│ LOAN-002 │<──>│ LOAN-003 │─> null
│ 50,000 │ │ 100,000 │ │ 200,000 │
└──────────┘ └──────────┘ └──────────┘
▲ ▲
│ │
head tail
Node Structure ┌───────────────────────┐ │ Node │ │ ┌─────────────────┐ │ │ │ data (payload) │ │ │ └─────────────────┘ │ │ ┌─────────────────┐ │ │ │ next (pointer) ─┼──┼──> next Node or null │ └─────────────────┘ │ └───────────────────────┘
Key Takeaway
A linked list is one of the most fundamental data structures in computer science. It is a chain of nodes where each node holds a piece of data and a reference to the next node. Unlike an array, the nodes are not stored side by side in memory. They can live anywhere on the heap, and the only thing connecting them is the next pointer inside each node. You access the list through a head reference that points to the first node, and you reach any other node by walking the chain one step at a time.
The key trade-off between a linked list and an array is access versus modification. An array gives you O(1) random access by index because elements sit in a contiguous block, but inserting at the front costs O(n) because every element must shift. A linked list gives you O(1) insertion and deletion at the head because you only re-point a reference, but reaching the fifth node means walking through the first four, so access is O(n). A doubly linked list adds a prev pointer so you can traverse backwards, which is how Java's java.util.LinkedList is implemented internally.
In practice, linked lists have poor cache locality because the nodes are scattered across memory, so for pure sequential iteration an ArrayList is faster even though the big-O is the same. The real value of understanding linked lists lies in coding interviews, where reversal, cycle detection, merging, and fast-slow pointer problems are staples, and in understanding the internals of structures like LinkedHashMap and ConcurrentLinkedQueue.
In our banking system at National Bank of India, we use a linked list to model Rajesh's pending loan application queue. New applications arrive at the front in constant time, and processed applications are removed from the front in constant time. We rarely need random access into the middle of the queue, so the linked list is a natural fit.
Remember one sentence: a linked list is a chain of heap-scattered nodes connected by next pointers, trading O(1) random access for O(1) head insertion.
---