Linked Lists
Singly, doubly and circular linked lists in Python, traversal, insertion and deletion at the head, tail and middle, the costs compared with arrays, and the classic pointer techniques — reversal, the fast/slow (tortoise and hare) pointers for the middle and for cycle detection, merging sorted lists, and sentinel nodes.
The idea
A linked list stores elements in nodes scattered in memory; each node holds a value and a reference to the next node. Unlike an array, there is no contiguous block and no index arithmetic.
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
# 3 -> 7 -> 1 -> None
head = Node(3, Node(7, Node(1)))
def to_list(head):
out = []
while head: # traversal: O(n)
out.append(head.val)
head = head.next
return out
Variants
| Variant | Node fields | Notes |
|---|---|---|
| Singly linked | val, next | simplest; can only move forward |
| Doubly linked | val, prev, next | deletion given a node; backward traversal; more memory |
| Circular | last node points to the first | round-robin scheduling; no None terminator — loops need a stop condition |
| With tail pointer | extra tail reference | append at the end — a natural queue |
Operations and costs
| Operation | Singly linked (head only) | With tail | Doubly linked | Array (Python list) |
|---|---|---|---|---|
| Access -th element | ||||
| Search for a value | ||||
| Insert/delete at head | ||||
| Insert at tail | amortised | |||
| Delete at tail | ||||
| Insert after a known node | ||||
| Delete a known node | (need predecessor) |
def insert_after(node, val): # O(1)
node.next = Node(val, node.next)
def delete_after(node): # O(1): unlink node.next
if node.next:
node.next = node.next.next
def push_front(head, val): # returns the new head
return Node(val, head)
Classic techniques
Reversal in place — time, space
def reverse(head):
prev = None
while head:
nxt = head.next # save the rest
head.next = prev # point backwards
prev, head = head, nxt
return prev # new head
Fast and slow pointers
- Middle node: move
slowone step andfasttwo steps; whenfastreaches the end,slowis at the middle. - Cycle detection (Floyd): if there is a cycle,
fastlapsslowand they meet; to find the entry, restart one pointer at the head and move both one step at a time. - -th node from the end: advance one pointer steps, then move both until the leader hits the end.
Merging two sorted lists
def merge(a, b):
dummy = tail = Node(None)
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
This is the core of merge sort on linked lists, which sorts in without random access.
Where linked structures show up
Stacks and queues (head insertion/removal), adjacency lists of graphs, separate chaining in hash tables (see hash tables), LRU caches (doubly linked list + hash map), and memory allocators' free lists.
Quick revision
Practice questions
GATE-style questions: 3 one-mark and 6 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.
In a singly linked list of nodes with only a head pointer, the time to insert at the head and to access the -th node are, respectively,
What does this program print?
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def build(xs):
head = None
for x in reversed(xs):
head = Node(x, head)
return head
def mystery(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
h = mystery(build([1, 2, 3, 4]))
print(h.val * 10 + h.next.val)
Floyd's cycle-detection algorithm moves a slow pointer one step and a fast pointer two steps at a time. Which statement is correct?
The helpers below are defined first:
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def build(xs):
head = None
for x in reversed(xs):
head = Node(x, head)
return head
Using these helpers, what does this program print?
def middle(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
return slow.val
print(middle(build([10, 20, 30, 40, 50, 60])))
Compared with a Python list (dynamic array), a singly linked list
One or more options are correct.
Given a direct reference to a node in a doubly linked list, deleting that node takes
The helpers below are defined first:
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def build(xs):
head = None
for x in reversed(xs):
head = Node(x, head)
return head
Using these helpers, what does this program print?
def f(node):
if node is None:
return 0
if node.next is None:
return node.val
return node.val + f(node.next.next)
print(f(build([1, 2, 3, 4, 5])))
Two sorted singly linked lists have lengths and . Merging them into one sorted list by relinking nodes takes
To insert a new node between two existing adjacent nodes of a doubly linked list, the number of pointer fields that must be set or changed is ______.