Back to Study Material Data Structures and Algorithms

Singly Linked List

A singly linked list is the most basic form of linked list. Every node holds a value and a single next pointer that points to the next node in the sequence...

Singly Linked List

The Simplest Linked Structure with One-Way Pointer Chains

A singly linked list is the most basic form of linked list. Every node holds a value and a single next pointer that points to the next node in the sequence. The list is accessed through a head pointer that points to the first node. Traversal proceeds forward only: you start at head and follow next pointers until reaching a node whose next is null.

Core operations and their complexities: accessing the k-th element requires traversing k nodes, so it is O(k), and O(n) in the worst case. Searching for a value requires scanning the entire list in the worst case, O(n). Inserting at the head is O(1): create a new node, set its next to the current head, and update head to the new node. Inserting at the tail requires traversing to the end, O(n), unless you maintain a separate tail pointer that makes it O(1). Deleting the head is O(1). Deleting an arbitrary node by value requires first finding the node's predecessor, O(n), and then adjusting the pointer, O(1).

Traversal with a pointer variable: set current equal to head, then while current is not null, process current.data and advance current to current.next. Be careful not to dereference current.next before confirming current is not null, as this causes a null pointer exception.

A common technique is the dummy head node, also called a sentinel. Adding a dummy node before the actual first element simplifies edge cases: inserting or deleting the first real element uses the same code as operating on middle elements, because the dummy node always serves as the predecessor. This reduces the number of special cases and makes the code cleaner and less error-prone.

Singly linked lists are used to implement stacks (where push and pop both operate at the head) and queues (where enqueue adds to the tail and dequeue removes from the head, with the tail pointer making both O(1)).

Finding the middle of a singly linked list efficiently uses the two-pointer technique: a slow pointer moves one step at a time while a fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer is at the middle. This is O(n) with O(1) space and avoids computing the length first.

Worked example: given a singly linked list, determine whether it is a palindrome. Step 1: find the middle using slow/fast pointers. Step 2: reverse the second half in-place. Step 3: compare the first half with the reversed second half node by node. Step 4 (optional): restore the list. Total time O(n), space O(1).

Interview tip: always clarify whether the list has a tail pointer before designing your algorithm. Its presence or absence changes the complexity of tail operations from O(n) to O(1).