Linked Lists
Data elements connected together via links.
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, allowing nodes to be stored in any available memory location. This structure allows for quick insertion or deletion of nodes anywhere in the linked list without reorganizing the entire data structure.
Singly linked lists are great for quick operations at the beginning. You can add or remove items at the beginning in constant time. Each list node connects to the next node with a pointer, letting you move through the list step-by-step. You can also easily split or join lists by changing just 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) |
While linked lists need to traverse from the start to find a node, if you have a direct reference to any node in the list, you can perform quick operations there. Just like how you can easily add or remove from the beginning, you can insert or delete nodes in constant time from any position where you have a pointer. This makes linked lists efficient when you maintain references to important positions in your list, like keeping track of both ends with sentinel nodes.
A linked list node is like a box with two compartments: one to store your data (called value), and another to point 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 by just changing where their pointers aim.
- The
valueyou want to store (like a number or a word) - One or two
pointersthat shows the way to other connected nodes
The beauty of nodes is how they can work together to create different structures. By changing how nodes point to each other, we can create different types of linked lists - from simple chains where nodes only point forward, to morecomplex structures like circular lists or doubly linked lists. This flexibility is why linked lists are often used as building blocks for other data structures like queues and hashmaps.
Pointers are like threads that stitch nodes together into a connected chain. Unlike arrays where elements are placed side by side in memory, linked lists use these pointers to create flexible connections between nodes that can be anywhere in memory. This design makes insertion and deletion operations much simpler - instead of shifting many elements like in an array, we just need to reconnect a few pointers to change the list's structure.
Working with pointers is all about managing connections in the right order. When adding a new node, we must carefully update the pointers to avoid losing any connections. First, we set up all the new node's connections while it's still separate" from our list, then we connect it to the existing structure. This methodical approach, like connecting train cars, ensures we don't accidentally break any existing connections or lose access to parts of our list.
Singly linked lists are like a scavenger hunt where each clue only points to the next location. This simple, one-way structure makes them easy to understand and implement. While you can only move forward through the list, this simplicity makes them perfect for basic data storage and simple traversal needs.
- 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 strength of singly linked lists lies in their simplicity and efficiency. They use less memory than doubly linked lists since each node only needs one pointer, and operations at the beginning of the list are extremely fast. However, you need to be careful about keeping track of positions - once you move past a node, there's no way to go back.
Singly Linked List
# 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 our list. This boundary is important because it tells us when to stop traversing and helps prevent errors. Unlike arrays that can instantly jump to any position, singly linked lists must always start at the beginning and follow the next pointers until they find what they're looking for.
Doubly linked lists are an upgrade to singly linked lists because each node can look both forward and backward . Think of it like a train where each railcar can connect to both the railcars in front and behind it. This bidirectional movement makes many operations more efficient, allowing us to even traverse 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.
However, these benefits come at a cost: doubly linked lists use more memory because each node needs an extra pointer. They're also more complex to maintain since every insertion and deletion needs to update both next and prev pointers correctly. Despite these tradeoffs, the added flexibility often makes doubly linked lists the better choice when you need to traverse your data in both directions or perform frequent deletions.
Doubly Linked List
# 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, creating clear boundaries for our list. This double-linked structure makes deleting nodes much easier than in singly linked lists - we don't need to keep track of the previous node during traversal because it's already connected.
Sentinel nodes, also known as dummy nodes, are a useful technique in linked lists. These nodes don't actually contain useful data but rather serve as placeholders at the start and end of the list. They eliminate the need to handle annoying edge cases when inserting or deleting elements at the list's beginning or end.
Sentinel Nodes
# 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. These nodes create a fixed boundary around the linked list. This setup eliminates the need to handle edge cases in linked list operations, simplifying the overall code.
Linked lists are important to understand because they are the foundation for many other data structures, including hashmaps and queues. Here are essential tips and tricks for linked lists: