CS Core & Software Engineering · Data Structures & Algorithms

Linked Lists

Singly and doubly linked lists, pointer manipulation, reversal and cycle detection.

Eight concepts on singly and doubly linked lists — pointer structure, why index access is linear, sentinel heads, iterative reversal, Floyd cycle detection, the middle-node trick, and when two pointers per node pay off.

CS Core & Software Engineering
Medium level
8 concepts
5 practice questions

1Nodes and next pointers

A singly linked list is a chain of nodes. Each node holds a value and one pointer to the next node; the last node's next is null. Nodes need not sit in contiguous memory, so there is no address arithmetic from an index — you reach a position only by starting at the head and following next, one link at a time.

Figure. Four nodes in a singly linked chain. Edges are next pointers; the last node has next null.

How a walk works

Hold the headThe list is identified by a pointer to the first node; lose that and the chain is unreachable.
Follow nextFrom the current node, read its next field to step one link forward.
Stop at nullWhen next is null you have left the last node; there is no wrap-around unless the list was built with a cycle.

In a singly linked list of n nodes, why is reading the element at index k not O(1)?

Because values are encrypted until you decrypt each node
Because nodes are not in one contiguous block, so you must follow next from the head k times
Because every read also updates the previous pointer

There is no base+k address formula. Contiguity is what arrays use for O(1) index access; a list only offers a next chain from the head.

2Access is linear; splice is constant

Search or access by position costs O(n) because you traverse from the head. Once you already hold a pointer to the node before the splice point, inserting or deleting the next node is constant time: rewire one or two next fields, with no shifting of the rest of the list. That trade — slow index, fast local edit — is the whole point of choosing a list over an array.

On the Nodes and next pointers chain: walking k steps is O(k); once you hold the predecessor, rewiring next for insert or delete is O(1) with no element shift.

Insert after a known node

Have the predecessorCall it p. The new node will sit between p and p.next.
Wire forwardSet new.next = p.next, then p.next = new. Two pointer writes; the rest of the list is untouched.
Do not count the walk twiceIf you still have to find p from the head, that walk is O(n) and dominates; the splice itself stays O(1).

List costs when the relevant pointer is already known
Operation	Cost	Why
Access / search by position or value	O(n)	Must walk from the head
Insert after a known node	O(1)	Rewire next; no shift
Delete the successor of a known node	O(1)	Rewire next; no shift
Insert at head (pointer to head known)	O(1)	New node points at old head

You already have a pointer to node p in a singly linked list. Inserting a new node immediately after p is

O(n), because every later node must shift right in memory
O(1), because you only rewire next pointers
O(\log n), because lists are always balanced trees underneath

Lists do not shift elements. With p in hand, two next assignments splice the new node in. Shifting is the array cost this structure avoids.

3Dummy (sentinel) head

A dummy or sentinel node sits before the real head and is never part of the logical list. Algorithms that insert or delete at the front treat the first real node like any other successor of the sentinel, so the empty-list and single-node edge cases stop needing separate branches. When the routine finishes, the real head is dummy.next.

Figure. Sentinel before the logical list. Algorithms return dummy.next as the real head.

How a sentinel simplifies a delete

Attach dummyCreate a node whose next is the current head. Work with a pointer walking from dummy, not from head.
Uniform deleteTo remove the first real node, set dummy.next = head.next — the same pattern as deleting any later successor.
Return the real headReturn dummy.next. If the list became empty, that value is null without a special case.

Why does a dummy head help when deleting the first node of a singly linked list?

It stores a second copy of every value so deletes never lose data
The first real node becomes an ordinary successor of the sentinel, so the same rewiring code covers head and middle deletes
It makes index access O(1) by sitting at a fixed memory address

Without a sentinel, deleting the head must update the caller's head pointer as a special case. With dummy.next as the real head, every delete is "rewire the predecessor," including the first real node.

4Iterative three-pointer reversal

To reverse a singly linked list in place, walk with three pointers — prev, curr, and next — flipping each node's next to its predecessor. The walk is O(n) time and O(1) extra space. Recursion can reverse too, but it spends a stack frame per node; interviews prefer the iterative form for that reason.

Figure. Same four values after reversal: next edges run right-to-left toward the old head.

One node at a time

Seedprev = null, curr = head.
Save and flipnext = curr.next, then curr.next = prev.
Advanceprev = curr, curr = next. Repeat until curr is null.
New headReturn prev — the last node visited, which is the old tail.

Reverse, iterative

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Reverse 1 → 2 → 3 → 4 → 5

Given the singly linked list 1 → 2 → 3 → 4 → 5 → null, return the reversed list 5 → 4 → 3 → 2 → 1 → null.

start: prev, currnull, 1
flip 1.next → null; advanceprev=1, curr=2
flip 2.next → 1; advanceprev=2, curr=3
flip 3, then 4, then 5prev=5, curr=null
return prev5 → 4 → 3 → 2 → 1

Pro tip. Save next before you overwrite curr.next. If you flip first without saving, the rest of the list is unreachable and the walk dies after one node.

Coding lab. Reverse 1-2-3-4-5 runs in the app, with checks on your output.

After a correct iterative reversal of a non-empty list, which pointer is the new head?

The original head, unchanged
prev at exit — the last node that was current
curr at exit — which is always still the original head

The loop ends when curr becomes null. prev then holds the old tail, which is the new head. Returning the original head would leave you at the new tail.

5Floyd cycle detection

Floyd's tortoise-and-hare detects a cycle with two pointers and O(1) extra space: slow advances one step, fast advances two. If there is no cycle, fast hits null. If there is a cycle, fast laps slow inside the loop and they meet. A visited set also works but spends linear memory — the interview ask is usually the constant-space version.

Figure. Same list as the ledger. The return edge from 5 to 3 is the cycle; Floyd's pointers meet on the loop.

How the meeting proves a cycle

Start togetherslow = fast = head.
Different stridesEach iteration: slow = slow.next, fast = fast.next.next (stop if fast or fast.next is null).
Meet or finishEqual pointers mean a cycle. Fast reaching null means an acyclic list.

Has cycle?

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Meet inside 1 → 2 → 3 → 4 → 5 → 3

List 1 → 2 → 3 → 4 → 5 with 5.next = 3. Do slow (1 step) and fast (2 steps) meet?

startslow=1, fast=1
step 1slow=2, fast=3
step 2slow=3, fast=5
step 3 (fast: 5 → 3 → 4)slow=4, fast=4 — meet

Pro tip. To find where the cycle begins after a meeting, reset one pointer to head and advance both one step at a time; their next meeting is the cycle entrance.

Floyd's algorithm uses O(1) extra space. What would a hash-set cycle check use instead?

O(1) space and O(1) time
O(n) space to remember visited nodes
O(n^2) space for an adjacency matrix of the list

Storing every seen node needs linear memory. Floyd trades that memory for two pointers and a meeting argument inside the cycle.

6Middle node in one pass

The same two-speed idea finds the middle without counting n first: slow takes one step while fast takes two. When fast reaches the end, slow sits at the middle. On an even-length list the usual convention returns the second middle (or the first — pick one and stay consistent). Time is still O(n) with O(1) space.

Same five-node chain as Floyd cycle detection, but both pointers start at the head and stop when fast cannot take two steps — slow then sits on the middle.

One pass

Start togetherslow = fast = head.
AdvanceWhile fast and fast.next exist: slow one step, fast two steps.
Read the middleWhen the loop ends, slow is the middle node.

Middle of 1 → 2 → 3 → 4 → 5

Find the middle node of the odd-length list 1 → 2 → 3 → 4 → 5.

startslow=1, fast=1
step 1slow=2, fast=3
step 2slow=3, fast=5
fast.next is null — stopmiddle = 3

Pro tip. This is Floyd's stride pattern without a cycle: fast exploring ahead is what lets slow land halfway in one pass.

On a list of 5 nodes, when fast first sits on the last node, where is slow?

Still on the head
On the middle (node 3)
Also on the last node

Fast moves twice as far, so when it has covered about the full length, slow has covered about half — the middle.

7Merge two sorted lists

Merging two sorted singly linked lists into one sorted list is the linked-list form of the merge step in mergesort. Walk both heads, always splice the smaller current node onto the result, and append whatever remains when one list empties. With a dummy head the edge cases stay uniform. Total time is linear in the combined length; extra space stays constant if you reuse the existing nodes.

Figure. Lists A = 1→3→5 and B = 2→4. First compare takes the smaller head (1) onto the result; the B head stays for the next compare.

How the merge walks

Dummy tailStart a sentinel; keep a tail pointer at the last node of the merged result.
Take the smallerWhile both lists remain, attach the smaller head to tail.next and advance that list's head.
Append the restWhen one list is empty, attach the other list's remaining chain in one shot.

Merge two sorted lists

def merge_two_lists(a, b):
    dummy = tail = Node(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

Merge 1 → 3 → 5 with 2 → 4

Merge sorted lists A = 1 → 3 → 5 and B = 2 → 4 into one sorted list.

compare 1 vs 2take 1; A→3
compare 3 vs 2take 2; B→4
compare 3 vs 4take 3; A→5
compare 5 vs 4take 4; B empty
append rest of A1 → 2 → 3 → 4 → 5

Pro tip. Reuse nodes; do not allocate a fresh node per value unless the problem forbids mutation. The O(1) extra-space claim depends on that.

Merging two sorted lists of lengths n and m by the two-pointer splice above costs

O(nm) comparisons in the worst case
O(n+m) time, because each node is spliced exactly once
O(\log(n+m)) time via binary search on both lists

Every node moves to the result at most once. There is no nested scan of the other list for each node.

8Doubly linked lists

A doubly linked node stores prev and next. Walking backward becomes constant time per step, and deleting a node you already hold needs no hunt for its predecessor. The cost is roughly twice the pointer storage per node and more pointer updates on every splice. Prefer doubly linked when you need reverse walks or constant-time delete-by-node; stay singly linked when memory and simple forward scans dominate.

Figure. Three doubly linked nodes. Forward next edges on top conceptually; prev edges return leftward.

Delete a held doubly linked node

Bridge neighborsIf node.prev exists, set node.prev.next = node.next.
Bridge the other wayIf node.next exists, set node.next.prev = node.prev.
No searchYou never scanned from the head — both neighbors were on the node itself.

Singly vs doubly
Need	Singly	Doubly
Forward walk	Natural	Natural
Backward walk	Not available	O(1) per step via prev
Delete given only the node	Need predecessor (O(n) to find)	O(1) via prev/next
Pointer storage per node	One next	prev and next

You hold a pointer to an interior node and must delete it in O(1) without a predecessor pointer. Which structure supports that directly?

Singly linked list only
Doubly linked list (rewire prev and next)
Either, because delete is always O(1) on lists

Singly linked delete of an arbitrary node needs the predecessor to rewire next. Doubly linked nodes carry prev, so both neighbors can be updated immediately.

Notes

Structure: Each node stores a value and a pointer to the next node (and previous, in a doubly linked list); nodes are not contiguous in memory.
Access vs Insertion: Indexing is O(n) because you must traverse from the head, but inserting/deleting at a known node is O(1) (no shifting).
Reversal: Iteratively re-point each node's next to its predecessor using three pointers (prev, curr, next) in O(n) time and O(1) space.
Cycle Detection: Floyd's tortoise-and-hare uses slow (1 step) and fast (2 steps) pointers; if they meet, a cycle exists.
Dummy Head Node: A sentinel node before the head simplifies edge cases when inserting or deleting at the front.

Formulas

Search/access by position: O(n); insert/delete at a given node: O(1).
Reversal: O(n) time, O(1) space.
Floyd cycle detection: O(n) time, O(1) space.
Merge two sorted lists: O(n+m) time.
Doubly linked list node overhead: two pointers per node versus one for singly linked.

Exam traps & shortcuts

Use a dummy/sentinel head to avoid special-casing operations on the first node.
For 'detect a cycle' or 'find the cycle start,' use fast/slow pointers rather than a visited set (which needs O(n) space).
To find the middle in one pass, advance a fast pointer two steps for each single step of a slow pointer.
Reverse a list iteratively with three pointers; recursion works but costs O(n) stack space.

Reference tables

Costs assume a singly linked list unless noted. "Known node" means you already hold the relevant pointer — the walk to find it is separate.

Complexity sheet
Operation	Time	Extra space
Access / search by position	O(n)	O(1)
Insert / delete after a known node	O(1)	O(1)
Iterative reversal	O(n)	O(1)
Floyd cycle detection	O(n)	O(1)
Merge two sorted lists	O(n+m)	O(1) if reusing nodes
Doubly linked node overhead	—	two pointers per node vs one

Recap

Lists trade index arithmetic for cheap local rewires. Keep the pointer discipline straight and the classic tricks fall out of the same two ideas: a sentinel for edge cases, and two speeds for middle and cycle.

Access trade: No contiguity ⇒ index access is O(n); splice at a known node is O(1).
Sentinel: Dummy head makes head insert/delete look like every other splice.
Reverse: Reverse with prev/curr/next — O(n) time, O(1) space; recursion spends stack.
Two speeds: Floyd: slow×1, fast×2; meet ⇒ cycle. Same strides find the middle.
Doubly linked: Doubly linked: prev buys reverse walk and O(1) delete-by-node.

Practise Linked Lists

Reading is free and needs no account. Practice, mocks and progress live in the app.

5 exam-style questions on this topic, with explanations
A 5-question practice set that ends the chapter
Timed mocks scored with the real marking scheme
Readiness tracked per topic, kept on your device

Continue with Google — freeNo card, no trial. Works offline once installed.