Singly Linked ListSingly linked lists

01Why it exists

Reach for it when you see:You do not know how many there will be, frequent insertion and deletion in the middle, node.next, head, pointers being rewired, the ListNode that shows up in interviews.

02The core idea

A singly linked list is made of nodes, and each node records just two things: its own value, and where the next node is (next). The last node's next is None. The whole list is held by a single head pointer at the front; every other node has to be reached by following next from head.

Lists and arrays are a matched pair of trade-offs. An array computes addresses from contiguous memory, so random access is O(1) and inserting in the middle is O(n). A list gives up contiguity, so inserting and deleting at a known position is O(1) — just pointer changes — but reaching element i takes i steps, which is O(n). Searching for a value is O(n) in both. In one line: arrays are good at reading, lists are good at restructuring at a position you already hold.

In practice a plain singly linked list is rarely the right tool on its own, because every node carries an extra pointer and the layout is unkind to the cache. Its real value is as practice with pointers and as a component of more complex structures. Two habits are worth building: a sentinel node (dummy head) removes the special cases for "delete the head" and "insert at the front"; and when rewiring, attach the new pointer before detaching the old one, so you never lose the rest of the list.

03The algorithm

1. 1Inserting after node p: point the new node's next at p.next first, then point p.next at the new node. Do it the other way round and you lose everything after p.
2. 2Deleting the node after p: p.next = p.next.next. Nothing points at the skipped node any more, so it is gone (in C++ you have to delete it yourself).
3. 3For any operation that can touch the head, create a dummy node pointing at head first and return dummy.next when you are done. That makes "delete the head" and "delete from the middle" the same piece of code.
4. 4Traverse with while cur:, keeping an extra prev when you need the previous node. Use while cur.next: when you want to stop on the last node.
5. 5Once it is written, test three inputs: an empty list, a list of one node, and a target that is the last node. Almost every bug in a pointer problem is at a boundary.

04Interactive demo

A comparison of how many nodes each operation walks past. Inserting at the front walks none, while inserting at the back and reading element 4 both walk all the way from head; deleting rewires a single pointer and leaves everything after it untouched.

05Code

A minimal hand-written list class with the complexity marked on every method, ending with a sentinel node that shows how "delete every node equal to val" gets rid of the special case for the head.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next          # points at the next node; None on the last one


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

    def push_front(self, val):            # O(1)
        self.head = Node(val, self.head)  # the new node's next points at the old head
        self.size += 1

    def push_back(self, val):             # O(n): with no tail pointer you have to walk to the end
        node = Node(val)
        if self.head is None:
            self.head = node
        else:
            cur = self.head
            while cur.next:
                cur = cur.next
            cur.next = node
        self.size += 1

    def get(self, index):                 # O(n): one node at a time is the only way
        cur = self.head
        for _ in range(index):
            cur = cur.next
        return cur.val

    def insert_after(self, node, val):    # O(1): given that you already hold the node
        node.next = Node(val, node.next)
        self.size += 1

    def remove_after(self, node):         # O(1): skip over the next node
        if node.next:
            node.next = node.next.next
            self.size -= 1

    def find(self, val):                  # O(n)
        cur = self.head
        while cur and cur.val != val:
            cur = cur.next
        return cur


# A sentinel (dummy) node removes the special case for "delete the head"
def remove_all(head, val):
    dummy = Node(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next      # skip it
        else:
            cur = cur.next
    return dummy.next

06Practice

• LeetCode 707Design Linked ListMedium
• LeetCode 203Remove Linked List Elements (sentinel node)Easy
• LeetCode 83Remove Duplicates from Sorted ListEasy
• LeetCode 237Delete Node in a Linked List (deleting without the previous node)Medium
• LeetCode 19Remove Nth Node From End of ListMedium