Linked Lists
A linear data structure where elements are stored in nodes, each pointing to the next.
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. This means you can insert or delete a node anywhere in the list without shifting the rest of the data around.
Singly linked lists are great for operations at the beginning of the list. You can add or remove items there in constant time. Each list node connects to the next with a pointer, so you walk through the list one step at a time. You can also split or join lists just by rerouting a few pointers.
| Operations | Time | Space |
|---|---|---|
| Insert at Head | O(1) | O(1) |
| Insert at Tail | O(1) | O(1) |
| Insert at Position | O(n) | O(1) |
| Delete from Head | O(1) | O(1) |
| Delete from Tail | O(1)* | O(1) |
| Delete at Position | O(n) | O(1) |
| Access | O(n) | O(1) |
| Search | O(n) | O(1) |
| Size | O(1)* | O(1) |
| Reverse | O(n) | O(1) |
| Get Middle | O(n) | O(1) |
Linked lists normally have to walk from the start to find a node. But if you already hold a pointer to a node, the work at that spot is fast. You can insert or delete in constant time from any position you have a pointer to. That's why linked lists shine when you keep references to important spots, like tracking both ends with sentinel nodes.
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). This simple design makes linked lists flexible. Unlike arrays, where elements are locked in place, linked list elements can connect and disconnect freely just by changing where their pointers aim.
- The
valueyou want to store (like a number or a word) - One or two
pointersthat 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 listsallow more flexibility. That's why linked lists show up as building blocks inside other data structures like queues and hashmaps.
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.
Working with pointers is all about doing things in the right order. When adding a new node, carefully update the pointers so you don't lose any connections. Set up the new node's connections first while it's still separate from the list, then splice it into the existing structure. This step-by-step approach is like connecting train cars: as long as you follow the order, you won't accidentally break anything or lose access to part of the 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
valholds the actual information you want to store, like a number or a word - The
nextpointer 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
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 nextpointers until they find what they're looking for.
Doubly linked lists 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
valholds the actual information you want to store, like a number or a word. - The
nextpointer shows the way to the next node, like an arrow pointing forward. - The
prevpointer 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.
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 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, also called dummy nodes, are a handy trick when working with linked lists. They don't hold real data. Instead, they sit at the start and end of the list as placeholders. Their job is to make inserting and deleting at the boundaries painless, so you don't have to write special edge-case logic for the head and tail.
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
The linked list starts with two dummy nodes: self.left and self.right. They form a fixed boundary around the list, so you never have to write special cases for an empty list, the head, or the tail. This removes the need to handle edge cases, and the result is cleaner code overall.
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:
Two Pointers
→A technique using two pointers to traverse data structures efficiently.
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.
Linked lists are all about pointer surgery. Work through these classic problems to build muscle memory for the patterns above — reversal, dummy nodes, fast/slow traversal, and design problems that combine multiple techniques: