Introduction
A singly linked list is a linear collection of nodes where each node stores a value and a reference (pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory, so growing or shrinking the list does not require shifting elements. The list is accessed through a single reference called the head, and the last node's next pointer is None, marking the end of the list.
Cricket analogy: A singly linked list is like a chain of relay messages passed from one fielder to the next, each only knowing who to throw to next, so adding or dropping a fielder from the chain doesn't require reshuffling the whole outfield the way changing a fixed batting order would.
Structure/Syntax
class Node:
def __init__(self, value):
self.value = value
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
self.size = 0
def is_empty(self):
return self.head is NoneExplanation
Each Node object bundles a value with a next reference. The SinglyLinkedList class keeps track of the head node, which is the entry point for all traversals. Because each node only knows about the node after it, traversal is strictly forward: to reach the third node, you must walk through the first and second nodes. Insertion at the head is O(1) because it only requires creating a new node and rewiring one pointer, while insertion at the tail or at an arbitrary position requires O(n) traversal to find the insertion point.
Cricket analogy: Each fielder in the relay chain knows only the next fielder to throw to, and the captain (head) is the entry point for any relay; to reach the third fielder, the ball must pass through the first two, so adding a new first fielder is instant O(1) rewiring, while inserting mid-chain requires walking through the earlier throws in O(n).
Example
class SinglyLinkedList:
def __init__(self):
self.head = None
self.size = 0
def push_front(self, value):
node = Node(value)
node.next = self.head
self.head = node
self.size += 1
def push_back(self, value):
node = Node(value)
if self.head is None:
self.head = node
else:
current = self.head
while current.next is not None:
current = current.next
current.next = node
self.size += 1
def to_list(self):
result = []
current = self.head
while current is not None:
result.append(current.value)
current = current.next
return result
class Node:
def __init__(self, value):
self.value = value
self.next = None
sll = SinglyLinkedList()
sll.push_back(10)
sll.push_back(20)
sll.push_front(5)
print(sll.to_list())Complexity
push_front runs in O(1) time since it only touches the head pointer. push_back and to_list run in O(n) time because they must traverse the entire list. Searching for a value is also O(n) in the worst case. Space complexity is O(n) for storing n nodes, plus O(1) extra space for most operations since no additional data structures are used.
Cricket analogy: Sending a new opening batsman in is O(1) since only the top of the order changes, but adding a batsman at the end of the lineup or checking if a specific player is anywhere in the order takes O(n) because you must walk the whole batting chain, and the chain itself needs O(n) space with no extra scoreboard structures.
Key Takeaways
- A singly linked list node stores a value and a single 'next' pointer to the following node.
- Insertion and deletion at the head are O(1); operations at the tail or middle are O(n) without a tail pointer.
- Random access by index is O(n) because there is no direct indexing like arrays.
- Keeping a separate tail reference can make push_back O(1) as well.
- Singly linked lists use less memory per node than doubly linked lists since they store only one pointer.
Practice what you learned
1. What is the time complexity of inserting a new node at the head of a singly linked list?
2. What does the 'next' pointer of the last node in a singly linked list typically point to?
3. Why is accessing the k-th element of a singly linked list O(n) instead of O(1) like an array?
4. In the SinglyLinkedList example, why does push_back require a full traversal without a tail pointer?
Was this page helpful?
You May Also Like
Doubly Linked Lists
A linked list where each node has both next and previous pointers, allowing efficient bidirectional traversal.
Circular Linked Lists
A linked list variant where the last node points back to the first, forming a continuous loop with no None end.
Linked List Operations and Problems
Classic linked list algorithms including reversal, cycle detection with Floyd's algorithm, and finding the middle node.
Arrays in Data Structures
How arrays store elements in contiguous memory and why that layout drives their performance characteristics.