Singly Linked List
Overview
A Singly Linked List is a linear data structure consisting of a sequence of nodes. Unlike an array where elements are stored in contiguous memory locations, linked list nodes can be scattered anywhere in memory. Each node contains two things: the data it holds, and a pointer (or reference) to the next node in the sequence.
The primary advantage of a linked list over an array is dynamic size and O(1) insertions/deletions at the head (or anywhere, provided you already have a reference to the specific node). In an array, inserting an element at the beginning requires shifting every single subsequent element to the right, which is an O(N) operation. In a linked list, you simply update a couple of pointers.
However, this comes at the cost of random access. You cannot instantly access the 5th element like you can in an array (arr[4]). To find the 5th element in a linked list, you must start at the head and traverse node by node (O(N) time complexity). Additionally, the pointers themselves consume extra memory overhead.
Syntax
Notice how insertAtHead requires zero data shifting. No matter how large the list gets, inserting at the front is always exactly two pointer assignments.
public class LinkedList {
// 1. Defining the Node class (usually a static inner class)
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
Node head; // Pointer to the first node
// 2. O(1) Insertion at the Head
public void insertAtHead(int data) {
Node newNode = new Node(data);
newNode.next = head; // Point new node to current head
head = newNode; // Make new node the new head
}
// 3. O(N) Traversal
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next; // Move to the next node
}
System.out.println("null");
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.printList(); // Output: 1 -> 2 -> 3 -> null
}
}Common Pitfalls
- Losing the
headpointer. When traversing a linked list, NEVER usehead = head.nextunless you are permanently deleting the head node. If you overwrite the head pointer, you lose reference to the beginning of the list, and the Garbage Collector will destroy your data. Always create a temporary pointer:Node current = head;. - NullPointerException on edge cases. When inserting or deleting, always ask yourself: 'What if the list is empty (
head == null)?' or 'What if I am deleting the very last node?'. Failing to handle the empty-list condition is the #1 cause of bugs in linked list code. - Forgetting to update the
nextpointer of the preceding node during deletion. To delete a node, you must have a reference to the node before it, so you can route itsnextpointer around the deleted node to the one after it.
Interview Questions
O(N). Because memory is not contiguous, there is no index-based math to find the middle. You must start at the head and traverse node-by-node until you reach the middle.
You need three pointers: prev (initially null), current (initially head), and nextTemp. In a loop, store current.next in nextTemp, change current.next to point to prev, then move prev and current one step forward. Return prev as the new head.
A Queue requires constant insertions at one end and deletions at the other. In an ArrayList, removing from the front (dequeue) requires shifting all remaining elements left, an O(N) operation. A Linked List can enqueue at the tail and dequeue at the head in strict O(1) time with no resizing overhead.
Real-World Example
Operating systems use linked lists to manage free memory blocks. When a program requests memory, the OS traverses a linked list of free blocks to find one large enough. When memory is freed, it is inserted back into the list. Linked lists are perfect here because insertions and deletions happen constantly and unpredictably.
// A simplified Free Memory Manager
class MemoryBlock {
int size;
int startAddress;
MemoryBlock next;
}
public class MemoryAllocator {
MemoryBlock freeListHead;
public void freeMemory(int size, int address) {
// O(1) insertion of newly freed memory back into the pool
MemoryBlock newFreeBlock = new MemoryBlock(size, address);
newFreeBlock.next = freeListHead;
freeListHead = newFreeBlock;
}
}Check Your Knowledge
Test your understanding of Singly Linked List with these quick questions.