Singly Linked List
Overview
A Singly Linked List is a linear data structure, but unlike an Array, its elements are not stored in contiguous memory locations. Instead, it consists of distinct objects called 'Nodes'. Each Node contains two things: the actual data (value), and a pointer (reference) to the *next* Node in the sequence. You use a Linked List when you need incredibly fast O(1) insertions or deletions at the beginning or middle of a list, because you don't have to shift any other elements—you just change a couple of pointers.
Syntax
The `head` is the only thing the Linked List class actually keeps track of. To find any other node, you must start at the `head` and follow the `next` pointers one by one until you reach the end (where `next` is null).
// 1. Define the building block: The Node
class Node {
int data;
Node next; // Pointer to the next node
public Node(int data) {
this.data = data;
this.next = null;
}
}
// 2. Define the List
public class LinkedList {
Node head; // The very first node
// O(1) Insertion at the front
public void insertAtHead(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
}Because elements are not indexed, searching for an element or accessing the Nth element takes O(N) linear time.
public void printList() {
Node current = head;
// Keep moving forward until we hit the end (null)
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next; // Move to the next node
}
System.out.println("null");
}Common Pitfalls
- Losing the `head` pointer. If you move `head = head.next` during traversal, you completely lose access to the first element and it gets garbage collected.
- NullPointerExceptions when checking `current.next.data` without first verifying that `current.next` is not null.
Interview Tips
- Emphasize that elements are not stored in contiguous memory. This means lookup is O(N), but insertion at the head is O(1).
Real-World Example
Singly Linked Lists are often used to implement Stacks, or to handle hash collisions in HashMaps (Chaining).
public class HashMapChaining {
// An array of Linked List Nodes to handle collisions
Node[] buckets = new Node[16];
public void put(int key, String value) {
int index = key % 16;
Node newNode = new Node(key, value);
// Insert at the head of the linked list for this bucket
newNode.next = buckets[index];
buckets[index] = newNode;
}
}