Basics of Linked Lists (Linked Storage)

Anyone who has solved problems on LeetCode has almost certainly worked with singly linked lists. LeetCode represents a node like this:

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

That definition is deliberately minimal so the focus stays on algorithm questions. Nodes in actual language standard libraries tend to be richer. A typical version looks more like:

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

Two practical differences stand out. First, real libraries usually support generics, letting the stored value be any type; LeetCode’s version restricts it to an integer. Second, most libraries prefer doubly linked lists over singly linked ones. A singly linked node carries only a next pointer, while a doubly linked node also stores a prev pointer to the preceding node.

The extra prev pointer enables traversal in both directions. The cost is that insertions, deletions, searches, and updates become slightly more involved because both pointers must stay consistent. We will examine that carefully when we build a doubly linked list later.

Why Use Linked Lists?

Earlier we looked at how arrays store data in one contiguous memory block. From the starting address of that block you can jump straight to any element by calculating an offset from its index.

A linked list works differently. It does not require its elements to occupy neighboring memory locations. Nodes can live anywhere in memory; each one simply holds pointers (next and, in the doubly linked case, prev) that connect the scattered pieces into a chain.

This design has clear advantages. Memory is used more flexibly: whenever a new node is needed, a small free chunk of memory can be allocated and the node created. There is no requirement that it sit next to the previous node. Nodes can also be added or removed on demand, so there is never a need to resize an underlying buffer or shift existing elements. In principle a linked list can grow until memory itself is exhausted—an uncommon practical limit.

The trade-off is the loss of constant-time random access. Because nodes are not laid out contiguously, reaching the element at a given index means starting at the head and following pointers until that node is found. That is the essential idea behind linked lists. Next we will implement the fundamental operations for both singly and doubly linked lists.

Core Operations on Singly Linked Lists

A small helper that turns an array into a singly linked list will be useful for the examples that follow:

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

# Build a singly linked list from an array
def createLinkedList(arr):
    if arr is None or len(arr) == 0:
        return None

    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next

    return head

Reading and Updating

To walk every node and print its value:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Traverse and print
p = head
while p is not None:
    print(p.val)
    p = p.next

Accessing or changing a node by index follows the same pattern: begin at the head and advance a pointer in a loop until the desired position is reached, then read or write the value. In the worst case this costs linear time in the length of the list.

Insertion

At the head.

Because we already hold a reference to the current head, the new node is simply placed in front of it and the head reference is updated:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Insert 0 at the front
newNode = ListNode(0)
newNode.next = head
head = newNode

# List is now 0 -> 1 -> 2 -> 3 -> 4 -> 5

This runs in constant time.

At the tail.

The straightforward approach is:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Insert 6 at the end
p = head
# Advance to the final node
while p.next is not None:
    p = p.next
# Attach the new node
p.next = ListNode(6)

# List is now 1 -> 2 -> 3 -> 4 -> 5 -> 6

The operation is linear because the end of the list must first be located. Maintaining an explicit tail reference eliminates the traversal; that optimization appears when we implement a doubly linked list.

In the middle.

Locate the node immediately before the insertion point, then splice the new node into the chain:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Insert 66 after the third node
# First reach the predecessor (the third node)
p = head
for _ in range(2):
    p = p.next
# p now points at the third node

# Wire the new node’s successor
new_node = ListNode(66)
new_node.next = p.next

# Link it in
p.next = new_node

# List is now 1 -> 2 -> 3 -> 66 -> 4 -> 5

Again the cost is linear because the predecessor must be found.

Deletion

An arbitrary node.

Find the predecessor of the node to be removed, then retarget that predecessor’s next pointer so it skips the unwanted node:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Delete the fourth node by operating on its predecessor
p = head
for i in range(2):
    p = p.next

# p is now the third node (predecessor of the target)
# Unlink the fourth node
p.next = p.next.next

# List is now 1 -> 2 -> 3 -> 5

The work is linear because the predecessor must be located.

The tail.

Reach the second-to-last node and set its next pointer to null:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Remove the last node
p = head
# Advance to the second-to-last node
while p.next.next is not None:
    p = p.next

# Detach the final node
p.next = None

# List is now 1 -> 2 -> 3 -> 4

This is also linear.

The head.

Simply advance the head reference:

# Build the list
head = createLinkedList([1, 2, 3, 4, 5])

# Remove the first node
head = head.next

# List is now 2 -> 3 -> 4 -> 5

The operation is constant time.

A common question is whether the discarded head node (the original node holding 1) still pointing at the new head creates a memory leak. It does not. Once no live references remain to that node, a garbage collector reclaims it. This automatic reclamation occurs in languages that provide garbage collection (Java, Go, Python, JavaScript, and similar). C and C++ lack a collector, so the programmer must explicitly free each removed node; otherwise memory leaks. That is why the corresponding C/C++ implementations free the deleted nodes by hand.

Explicitly nulling the deleted node’s next pointer is still good practice; it can prevent accidental use of a stale pointer in other situations. In the accompanying visualization the deleted node’s next pointer is deliberately set to null.