Singly Linked Lists

Analogy categoryAnalogies

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

python

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 None

Explanation

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

python

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?

Doubly Linked Lists

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#SinglyLinkedLists#Singly#Linked#Lists#Structure#StudyNotes#SkillVeris