Data Structures Linked Lists
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.
Linked lists are great for quick operations. You can add or remove items at the beginning in constant time. Inserting or deleting in the middle is also fast if you know where to do it. Each list node connects to the next 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 | O(1) | O(1) |
| Delete | O(1) | O(1) |
| Access | O(n) | O(1) |
| Search | O(n) | O(1) |
| Size | O(n) | O(1) |
List Nodes are the building blocks of linked lists. They're like containers that hold two things:
- The
valueyou want to store (like a number or a word) - One or two
pointersthat shows the way to other connected nodes
This simple design makes linked lists really flexible. You can easily add or remove nodes by just changing where the pointers aim. It's like rearranging a chain by reconnecting the links. This setup lets you quickly insert or delete items, even in the middle of the list, if you know where to do it.
Pointers are crucial for constructing linked lists, allowing each node to connect to the next. Linked lists efficiently perform insertions and deletions by simply updating links between nodes, without needing to shift elements like in arrays.
The example above shows how to insert a new ListNode after the head of a linked list. It starts by creating a new list node with the given value. Then, it sets this new node's next pointer to the node after head. Finally, head's next pointer is set to the new_node effectively placing the new node at the front.
Singly linked lists are the simplest type of linked list. In this structure, each node is like a container with two parts:
- 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 last node's pointer points to nothing (aka null), which tells us we've reached the end of the list. This simple design lets us easily add or remove nodes by just changing where the pointers aim:
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
Doubly linked lists are an upgrade to singly linked lists because each node has three parts instead of two:
- 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 first node's prev pointer and the last node's next pointer both point to null. This design allows us to traverse the list in both directions and makes certain operations, like deleting a node, more efficient.
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
Sentinel nodes, also known as dummy nodes, are a useful technique in linked lists. These nodes contain no actual data but serve as placeholders at the start and end of the list. They eliminate the need to handle special 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: