Singly linked list structure in Data Structures Theory - Time & Space Complexity

Time Complexity: Singly linked list structure

O(n)

Understanding Time Complexity

When working with a singly linked list, it is important to understand how the time needed to perform operations changes as the list grows.

We want to know how the time to find or access elements changes as the list gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def find(self, target):
        current = self.head
        while current is not None:
            if current.value == target:
                return True
            current = current.next
        return False
    

This code defines a singly linked list and a method to find if a value exists by checking each node one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each node in the list one by one.
• How many times: Up to once for every node until the target is found or the list ends.

How Execution Grows With Input

As the list gets longer, the time to find a value grows roughly in direct proportion to the number of nodes.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The work grows steadily as the list grows longer, checking each node one after another.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a value grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Finding a value in a singly linked list is as fast as in an array because both store data."

[OK] Correct: Unlike arrays, singly linked lists do not allow direct access by position, so you must check nodes one by one, making it slower for searching.

Interview Connect

Understanding how linked lists work and their time costs helps you explain data structure choices clearly and solve problems efficiently.

Self-Check

"What if we added a pointer to the tail node? How would that affect the time complexity of finding a value?"