Singly Linked List

A linked list solves the exact weakness we called out for lists: inserting near the front of a Python list costs O(n) because every later element has to shift over. A linked list gives up a list's O(1) random access in exchange for O(1) insertion and deletion at the head, by storing elements as separate objects connected by references instead of packed into one contiguous buffer.

Why Linked Lists Exist

The Node Class

Every linked list starts with the same tiny building block: a value, and a reference to the next node. Python needs no field types here — just plain attributes set in __init__.

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

Time complexity: O(1) to construct a Node — a fixed amount of attribute assignment. Space complexity: O(1) per node — one value reference and one next reference, regardless of list size.

Insert at Head — O(1)

def insert_at_head(self, val):
    node = Node(val)
    node.next = self.head
    self.head = node
    self.size += 1

Time complexity: O(1) — no traversal needed; only the new node and the head reference are touched. Space complexity: O(1) — one new node allocated.

Insert at Tail — O(n)

Without a dedicated tail pointer, appending means walking the entire list to find the current last node. (A production implementation would keep a self.tail reference specifically to make this O(1) — we show the O(n) walk here because it's the version interviewers usually expect you to derive and discuss.)

def insert_at_tail(self, val):
    node = Node(val)
    if self.head is None:
        self.head = node
    else:
        curr = self.head
        while curr.next is not None:
            curr = curr.next  # walk to the last node
        curr.next = node
    self.size += 1

Time complexity: O(n) — must traverse all existing nodes to reach the end. Space complexity: O(1) — one new node, no extra structures.

Delete by Value — O(n)

Deletion requires finding the target node first (a scan), then relinking its predecessor's next reference to skip over it.

def delete_value(self, val):
    if self.head is None:
        return False

    if self.head.val == val:  # special case: deleting the head itself
        self.head = self.head.next
        self.size -= 1
        return True

    prev = self.head
    while prev.next is not None and prev.next.val != val:
        prev = prev.next

    if prev.next is None:
        return False  # value not found

    prev.next = prev.next.next  # skip over the target node
    self.size -= 1
    return True

Time complexity: O(n) — the search for the target (or its absence) may walk up to the whole list. Space complexity: O(1) — no new nodes allocated; the removed node simply becomes eligible for garbage collection (Python's reference counting reclaims it once nothing points to it).

Traversal — O(n)

def print_all(self):
    curr = self.head
    values = []
    while curr is not None:
        values.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(values) + " -> None")

Time complexity: O(n) — visits every node exactly once. Space complexity: O(n) here for the values list built for printing (an O(1)-space version could print each value immediately instead of collecting them first).

Putting It Together — the Full LinkedList Class

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

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

    def insert_at_head(self, val):
        node = Node(val)
        node.next = self.head
        self.head = node
        self.size += 1

    def insert_at_tail(self, val):
        node = Node(val)
        if self.head is None:
            self.head = node
        else:
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = node
        self.size += 1

    def delete_value(self, val):
        if self.head is None:
            return False
        if self.head.val == val:
            self.head = self.head.next
            self.size -= 1
            return True

        prev = self.head
        while prev.next is not None and prev.next.val != val:
            prev = prev.next
        if prev.next is None:
            return False

        prev.next = prev.next.next
        self.size -= 1
        return True

    def __len__(self):
        return self.size  # O(1): maintained incrementally, never recomputed

Time complexity: constructing the class itself is O(1); each method carries the complexity noted above it (O(1) for head insert and __len__, O(n) for tail insert, delete, and any full traversal). Space complexity: O(n) overall for n stored nodes, plus O(1) extra working space per operation.