Singly Linked List

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Module 5, Chapter 5 Time to complete: ~25 minutes

Table of Contents

1. What Is a Linked List?
2. The Node Class
3. Building and Traversing a List
4. Insertion
5. Deletion
6. Linked Lists vs. Arrays — Complexity Compared
7. Summary & Next Steps

1. What Is a Linked List?

A linked list is a sequence of elements where each element ("node") holds its value plus a reference ("pointer") to the next node. Unlike a Python list/array (Module 2), the elements are not stored contiguously in memory — they're scattered, connected only by these pointers.

[ 3 | next ] → [ 7 | next ] → [ 1 | next ] → [ 9 | None ]
  head node                                    tail node

This scattered layout is the whole point: inserting or deleting a node only requires rewiring a couple of pointers, not shifting every element after it — the opposite of what happens with an array (Module 2, Chapter 2).

2. The Node Class

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None      # points to the next Node, or None if it's the last one

A linked list itself is usually just a reference to its first node (the "head"):

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

3. Building and Traversing a List

# Building [3, 7, 1, 9] by hand
head = Node(3)
head.next = Node(7)
head.next.next = Node(1)
head.next.next.next = Node(9)
 
# Traversal: follow .next until it's None
def print_list(head):
    current = head
    while current is not None:
        print(current.value, end=" -> ")
        current = current.next
    print("None")
    # O(n) time — must visit every node; O(1) auxiliary space

Manually chaining .next calls doesn't scale — in practice you build lists with a helper:

def build_list(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head
    # O(n) time, O(n) space (n new Node objects)

4. Insertion

def insert_at_head(head, value):
    new_node = Node(value)
    new_node.next = head
    return new_node          # new_node is the new head
    # O(1) — no traversal needed
 
def insert_at_tail(head, value):
    new_node = Node(value)
    if head is None:
        return new_node
    current = head
    while current.next is not None:   # must walk to the end
        current = current.next
    current.next = new_node
    return head
    # O(n) — without a tail pointer, you must traverse the whole list first
 
def insert_after(node, value):
    new_node = Node(value)
    new_node.next = node.next
    node.next = new_node
    # O(1) — given a reference to `node`, insertion is a pointer rewire

Note the asymmetry: inserting at the head is O(1), but inserting at the tail is O(n) unless you separately track a tail pointer (as LinkedList above does) — a common design choice specifically to make tail insertion O(1) too.

5. Deletion

def delete_value(head, value):
    if head is None:
        return None
    if head.value == value:          # deleting the head
        return head.next
    current = head
    while current.next is not None:
        if current.next.value == value:
            current.next = current.next.next    # skip over the node — it's now unreferenced
            return head
        current = current.next
    return head
    # O(n) — must find the node (and the one before it) first

Deleting the head is O(1). Deleting anywhere else requires first finding the node before the one to delete (since a singly linked list has no way to go backward) — that search is O(n).

6. Linked Lists vs. Arrays — Complexity Compared

Neither structure is "better" in general — it's the tradeoff from Chapter 4 of Module 1 (time-space tradeoff) playing out again: arrays win at random access, linked lists win at front insertion/deletion. Choosing between them means asking which operation your problem does most.

7. Summary & Next Steps

Key Takeaways

• A linked list is a chain of Node objects, each pointing to the next — no contiguous memory required.
• Insertion/deletion at the head is O(1), a clear win over an array's O(n) shift.
• Random access by index is O(n) for a linked list, a clear loss compared to an array's O(1).
• The right structure depends on which operations dominate your use case.

Concept Check

1. Why is inserting at the head of a linked list O(1), while inserting at the head of a Python list is O(n)?
2. Why can't you binary search a singly linked list in O(log n), even though it's sorted?
3. What would you need to add to LinkedList to make tail insertion O(1)?

Next Chapter

→ Chapter 2: Doubly Linked List

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index