Linked Lists

A linear data structure where elements are stored in nodes, each pointing to the next.

Definition

On the arrays page, inserting one element at the front moved every other element over. A linked list pulls off the same insert with two pointer updates, and it doesn't matter whether the list holds ten items or ten million. What kind of structure makes that possible?

One that gives up the thing arrays are built on. A linked list is a chain of list nodes, where each node points to the next using a pointer. Linked lists are stored noncontiguously in memory, so nodes can sit anywhere there's free space. Nothing ever needs to shift to make room, which is why inserting and deleting are so cheap. The price shows up when you want to read: with no neat row of lockers, there's no formula that jumps straight to item 3. You follow the chain, one pointer at a time.

Operations

Watch the head insert that arrays struggled with. Say the list is 7 → 12 → 25 and you want a 3 at the front. Create the node, aim its next pointer at the 7, and move head to the new node. Two pointer updates, zero shifting, and the count stays two even when the list holds a million nodes. That's why you can add or remove items at the head in constant time, and why you can split or join whole lists just by rerouting a few pointers.

Now the part that trips people up. You might think a linked list can insert anywhere in O(1), making it strictly better than an array. What actually happens: the insert itself is cheap, but getting to the spot costs O(n), because the only way to reach a node is to walk the chain from the head. Notice how many rows in the table below include a traversal step first. But if you already hold a pointer to a node, the work at that spot really is constant time. That's why linked lists shine when you keep references to important spots, like tracking both ends with sentinel nodes. Here's the full cost breakdown, traversal included:

Operations	Time	Space	Notes
Insert at Head	O(1)	O(1)	Adds node at beginning. Just update head pointer
Insert at Tail	O(1)	O(1)	Adds node at end. Requires tail pointer, else O(n)
Insert at Position	O(n)	O(1)	Must traverse to position first, then O(1) to insert
Delete from Head	O(1)	O(1)	Removes first node. Update head pointer
Delete from Tail	O(1)*	O(1)	O(1) for doubly-linked list, O(n) for singly-linked without tail
Delete at Position	O(n)	O(1)	Must traverse to position first, then O(1) to delete
Access	O(n)	O(1)	Must traverse from head to reach nth position
Search	O(n)	O(1)	Must traverse until value is found or reach end
Size	O(1)*	O(1)	O(1) if size is maintained, O(n) if counting nodes
Reverse	O(n)	O(1)	Must visit each node to reverse pointers
Get Middle	O(n)	O(1)	Can use slow/fast pointer technique

Linked List Nodes

A linked list's flexibility comes from one tiny building block. A linked list node is like a box with two compartments: one for your data (called value), and another that points to the next box in line (called next). The picture misses one thing, though: boxes on a shelf sit in order, while nodes are scattered wherever memory had room, and the pointer is the only thing that knows where the next box lives. Unlike arrays, where elements are locked in place, linked list elements can connect and disconnect freely just by changing where their pointers aim.

The value you want to store (like a number or a word)
One or two pointers that show the way to other connected nodes

Nodes get their power from how they connect. By changing how they point to each other, we can build different types of linked lists. Simple chains point only forward, while more complex structures like circular lists or doubly linked lists allow more flexibility. That's why linked lists show up as building blocks inside other data structures like queues and hashmaps.

Linked List Pointers

Pointers are like threads that stitch nodes together into a chain. Arrays put their elements side by side in memory, but linked lists use pointers to connect nodes that can live anywhere. That makes insertion and deletion much simpler. Instead of shifting elements around like in an array, you just reconnect a few pointers.

Here is 7 → 12 → 25 → null. We want to insert 99 between 7 and 12, so we build it off to the side first, its next aimed nowhere yet.

Two pointers have to change: 99.next and 7.next. Tap the node whose next you set first.Whichever you skip, the list still has to reach 12. Which node still knows where 12 is?

Set 99.next first. While 7 still points at 12, 99 can grab the rest of the list safely. Redirect 7 first and the path to 12 is gone.

99.next = 12. The new node grabs the rest of the list while 7 still points there too, so nothing is lost yet. 7 just doesn't point at 99 yet.

7.next = 99, and the splice is done: 7 → 99 → 12 → 25. Set 7.next first instead and 12 and 25 float away unreachable. That order is the whole skill.

Here is 7 → 12 → 25 → null. We want to insert 99 between 7 and 12, so we build it off to the side first, its next aimed nowhere yet.

head▼

x▼

null

Working with pointers is all about doing things in the right order, and the caution has a real reason: a pointer is often the only connection to everything that comes after it. Overwrite it too early and the rest of the list becomes unreachable, because nothing points to it anymore. So when adding a new node, set up the new node's connections first while it's still separate from the list, then splice it into the existing structure. It's like connecting train cars, with one difference: there's no track under a linked list. Uncouple at the wrong moment and everything behind the break is gone.

Singly Linked List

Singly linked lists are like a scavenger hunt where each clue only points to the next location. This one-way structure makes them easy to understand and implement. You can only move forward through the list, but that simplicity makes them a solid fit for basic storage and straightforward traversal. The hunt analogy breaks in one way that matters: on a real scavenger hunt you can retrace your steps. Here, no clue points backward.

The val holds the actual information you want to store, like a number or a word
The next pointer shows the way to the next node, like an arrow pointing forward

Singly linked lists win on simplicity and memory: each node only needs one pointer, and operations at the beginning of the list are extremely fast. The tradeoff is that you have to keep careful track of your position. Once you move past a node, there's no way back.

singly_linked_list.py

# ListNode class for Singly Linked List
class ListNode:
    def __init__(self, val: int = 0, next = None):
        self.val = val
        self.next = next

A singly list has one handle, head, so a read starts there with cur on 7. Each arrow is a next pointer.

cur = cur.next lights up the pointer leaving 7 and follows it to 12, exactly one node forward.

Again, cur follows 12.next to 25, the last node.

25.next is null, so cur = cur.next steps onto null and while cur stops. You only ever follow one next at a time, never jumping to an arbitrary node.

A singly list has one handle, head, so a read starts there with cur on 7. Each arrow is a next pointer.

head

cur▼

x▼

null

The last node's next pointer points to null, marking the end of the list. That boundary tells you when to stop traversing and helps prevent errors. Unlike arrays, which can jump to any position instantly, singly linked lists always start from the beginning and follow the next pointers until they find what they're looking for. That raises a question worth sitting with for a second: you're holding a pointer to a node in the middle of the list and you need the node right before it. How do you get there?

Doubly Linked List

How do you reach the node just before the one you're standing on? In a singly linked list, the only honest answer is to walk from the head all over again. Doubly linked lists exist so you never have to. They give each node two pointers: one forward, one backward. Think of a train where each railcar connects to the cars in front of and behind it. This bidirectional movement makes many operations more efficient, and it even lets you walk the list in reverse.

The val holds the actual information you want to store, like a number or a word.
The next pointer shows the way to the next node, like an arrow pointing forward.
The prev pointer points to the previous node, like an arrow pointing backward.

The extra pointer isn't free. Doubly linked lists use more memory, and every insertion or deletion has to update both next and prev correctly. Even so, the added flexibility usually wins out when you need to traverse in both directions or delete nodes frequently. Before the code, make a prediction: inserting a new node between two existing neighbors, how many pointers have to change?

doubly_linked_list.py

# ListNode class for Doubly Linked List
class ListNode:
    def __init__(self, val: int = 0, prev = None, next = None):
        self.val = val
        self.prev = prev
        self.next = next

The list is null ← 8 ⇄ 3 ⇄ 5 → null. We want to insert 99 after 3, so we build it off to the side first, both its prev and next unset.

Set 99's own prev and next first. With 3 ⇄ 5 still intact, 99 captures both neighbors safely.

99.prev = 3 and 99.next = 5. The new node now reaches both neighbors, but neither 3 nor 5 points back at it yet.

3.next = 99 and 5.prev = 99. The neighbors turn around to face 99: 8 ⇄ 3 ⇄ 99 ⇄ 5. Walking back from 5 now passes 99 too, so both directions still agree.

The list is null ← 8 ⇄ 3 ⇄ 5 → null. We want to insert 99 after 3, so we build it off to the side first, both its prev and next unset.

x▼

null

head▼

nextprev

x▼

nextprev

x▼

null

The answer is four: the new node's prev and next, plus the next of the node before it and the prev of the node after it. Miss one and the chain disagrees with itself depending on which direction you walk. You'll also notice the first node's prev pointer and the last node's next pointer both point to null, marking the ends of the list. This double-linked structure makes deleting nodes much easier than in a singly linked list, since you don't need to track the previous node while traversing. It's already connected.

Sentinel Nodes

Every insert and delete so far hides some annoying special cases. Inserting into an empty list needs its own code path. So does deleting the head, and so does deleting the tail, because each one rewires the list's entry points instead of an ordinary node. Sentinel nodes, also called dummy nodes, make those cases disappear. They don't hold real data. They sit at the start and end of the list as permanent placeholders, so every real node always has a neighbor on both sides.

sentinel_nodes.py

# Definition of a doubly linked list
class ListNode:
    def __init__(self, val: int = 0, prev = None, next = None):
        self.val = val
        self.prev = prev
        self.next = next

class DoublyLinkedList:
    def __init__(self):
        # Create left and right dummy nodes
        self.left = ListNode(0)
        self.right = ListNode(0)
        # Connect the dummy nodes
        self.left.next = self.right
        self.right.prev = self.left

    def get_head(self) -> Optional[ListNode]:
        # Return first real node or None if empty
        cur = self.left.next
        if cur == self.right:
            return None
        return cur

A sentinel list is born with two dummies, left and right, wired to each other. To insert 5, we build it off to the side first, its prev and next unset.

Tap the node whose pointers you set first, before touching left.Same move as any insert: wire the newcomer to its neighbors first.

Set 5's own prev and next first. Because left and right already exist, this is the same splice as any other, with nothing special about the empty list.

5.prev = left and 5.next = right. The new node reaches both dummies, but neither dummy points back at it yet.

left.next = 5 and right.prev = 5: left ⇄ 5 ⇄ right. The exact same four writes as inserting anywhere else, with no empty-list special case, because left and right are always there to splice between.

A sentinel list is born with two dummies, left and right, wired to each other. To insert 5, we build it off to the side first, its prev and next unset.

left▼

nextprev

right▼

The linked list starts with two dummy nodes: self.left and self.right. They form a fixed boundary around the list, so an empty list, the head, and the tail stop being special: every real insert happens between two nodes that already exist. This removes the need to handle edge cases, and the result is cleaner code overall.

Best Practices

Linked lists are worth knowing well because they sit underneath a lot of other data structures, including hashmaps and queues. Here are a few tips for working with them:

Pointers are the whole game with linked lists. Practice advancing them safely, and learn how to insert or remove nodes without losing your reference to the rest of the list.

Algorithms

Two Pointers

→

A technique using two pointers to traverse data structures efficiently.

L →← R

Fast & Slow Pointers

→

A technique using two pointers moving at different speeds to detect cycles.

Recursion

→

A method where a function calls itself to solve smaller instances of the same problem.

Sorting

→

Algorithms for arranging elements in a specific order for efficient processing.

Practice Problems

First, a quick self-check from this page: why is inserting at the head O(1) while inserting at position i is O(n)? And what does the prev pointer buy you when you delete a node? If both answers come back quickly, you're ready. Linked lists are all about pointer surgery. Work through these classic problems to build muscle memory for reversal, dummy nodes, fast/slow traversal, and design problems that combine multiple techniques:

Data StructuresLinked Lists

Linked Lists

A linear data structure where elements are stored in nodes, each pointing to the next.

Data StructuresLinked Lists

Linked Lists

A linear data structure where elements are stored in nodes, each pointing to the next.

Definition

Operations

Operations	Time	Space	Notes
Insert at Head	O(1)	O(1)	Adds node at beginning. Just update head pointer
Insert at Tail	O(1)	O(1)	Adds node at end. Requires tail pointer, else O(n)
Insert at Position	O(n)	O(1)	Must traverse to position first, then O(1) to insert
Delete from Head	O(1)	O(1)	Removes first node. Update head pointer
Delete from Tail	O(1)*	O(1)	O(1) for doubly-linked list, O(n) for singly-linked without tail
Delete at Position	O(n)	O(1)	Must traverse to position first, then O(1) to delete
Access	O(n)	O(1)	Must traverse from head to reach nth position
Search	O(n)	O(1)	Must traverse until value is found or reach end
Size	O(1)*	O(1)	O(1) if size is maintained, O(n) if counting nodes
Reverse	O(n)	O(1)	Must visit each node to reverse pointers
Get Middle	O(n)	O(1)	Can use slow/fast pointer technique

Linked List Nodes

The value you want to store (like a number or a word)
One or two pointers that show the way to other connected nodes

Linked List Pointers

Here is 7 → 12 → 25 → null. We want to insert 99 between 7 and 12, so we build it off to the side first, its next aimed nowhere yet.

Two pointers have to change: 99.next and 7.next. Tap the node whose next you set first.Whichever you skip, the list still has to reach 12. Which node still knows where 12 is?

Set 99.next first. While 7 still points at 12, 99 can grab the rest of the list safely. Redirect 7 first and the path to 12 is gone.

99.next = 12. The new node grabs the rest of the list while 7 still points there too, so nothing is lost yet. 7 just doesn't point at 99 yet.

7.next = 99, and the splice is done: 7 → 99 → 12 → 25. Set 7.next first instead and 12 and 25 float away unreachable. That order is the whole skill.

Here is 7 → 12 → 25 → null. We want to insert 99 between 7 and 12, so we build it off to the side first, its next aimed nowhere yet.

head▼

x▼

null

Singly Linked List

The val holds the actual information you want to store, like a number or a word
The next pointer shows the way to the next node, like an arrow pointing forward

singly_linked_list.py

# ListNode class for Singly Linked List
class ListNode:
    def __init__(self, val: int = 0, next = None):
        self.val = val
        self.next = next

A singly list has one handle, head, so a read starts there with cur on 7. Each arrow is a next pointer.

cur = cur.next lights up the pointer leaving 7 and follows it to 12, exactly one node forward.

Again, cur follows 12.next to 25, the last node.

25.next is null, so cur = cur.next steps onto null and while cur stops. You only ever follow one next at a time, never jumping to an arbitrary node.

A singly list has one handle, head, so a read starts there with cur on 7. Each arrow is a next pointer.

head

cur▼

x▼

null

Doubly Linked List

The val holds the actual information you want to store, like a number or a word.
The next pointer shows the way to the next node, like an arrow pointing forward.
The prev pointer points to the previous node, like an arrow pointing backward.

doubly_linked_list.py

# ListNode class for Doubly Linked List
class ListNode:
    def __init__(self, val: int = 0, prev = None, next = None):
        self.val = val
        self.prev = prev
        self.next = next

The list is null ← 8 ⇄ 3 ⇄ 5 → null. We want to insert 99 after 3, so we build it off to the side first, both its prev and next unset.

Set 99's own prev and next first. With 3 ⇄ 5 still intact, 99 captures both neighbors safely.

99.prev = 3 and 99.next = 5. The new node now reaches both neighbors, but neither 3 nor 5 points back at it yet.

3.next = 99 and 5.prev = 99. The neighbors turn around to face 99: 8 ⇄ 3 ⇄ 99 ⇄ 5. Walking back from 5 now passes 99 too, so both directions still agree.

The list is null ← 8 ⇄ 3 ⇄ 5 → null. We want to insert 99 after 3, so we build it off to the side first, both its prev and next unset.

x▼

null

head▼

nextprev

x▼

nextprev

x▼

null

Sentinel Nodes

sentinel_nodes.py

# Definition of a doubly linked list
class ListNode:
    def __init__(self, val: int = 0, prev = None, next = None):
        self.val = val
        self.prev = prev
        self.next = next

class DoublyLinkedList:
    def __init__(self):
        # Create left and right dummy nodes
        self.left = ListNode(0)
        self.right = ListNode(0)
        # Connect the dummy nodes
        self.left.next = self.right
        self.right.prev = self.left

    def get_head(self) -> Optional[ListNode]:
        # Return first real node or None if empty
        cur = self.left.next
        if cur == self.right:
            return None
        return cur

A sentinel list is born with two dummies, left and right, wired to each other. To insert 5, we build it off to the side first, its prev and next unset.

Tap the node whose pointers you set first, before touching left.Same move as any insert: wire the newcomer to its neighbors first.

Set 5's own prev and next first. Because left and right already exist, this is the same splice as any other, with nothing special about the empty list.

5.prev = left and 5.next = right. The new node reaches both dummies, but neither dummy points back at it yet.

A sentinel list is born with two dummies, left and right, wired to each other. To insert 5, we build it off to the side first, its prev and next unset.

left▼

nextprev

right▼

Best Practices

Linked lists are worth knowing well because they sit underneath a lot of other data structures, including hashmaps and queues. Here are a few tips for working with them:

Pointers are the whole game with linked lists. Practice advancing them safely, and learn how to insert or remove nodes without losing your reference to the rest of the list.

Algorithms

Two Pointers

→

A technique using two pointers to traverse data structures efficiently.

L →← R

Fast & Slow Pointers

→

A technique using two pointers moving at different speeds to detect cycles.

Recursion

→

A method where a function calls itself to solve smaller instances of the same problem.

Sorting

→

Algorithms for arranging elements in a specific order for efficient processing.

Practice Problems

Completed	Title		Status	Notes	Solution
	Reverse Linked List	Easy
	Merge Two Sorted Lists	Easy
	Linked List Cycle	Easy
	Middle of the Linked List	Easy
	Reorder List	Medium
	Remove Nth Node From End of List	Medium
	Add Two Numbers	Medium
	Copy List with Random Pointer	Medium
	LRU Cache	Medium
	Sort List	Medium
	Merge k Sorted Lists	Hard
	Reverse Nodes in k-Group	Hard

Linked Lists

A linear data structure where elements are stored in nodes, each pointing to the next.

singly_linked_list.py

doubly_linked_list.py

sentinel_nodes.py

Mastering Pointers

Understanding Dummy Nodes

Recognizing Patterns

Tackling Recursive Problems

Practice with Variants

Two Pointers

Fast & Slow Pointers

Recursion

Sorting

Linked Lists

A linear data structure where elements are stored in nodes, each pointing to the next.

Linked Lists

A linear data structure where elements are stored in nodes, each pointing to the next.

singly_linked_list.py

doubly_linked_list.py

sentinel_nodes.py

Mastering Pointers

Understanding Dummy Nodes

Recognizing Patterns

Tackling Recursive Problems

Practice with Variants

Two Pointers

Fast & Slow Pointers

Recursion

Sorting