Definition
- Traversal count – walk from
headtonull, incrementing a counter for each node; O(n) time, O(1) space. - Maintained size – keep an integer
sizefield on the list object that increments onaddand decrements onremove; O(1) to read. - Trade-off – traversal count is always accurate but slow; maintained size is fast but requires every mutation path to update the field correctly.
- Java standard –
java.util.LinkedListinternally maintains asizefield sosize()returns in constant time.
National Bank of India wants to know how many pending loan applications Rajesh currently has in his queue. A clerk can either start at the first slip and count one by one until the chain ends, or the front desk can maintain a tally board that gets incremented every time a new application arrives and decremented every time one is processed. The tally board is faster to read, but someone must remember to update it on every change.
Understanding the Concepts
What is the length of a linked list?
The length of a linked list is the number of nodes it contains. Since a linked list does not store its size as a property by default, you typically compute it by traversing the entire chain and counting each node.
package com.bank.model;
import java.math.BigDecimal;
public class LoanNode {
String loanId;
BigDecimal amount;
LoanNode next;
public LoanNode(String loanId, BigDecimal amount) {
this.loanId = loanId;
this.amount = amount;
this.next = null;
}
}
How do you count nodes by traversal?
Set a counter to zero and a current pointer to the head. While current is not null, increment the counter and advance to the next node. When the loop ends, the counter holds the length.
package com.bank.service;
import com.bank.model.LoanNode;
import java.math.BigDecimal;
public class LoanListLength {
public static int countNodes(LoanNode head) {
int count = 0;
LoanNode current = head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public static void main(String[] args) {
LoanNode head = new LoanNode("LOAN-001", new BigDecimal("50000"));
head.next = new LoanNode("LOAN-002", new BigDecimal("100000"));
head.next.next = new LoanNode("LOAN-003", new BigDecimal("200000"));
System.out.println("Number of pending loans: " + countNodes(head));
}
}
Number of pending loans: 3
How do you maintain a size field for O(1) length?
Instead of counting every time, you can store a size field in the list object and update it on every mutation. This is how java.util.LinkedList works internally.
package com.bank.service;
import com.bank.model.LoanNode;
import java.math.BigDecimal;
public class LoanLinkedList {
private LoanNode head;
private int size;
public LoanLinkedList() {
this.head = null;
this.size = 0;
}
public void addFirst(String loanId, BigDecimal amount) {
LoanNode node = new LoanNode(loanId, amount);
node.next = head;
head = node;
size++; // must update on every add
}
public LoanNode removeFirst() {
if (head == null) return null;
LoanNode removed = head;
head = head.next;
removed.next = null;
size--; // must update on every remove
return removed;
}
public int getSize() {
return size; // O(1)
}
public static void main(String[] args) {
LoanLinkedList list = new LoanLinkedList();
list.addFirst("LOAN-001", new BigDecimal("50000"));
list.addFirst("LOAN-002", new BigDecimal("100000"));
list.addFirst("LOAN-003", new BigDecimal("200000"));
System.out.println("Size (O(1)): " + list.getSize());
list.removeFirst();
System.out.println("After remove: " + list.getSize());
}
}
Size (O(1)): 3
After remove: 2
How is traversal count different from maintained size?
| Feature | Traversal Count | Maintained Size |
|---|---|---|
| Time to read length | O(n) | O(1) |
| Extra storage | None | One int field |
| Accuracy guarantee | Always correct | Correct only if every mutation updates it |
| Code complexity | Simple one-time scan | Every add/remove must update the field |
| Use case | Rare length checks | Frequent length checks |
// Traversal count: always accurate, always O(n)
int count = 0;
LoanNode current = head;
while (current != null) { count++; current = current.next; }
// Maintained size: O(1) but requires discipline
int size = list.getSize(); // instant
What happens if the maintained size drifts out of sync?
If you forget to update the size field in any mutation path, the count silently drifts. In a financial system this is a serious bug because reports that depend on the count will show wrong numbers.
// BUG: forgot to decrement size on remove
public LoanNode removeFirstBuggy() {
if (head == null) return null;
LoanNode removed = head;
head = head.next;
removed.next = null;
// size-- is missing!
return removed;
}
// CORRECT: always update size on every mutation
public LoanNode removeFirstCorrect() {
if (head == null) return null;
LoanNode removed = head;
head = head.next;
removed.next = null;
size--;
return removed;
}
Can you count nodes recursively?
Yes, but iterative is preferred for production because the recursive version uses O(n) stack frames and risks StackOverflowError on long lists.
package com.bank.service;
import com.bank.model.LoanNode;
import java.math.BigDecimal;
public class RecursiveCount {
public static int countRecursive(LoanNode node) {
if (node == null) return 0;
return 1 + countRecursive(node.next);
}
public static void main(String[] args) {
LoanNode head = new LoanNode("LOAN-001", new BigDecimal("50000"));
head.next = new LoanNode("LOAN-002", new BigDecimal("100000"));
head.next.next = new LoanNode("LOAN-003", new BigDecimal("200000"));
System.out.println("Recursive count: " + countRecursive(head));
}
}
Recursive count: 3
What are the edge cases?
The empty list and single-node list are the primary edge cases. The traversal count handles both naturally because the loop either never runs (empty) or runs exactly once (single node).
package com.bank.service;
import com.bank.model.LoanNode;
import java.math.BigDecimal;
public class CountEdgeCases {
public static int count(LoanNode head) {
int c = 0;
LoanNode cur = head;
while (cur != null) { c++; cur = cur.next; }
return c;
}
public static void main(String[] args) {
System.out.println("Empty: " + count(null));
System.out.println("Single: " + count(new LoanNode("L-1", new BigDecimal("1000"))));
}
}
Empty: 0
Single: 1
How can you audit the maintained size?
In production, you can use the traversal count as an audit tool to verify that the maintained size field has not drifted. Run a periodic check that compares the two values.
package com.bank.service;
import com.bank.model.LoanNode;
public class SizeAuditor {
public static boolean auditSize(LoanNode head, int maintainedSize) {
int actualCount = 0;
LoanNode current = head;
while (current != null) {
actualCount++;
current = current.next;
}
if (actualCount != maintainedSize) {
System.out.println("DRIFT DETECTED: maintained=" + maintainedSize
+ " actual=" + actualCount);
return false;
}
return true;
}
}
What should a senior engineer know?
A senior engineer knows that java.util.LinkedList.size() is O(1) because it maintains a count internally. When building a custom linked list for a specific use case, the choice between traversal count and maintained size depends on how often the length is queried versus how many mutation paths exist. More mutation paths mean more places where a forgotten update could cause drift.
In concurrent environments, a maintained size must be updated atomically along with the structural change, or a race condition could make the count incorrect. Using AtomicInteger or synchronization is necessary in multithreaded code.
import java.util.concurrent.atomic.AtomicInteger;
public class ThreadSafeLoanList {
private volatile LoanNode head;
private final AtomicInteger size = new AtomicInteger(0);
public synchronized void addFirst(String id, java.math.BigDecimal amount) {
LoanNode node = new LoanNode(id, amount);
node.next = head;
head = node;
size.incrementAndGet();
}
public int getSize() {
return size.get();
}
}
Visual Overview
Traversal Count
head
│
▼
[LOAN-001] ──> [LOAN-002] ──> [LOAN-003] ──> null
count=1 count=2 count=3 loop ends
return 3
Maintained Size Field ┌─────────────────────────────┐ │ LoanLinkedList │ │ head ──> [LOAN-001] ──>...│ │ size = 3 │ │ │ │ addFirst() → size++ │ │ removeFirst() → size-- │ │ getSize() → return size │ └─────────────────────────────┘
Key Takeaway
Finding the length of a linked list means counting how many nodes it contains. The most straightforward approach is the traversal count: set a counter to zero, walk from head to null, and increment for each node. This is O(n) time and O(1) space, and it is always correct because it physically visits every node.
The faster alternative is to maintain a size field on the list object. You increment it every time you add a node and decrement it every time you remove one. Reading the length then becomes O(1), just returning the field. This is exactly how java.util.LinkedList reports its size instantly.
The trade-off is discipline. If you maintain a size field, every single code path that adds or removes a node must update that field. If even one path forgets, the count silently drifts out of sync with the actual structure. In a financial system at National Bank of India, that kind of drift is a serious bug. We keep a traversal-based count available in our audit tools so we can periodically verify that the maintained size still matches the real number of pending loan applications.
The choice between the two approaches comes down to how often you need the length versus how many mutation paths exist. If length is rarely needed, the O(n) walk is simpler and avoids bookkeeping bugs. If length is displayed on every screen refresh, maintaining a size field is worth the extra discipline.
Remember one sentence: count by traversal is always correct in O(n), or maintain a size field for O(1) but update it on every mutation.
---