Data Structures & Algorithms Cheatsheet

Linked Lists

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

Complexity

Nodes are scattered in memory and linked by pointers, so there is no indexing. Every position must be walked to.

Operation	Singly linked	Doubly linked	Dynamic array
access by index	O(n)	O(n)	O(1)
search by value	O(n)	O(n)	O(n)
insert or delete at head	O(1)	O(1)	O(n)
insert or delete at tail	O(n) · O(1) with tail ptr	O(1)	O(1) amortized
insert or delete after a known node	O(1)	O(1)	O(n)
delete a known node (no predecessor)	O(n)	O(1)	O(n)
reverse	O(n) time, O(1) space	O(n)	O(n)

Space is O(n) nodes plus one or two pointers each, so a linked list costs 2–3× an array for the same data and loses every cache benefit. Real code prefers arrays. Interviews use linked lists because pointer manipulation is easy to grade.

Node Definitions

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

def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

The Dummy Head

A sentinel node before the real head removes every "what if this is the first node" branch. Use it whenever the head itself might be removed or replaced.

def remove_elements(head, val):
    dummy = ListNode(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next    # unlink, no head special case
        else:
            cur = cur.next
    return dummy.next

def merge_two_sorted(a, b):
    dummy = tail = ListNode()
    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                  # attach the remaining run
    return dummy.next

Reversal

Three pointers, one pass. This is the single most asked linked-list operation, so it should be muscle memory.

def reverse(head):
    """O(n) time, O(1) space."""
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev                         # new head

def reverse_between(head, left, right):
    """Reverse positions left..right (1-indexed) in one pass."""
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    cur = prev.next
    for _ in range(right - left):       # repeatedly move cur.next to the front
        nxt = cur.next
        cur.next = nxt.next
        nxt.next = prev.next
        prev.next = nxt
    return dummy.next

def reverse_k_group(head, k):
    """Reverse every full group of k, leave any remainder as is."""
    node, count = head, 0
    while node and count < k:
        node = node.next
        count += 1
    if count < k:
        return head                     # tail group too short
    new_head = reverse_first_k(head, k)
    head.next = reverse_k_group(node, k)  # head is now the group tail
    return new_head

def reverse_first_k(head, k):
    prev, cur = None, head
    for _ in range(k):
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

// C++ iterative reversal
ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* nxt = head->next;
        head->next = prev;
        prev = head;
        head = nxt;
    }
    return prev;
}

Fast And Slow Pointers

One pointer moves two steps per one step of the other. That ratio finds the middle, detects cycles, and locates the cycle entry.

def middle(head):
    """Second middle for even length. Use `while fast.next and
    fast.next.next` for the first middle."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def has_cycle(head):
    """Floyd's tortoise and hare. O(n) time, O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def cycle_start(head):
    """Where the loop begins, or None. After the meeting, reset one
    pointer to head and step both one at a time."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

def nth_from_end(head, n):
    """Remove the nth node from the end in one pass."""
    dummy = ListNode(0, head)
    lead = lag = dummy
    for _ in range(n):
        lead = lead.next
    while lead.next:
        lead = lead.next
        lag = lag.next
    lag.next = lag.next.next
    return dummy.next

Why the reset works. If the non-cycle prefix has length a and the meeting point is b steps into a cycle of length c, then the distance from the meeting point back around to the entry is exactly a. Both pointers then arrive at the entry together.

Composite Problems

def is_palindrome(head):
    """O(n) time, O(1) space: find middle, reverse second half, compare."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second = reverse(slow)
    a, b = head, second
    while b:
        if a.val != b.val:
            return False
        a, b = a.next, b.next
    return True

def reorder(head):
    """L0 -> Ln -> L1 -> Ln-1 ... Split, reverse, weave."""
    if not head or not head.next:
        return
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second = reverse(slow.next)
    slow.next = None
    first = head
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2

def add_two_numbers(a, b):
    """Digits stored least significant first."""
    dummy = tail = ListNode()
    carry = 0
    while a or b or carry:
        s = carry + (a.val if a else 0) + (b.val if b else 0)
        carry, digit = divmod(s, 10)
        tail.next = ListNode(digit)
        tail = tail.next
        a = a.next if a else None
        b = b.next if b else None
    return dummy.next

Gotchas

Save next before you overwrite it. cur.next = prev without nxt = cur.next first loses the rest of the list.
Compare nodes with is, not ==. In Python == may call a custom __eq__ and compare values instead of identity.
Guard fast and fast.next, in that order. Checking fast.next first crashes on an empty list.
Even versus odd middles. while fast and fast.next lands on the second middle, while fast.next and fast.next.next on the first. Pick deliberately.
Cut the link when splitting. After finding the middle, set slow.next = None or the two halves stay joined and you build a cycle.
Recursion depth. A recursive reverse is O(n) stack. Python raises RecursionError past about 1,000 frames, so prefer the iterative form on long lists.
Return dummy.next, never head. If the original head was removed, head points into freed territory.
Doubly linked lists need both directions updated. Forgetting node.next.prev leaves a list that traverses correctly forward and corruptly backward.