Back to: Python Data Structure and Algorithims

Linked Lists and Big O Notation Explained (with Examples)

When we study data structures, it’s not just about how they’re built — it’s also about how efficiently they perform certain operations. That’s where Big O notation comes in.

In this blog, we’ll walk through the time complexities (Big O) of all the major operations you can perform on a Linked List, step by step.

---

🧠 Quick Recap: What’s a Linked List?

A linked list is a sequence of nodes.
Each node contains:

• A data field (the actual value)

• A next pointer (the reference to the next node)

Example structure:

• The head points to the first node.

• The tail points to the last node.

• The last node’s next is always None (end of list).

---

⚙️ Common Linked List Operations and Their Big O

Let’s analyze each operation one by one.

---

1️⃣ Append (Add a Node at the End)

Goal: Add a new node to the end of the list.

Logic:

• The current tail.next points to the new node.

• The new node becomes the new tail.

Python Example:

Time Complexity: O(1)

Why?
No matter how long the list is, we already have a reference to the tail.
It takes the same number of steps to connect one new node.

✅ Constant time operation

---

2️⃣ Remove from the End

Goal: Delete the last node from the list.

Logic:
To remove the last node, we must find the second-last node and make it the new tail.
But here’s the issue — we don’t have a direct pointer to the second-last node.

So, we must start from the head and iterate through the entire list until we reach the node right before the tail.

Python Example:

Time Complexity: O(n)

Why?
We must traverse the entire list to find the node before the tail.
As the list grows, the time grows linearly.

---

3️⃣ Add at the Beginning (Prepend)

Goal: Add a node at the start of the list.

Logic:

• Point the new node’s next to the current head.

• Move the head to the new node.

Python Example:

Time Complexity: O(1)

Why?
We only adjust a couple of pointers — it doesn’t matter if the list has 3 nodes or 3 million.
✅ Constant time

---

4️⃣ Remove from the Beginning

Goal: Remove the first node.

Logic:

• Move head to the next node (head = head.next).

• The previous first node is now disconnected.

Python Example:

Time Complexity: O(1)

Why?
Only one pointer (head) is updated.
✅ Constant time

---

5️⃣ Insert in the Middle

Goal: Add a new node after a specific position or node.

Logic:

• Traverse the list to find the target position.

• Change the pointers accordingly.

Python Example:

Time Complexity: O(n)

Why?
We have to search for the target node before inserting.
If it’s near the end, we may traverse the entire list.

---

6️⃣ Remove from the Middle

Goal: Delete a specific node (by value).

Logic:

• Traverse the list until the node before the target is found.

• Redirect its next pointer to skip the node being removed.

Python Example:

Time Complexity: O(n)

Why?
We must traverse until we find the node before the one we want to delete.

---

7️⃣ Lookup / Search

Goal: Find a value or index in the list.

Logic:
Start from the head and move one node at a time until you find the value.

Python Example:

Time Complexity: O(n)

Why?
You may need to traverse the entire list to find the item.

---

📊 Comparison: Linked List vs Python List (Array)

⭐ Key takeaway:

• Linked lists are great for quick insertions or deletions at the beginning.

• Python lists (arrays) are better for quick random access or removal at the end.

---

🧩 Visualization Example

Let’s visualize inserting and deleting:

➕ Adding at the Front

Before:

After adding 5:

✅ Constant time

---

➖ Removing from the End

Before:

After removing 30:

❌ Requires traversal → O(n)

---

🧠 Final Summary