Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Singly linked lists

Singly linked lists: definition, node structure, operations (create, traverse, search, insert, delete, reverse), complexity, diagrams to draw, Python syntax, and three complete programs with sample I/O.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Singly linked lists are a fundamental dynamic data structure where elements are connected by links, used when frequent insertions and deletions are needed without shifting data (unlike arrays). Engineers use them to build higher-level structures (stacks, queues, hash-table chains) and to model sequences that grow and shrink at runtime in systems, compilers, and networking software.

Key ideas

  • A node is a self-referential record with two fields: a data field storing the element, and a next (or link) field storing a reference to the next node or null.
  • The head (or start) is a reference to the first node of the list. If the list is empty, head is null. Optionally, a tail pointer may be maintained to the last node to speed up insert-at-end.
  • A null (None in Python) reference denotes “no next node”.
  • A sentinel node (dummy node) is a distinguished node placed at the start (or end) whose data is ignored but whose presence simplifies boundary cases (e.g., insertion or deletion at position 0).
  • A position i (0-based) in a list is the count of links from head to reach the node; head is position 0.
  • A traversal visits nodes one by one from head following next references until null.
  • Time complexity model: Access by index is O(n); insertion/deletion given a node reference is O(1); searching by value is O(n). Space per node is one data field plus one pointer; overall auxiliary space is O(n).

Exact statements commonly examined:

  1. Theorem (Traversal time): Traversing a singly linked list of n nodes takes Θ(n) time. Proof: each step follows exactly one next link; there are n links from head to null, so number of steps is proportional to n (lower- and upper-bounded by linear functions of n).
  2. Lemma (Insert after known node): Given a pointer p to a node in a singly linked list, inserting a new node q after p is O(1) by updating two links: q.next ← p.next; p.next ← q. Assumes p is not null and memory for q is available.
  3. Lemma (Delete after known node): Given pointer p to the node preceding node r, deletion of r is O(1): p.next ← r.next; free r. Assumes r exists (p.next = r). In garbage-collected languages like Python, freeing is automatic when no references remain.
  4. Property (Head insertion): Inserting at the beginning is O(1): new.next ← head; head ← new.
  5. Limitation (Random access): Singly linked lists do not provide O(1) indexing; to reach index i we must traverse i links → O(i) time.

Core operations and their stepwise derivations:

  • Create empty list: head ← null.
  • Insert at beginning (push-front): new ← allocate; new.data ← x; new.next ← head; head ← new.
  • Insert at end: if head = null then head ← new else traverse to last node t with t.next = null; set t.next ← new; new.next ← null. If maintaining tail, set tail.next ← new; tail ← new; O(1).
  • Insert at position i (0 ≤ i ≤ length): if i = 0 use head insertion; else traverse to node at position i−1, check bounds, then link as above. Complexity O(n) in worst case.
  • Delete from beginning: if head = null error; else temp ← head; head ← head.next; dispose temp.
  • Delete by value v (first occurrence): use two pointers prev ← null, curr ← head; while curr and curr.data ≠ v: advance; if curr = null not found; else if prev = null delete head; else prev.next ← curr.next; dispose curr. Complexity O(n).
  • Delete at position i (0 ≤ i < length): if i = 0 then delete from beginning; else traverse to the node at position i−1 (prev), check bounds (if prev = null or prev.next = null → error), set target ← prev.next; prev.next ← target.next; dispose target. Complexity O(n).
  • Search for value v: traverse from head comparing data; return position or node if found else not found. O(n).
  • Length: count nodes in one pass: O(n); or maintain a size variable updated on insert/delete for O(1) queries (with careful consistency).
  • Reverse iterative (in-place, O(n), O(1) extra): Maintain three pointers: prev ← null, curr ← head, next ← null. Loop: next ← curr.next; curr.next ← prev; prev ← curr; curr ← next; after loop set head ← prev. Loop invariant: sublist before curr is reversed and points to prev; no nodes lost because next holds remainder. Proof sketch: By induction on number of nodes processed.
  • Reverse recursive: base case head = null or head.next = null returns head; step: newHead ← reverse(head.next); head.next.next ← head; head.next ← null; return newHead. Requires call stack O(n).
  • Cycle detection (Floyd’s Tortoise–Hare): Use two pointers slow and fast; slow steps by one, fast by two; if fast meets slow, cycle exists; if fast or fast.next becomes null, no cycle. Proof idea: if a cycle exists, difference in positions modulo cycle length decreases until they meet. To find the cycle entry: after a meeting, reset one pointer to head and move both one step at a time; their meeting point is the entry (O(n) time, O(1) space).

Diagrams to draw in exams (describe precisely):

  • Node and link: Draw a small rectangle split into two boxes. Left box labeled “data”, right box labeled “next”. From the “next” box draw an arrow to the next node’s rectangle. For the last node, draw the arrow pointing to a small crossed box labeled “null”. Label the first node with a separate arrow from a variable named “head”.
  • Head insertion: Show head pointing to old first node A. Draw new node N. Draw N.next arrow to A; redraw head arrow to N. Cross out the old head→A arrow.
  • Deletion of a middle node: Show nodes P → R → S. Cross the arrow P.next → R. Draw a new arrow from P.next to S. Optionally draw a small cloud “garbage collector frees R” or cross R to show it is removed.
  • Reversal process: Three nodes A→B→C. Show prev, curr, next pointers: prev pointing to null, curr to A, next to B. After one iteration, show A.next ← prev making A point to null, move prev to A, curr to B. Repeat to indicate pattern.

Advantages and disadvantages:

  • Advantages: dynamic size (grows/shrinks at runtime), O(1) insertion/deletion at head or after a known node, no shifting like arrays.
  • Disadvantages: O(n) access by index; extra memory for next pointer per node; poor cache locality; need careful pointer updates; reverse traversal not possible without additional structure (use doubly linked lists for that topic).

Use-cases in syllabus context:

  • Implementing stacks and queues using linked lists (see “Stacks and queues using linked lists”).
  • Chaining in hash tables for collision resolution (see “Collision resolution: chaining”).
  • Adjacency lists in graph representation (see “Graph representation”).

Formulas

Programming syntax and patterns to remember (Python; concise pseudo-code formatting — see worked examples for exact syntax):

  • class Node: def __init__(self, data, next=None): self.data = data; self.next = next # pseudo-code shown compactly; see worked examples for runnable Python Node structure: data field and next pointer (None means null).
  • head is None or head == None Test for empty list.
  • while curr is not None: curr = curr.next Standard traversal from head using a loop.
  • # insert at head: new.next = head; head = new O(1) head insertion steps.
  • # insert after p: q.next = p.next; p.next = q O(1) insertion given pointer to previous node p.
  • # delete after p: r = p.next; p.next = r.next O(1) deletion given pointer to previous node p.
  • # reverse iterative core: next = curr.next; curr.next = prev; prev = curr; curr = next Core four statements inside the loop.
  • slow = slow.next; fast = fast.next.next Floyd’s cycle detection step update.

Worked examples

Example 1: Build, insert at position, delete by value, reverse, and display

Program (Python):

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def push_back(self, x):
        new = Node(x)
        if self.head is None:
            self.head = new
            return
        t = self.head
        while t.next is not None:
            t = t.next
        t.next = new

    def insert_at(self, i, x):
        if i < 0:
            raise IndexError('negative index')
        new = Node(x)
        if i == 0:
            new.next = self.head
            self.head = new
            return
        prev = self.head
        k = 0
        while prev is not None and k < i - 1:
            prev = prev.next
            k += 1
        if prev is None:
            raise IndexError('index out of bounds')
        new.next = prev.next
        prev.next = new

    def delete_value(self, v):
        prev = None
        curr = self.head
        while curr is not None and curr.data != v:
            prev = curr
            curr = curr.next
        if curr is None:
            return False
        if prev is None:
            self.head = curr.next
        else:
            prev.next = curr.next
        return True

    def reverse(self):
        prev = None
        curr = self.head
        while curr is not None:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

    def to_list(self):
        out = []
        t = self.head
        while t is not None:
            out.append(t.data)
            t = t.next
        return out

# I/O driver
import sys
sl = SinglyLinkedList()
line = sys.stdin.readline().strip()
if line:
    for tok in line.split():
        sl.push_back(int(tok))
# next lines: value to insert, position, value to delete
val_line = sys.stdin.readline().strip()
pos_line = sys.stdin.readline().strip()
del_line = sys.stdin.readline().strip()
if val_line:
    val = int(val_line)
    pos = int(pos_line)
    sl.insert_at(pos, val)
if del_line:
    sl.delete_value(int(del_line))
print('List:', ' '.join(map(str, sl.to_list())))
sl.reverse()
print('Reversed:', ' '.join(map(str, sl.to_list())))

Sample input:

10 20 30 40
25
2
30

Exact output:

List: 10 20 25 40
Reversed: 40 25 20 10

Explanation: Start with [10,20,30,40]; insert 25 at index 2 ⇒ [10,20,25,30,40]; delete value 30 ⇒ [10,20,25,40]; reverse ⇒ [40,25,20,10].

Example 2: Detect cycle with Floyd’s algorithm (constructs a cycle programmatically)

Program (Python):

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def make_list_with_cycle():
    # build 1 -> 2 -> 3 -> 4 and link 4.next to node with value 2
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2
    return n1

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

head = make_list_with_cycle()
print('Cycle:', 'Yes' if has_cycle(head) else 'No')

Sample input:


(no input)

Exact output:

Cycle: Yes

Explanation: The fast and slow pointers meet inside the 2→3→4 cycle.

Example 3: Merge two sorted singly linked lists into a single sorted list

Program (Python):

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def from_sorted_list(arr):
    head = None
    tail = None
    for x in arr:
        node = Node(x)
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head

def to_list(head):
    out = []
    t = head
    while t is not None:
        out.append(t.data)
        t = t.next
    return out

def merge_sorted(a, b):
    dummy = Node(0)
    tail = dummy
    pa, pb = a, b
    while pa is not None and pb is not None:
        if pa.data <= pb.data:
            tail.next = pa
            pa = pa.next
        else:
            tail.next = pb
            pb = pb.next
        tail = tail.next
    tail.next = pa if pa is not None else pb
    return dummy.next

# I/O: two lines of sorted integers
import sys
line1 = sys.stdin.readline().strip()
line2 = sys.stdin.readline().strip()
A = list(map(int, line1.split())) if line1 else []
B = list(map(int, line2.split())) if line2 else []
ha = from_sorted_list(A)
hb = from_sorted_list(B)
hc = merge_sorted(ha, hb)
print('Merged:', ' '.join(map(str, to_list(hc))))

Sample input:

1 3 5 7
2 2 4 6 8

Exact output:

Merged: 1 2 2 3 4 5 6 7 8

Explanation: Stable merge by always taking from the list whose head is smaller or equal. Runs in O(m+n) time and O(1) extra space by reusing nodes.

Common mistakes

  • Not handling empty list or single-node cases in insertion, deletion, or reverse.
  • Off-by-one errors when inserting at index i: stopping at the i-th node instead of the (i−1)-th node.
  • Forgetting to update head when inserting/deleting at position 0.
  • Not terminating traversal correctly, leading to infinite loops (e.g., while curr: curr = curr instead of curr = curr.next; or accidental cycles created in code).
  • Assuming O(1) random access like arrays; writing head[i] or similar in pseudo-code.
  • In merge or sorted insert, failing to connect the tail of the result to the remaining non-empty list.
  • In Python, comparing nodes with == to test identity; should use “is” for identity or compare data fields for equality of values.

For your exam

  • Short notes: advantages/disadvantages, use-cases (hash chaining, adjacency lists), complexity summary with O-notation and brief justifications.
  • Algorithms with steps: insert at head/end/position, delete by value/index, search, reverse iterative and recursive, Floyd’s cycle detection. Write preconditions, postconditions, and show key pointer updates in order.
  • Proof sketches: Why traversal is Θ(n); loop invariant for reversal; why Floyd’s algorithm detects a cycle.
  • Programs: implement a singly linked list with core operations and demonstrate with I/O. Ensure correct handling of empty lists and edge cases.
  • Diagrams: neatly draw nodes as boxes with data and next fields, arrows for links, head pointer, and null. For reverse, show prev/curr/next across at least two iterations.
  • Comparison: arrays vs singly linked lists trade-offs (access time, insertion cost, memory overhead) referencing other topics by name without re-teaching.

A full-marks answer is clear about preconditions, includes boundary cases, correct asymptotic analysis, correct and minimal pointer assignments, and a labeled diagram where appropriate.

Quick check

  1. State the two pointer assignments needed to insert a new node q after an existing node p in a singly linked list.
  2. What is the time complexity to access the i-th element in a singly linked list, and why?
  3. Name the pointer update order inside the standard iterative reverse of a singly linked list.

Answers: (1) q.next ← p.next; p.next ← q. (2) O(i) (and O(n) in worst case) because we must traverse from head following next links to reach the i-th node; there is no random access. (3) Save next ← curr.next; set curr.next ← prev; move prev ← curr; advance curr ← next.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?