Fundamentals

Linked lists and stacks are the two most foundational pointer-based data structures. Understanding how nodes connect and how LIFO ordering works gives you the toolkit to solve dozens of interview problems efficiently.

LinkedList Node Structure

Every linked list is built from nodes. Each node stores a value and a pointer to the next node (and optionally a previous node for doubly linked lists).

class ListNode:
    """Singly Linked List Node.

    This is the standard definition used in LeetCode problems.
    """
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class DListNode:
    """Doubly Linked List Node.

    Used in problems like LRU Cache where you need O(1) removal.
    """
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

Singly vs Doubly Linked List

# Singly Linked List (traverse forward only)
#
#   head
#    |
#    v
#  [1] -> [2] -> [3] -> [4] -> None
#
# Each node has: val, next

# Doubly Linked List (traverse both directions)
#
#           head                          tail
#            |                             |
#            v                             v
#  None <- [1] <-> [2] <-> [3] <-> [4] -> None
#
# Each node has: val, prev, next

Building a Linked List from an Array

def build_list(values):
    """Create a linked list from a Python list.

    Args:
        values: List of values, e.g., [1, 2, 3, 4]

    Returns:
        Head node of the linked list

    Example:
        head = build_list([1, 2, 3])
        # Creates: 1 -> 2 -> 3 -> None
    """
    dummy = ListNode(0)
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next


def print_list(head):
    """Print a linked list for debugging.

    Output format: 1 -> 2 -> 3 -> None
    """
    parts = []
    while head:
        parts.append(str(head.val))
        head = head.next
    print(" -> ".join(parts) + " -> None")

Stack Operations

A stack follows Last-In-First-Out (LIFO) ordering. In Python, use a regular list as a stack:

# Stack operations using Python list
#
#   push(5)    push(3)    push(7)    pop()     peek()
#                                     -> 7      -> 3
#              +---+      +---+
#              |   |      | 7 |      +---+      +---+
#   +---+      +---+      +---+      |   |      |   |
#   | 5 |      | 3 |      | 3 |      +---+      +---+
#   +---+      +---+      +---+      | 3 |      | 3 |
#   |   |      | 5 |      | 5 |      +---+      +---+
#   +---+      +---+      +---+      | 5 |      | 5 |
#                                     +---+      +---+

stack = []

# Push: O(1) amortized
stack.append(5)   # stack = [5]
stack.append(3)   # stack = [5, 3]
stack.append(7)   # stack = [5, 3, 7]

# Pop: O(1) - removes and returns top
top = stack.pop()  # top = 7, stack = [5, 3]

# Peek: O(1) - view top without removing
top = stack[-1]    # top = 3, stack unchanged

# Is empty: O(1)
is_empty = len(stack) == 0  # False

# Size: O(1)
size = len(stack)  # 2

When to Use Each Structure

The Dummy Node Pattern

Most linked list problems are easier with a dummy (sentinel) node. It eliminates edge cases when the head might change:

def remove_elements(head, val):
    """Remove all nodes with a given value.

    Using a dummy node avoids special handling
    when the head itself needs to be removed.

    Time:  O(n) - single pass
    Space: O(1) - only pointers
    """
    # Dummy node points to head
    #   dummy -> [1] -> [2] -> [6] -> [3] -> None
    #                          ^^^
    #                     remove val=6
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next  # skip the node
        else:
            prev = prev.next

    return dummy.next  # new head

Complexity Summary

* amortized   † O(1) if tail pointer maintained