Singly Linked List

A singly linked list is the simplest form of linked list where each node contains data and a single pointer to the next node. Unlike arrays, which store elements in contiguous memory, linked list nodes can reside anywhere in memory — each node simply holds a reference to the next. This makes insertions and deletions at the head O(1), but it also means there is no random access: to reach a particular node, you must always start from the beginning and follow pointers. Singly linked lists are the foundation for understanding more complex structures like doubly linked lists, stacks, and queues.

Structure#

In a singly linked list, we maintain a head pointer that references the first node. Each node holds two pieces of information: its data (the value stored) and a next pointer (a reference to the following node). The last node's next points to null, marking the end of the list. The head is our only entry point — without it, we have no way to locate any node. Losing the head reference means losing access to the entire list.

Traversal#

Traversing a linked list means visiting each node one by one, starting from the head and following next pointers until null is reached. Unlike arrays, linked lists do not support index-based access — you cannot jump directly to the third element. Instead, you must walk the chain. Traversal underpins almost every other operation: searching, printing, counting, and deletion all require visiting nodes in sequence.

Insertion#

Insertion can happen at three positions: beginning (head), end (tail), or at a specific index. Each case involves the same fundamental steps — create a new node, wire its next pointer, and update the surrounding pointers — but the efficiency and the node you need to locate first differ significantly between them.

Insert at Head#

Inserting at the head is the most efficient operation — O(1) time.

Insert at Tail#

Inserting at the tail requires traversing to the end first — O(n) time. Because we only hold a reference to the head, the only way to reach the last node is to follow the chain of next pointers until we find a node whose next is null. That final node is where we attach the new one.

Insert at Position#

To insert at a specific index, we traverse to the node just before that position — the node at index position - 1. Once we have that predecessor node, we wire in the new node by updating two pointers in the correct order: first point the new node to the predecessor's current next, then redirect the predecessor's next to the new node. Reversing this order would lose the reference to the rest of the list.

Deletion#

Deletion also has three cases: from head, from tail, or from a specific position. In all non-head cases, the core idea is the same: find the node before the target, then update its next pointer to skip over the target. The target node becomes unreachable and will be reclaimed by garbage collection in managed languages like Python and JavaScript.

Delete at Head#

Delete at Tail#

Deleting at the tail requires traversing to the second-to-last node — O(n) time. We need the second-to-last node (the predecessor of the tail) so we can set its next to null, effectively disconnecting the last node. There is no shortcut: because each node only has a forward pointer, there is no way to navigate backward from the tail to its predecessor.

Delete at Position#

Search#

Finding an element in a linked list requires linear traversal — O(n) in the worst case. Unlike arrays, there is no index to jump to directly, and unlike sorted arrays, there is no way to use binary search because linked lists have no random access. The only option is to walk from the head, checking each node's data until a match is found or the list is exhausted.

Common Patterns#

Reverse Linked List#

Reversing a linked list is a classic interview question. The iterative approach uses three pointers: prev (the already-reversed portion), current (the node being processed), and a temporary next variable (to preserve the rest of the list). All three are necessary because the moment we redirect current.next to point backward, we lose our only reference to the remaining forward list — unless we saved it first in next.

Find Middle Node#

Use the fast and slow pointer technique (also called the tortoise and hare). The intuition is straightforward: if the fast pointer moves two steps for every one step of the slow pointer, then by the time the fast pointer reaches the end of the list, the slow pointer will have traveled exactly half the distance — landing at the middle. This solves the problem in a single pass without needing to know the list length in advance.

Detect Cycle#

Floyd's Cycle Detection algorithm uses fast and slow pointers to detect if a linked list has a cycle. The key insight: if no cycle exists, the fast pointer will eventually reach null and the loop terminates. If a cycle does exist, both pointers are trapped inside it — and because the fast pointer gains one step on the slow pointer each iteration, it will eventually lap the slow pointer and they will meet at the same node. Their meeting is our proof of a cycle.

Complexity Summary#

Reviewing AI-Generated Code#

Understanding singly linked lists helps you evaluate AI-generated solutions:

What to Verify#

Common AI Pitfalls#

Questions to Ask AI#

When AI generates linked list code, verify:

• "What happens with an empty list?"
• "What happens with a single-node list?"
• "Are pointers updated in the correct order?"
• "Is the size being tracked correctly?"
• "Is the reference to the rest of the list saved before any pointer is redirected?"

Summary#

Singly linked lists are the foundation for more advanced data structures and algorithms. The patterns practiced here — sequential traversal, careful pointer manipulation, and two-pointer techniques — appear throughout doubly linked lists, stacks, queues, and graph traversal. Take time to internalize these fundamentals before moving on to doubly and circular linked lists.