🔗 Singly Linked List

Beginner to Intermediate ~15 min read

Arrays require contiguous memory and fixed size. What if you need dynamic growth? Enter Linked Lists - a chain of nodes connected by pointers. Each node holds data and a reference to the next node. Perfect for when you need O(1) insert/delete at the beginning!

The Chain of Nodes

What is a Linked List?

A linked list is a sequence of nodes where:

Each node contains: Data + Pointer to next node
Head: First node in the list
Tail: Last node (points to null)
Dynamic: Grows and shrinks as needed

head → [10|→] → [20|→] → [30|→] → null

Node Structure

The Building Block

class Node:
    def __init__(self, data):
        self.data = data  # Store value
        self.next = None  # Pointer to next node

That's it! Just data and a next pointer.

See It in Action

Watch how linked list operations work:

How Operations Work - Step by Step

Understanding linked list operations is crucial. Let's see exactly what happens during each operation, even if you don't play the animation!

1. Insert at HEAD - O(1)

Why O(1)? Only 3 steps!

Starting state:

HEAD → [10] → [20] → [30] → null

Want to insert 5 at HEAD:

Step 1: Create new node with value 5

[5] (new node, not connected yet)

Step 2: Point new node's next to current HEAD

[5] → [10] → [20] → [30] → null
                                        ↑
                                    (points to old HEAD)

Step 3: Update HEAD to point to new node

HEAD → [5] → [10] → [20] → [30] → null
       ✓ New HEAD!

Result: Done in 3 operations - O(1)! No matter how long the list is, always 3 steps.

2. Insert at TAIL - O(n)

Why O(n)? Must traverse entire list!

Starting state:

HEAD → [10] → [20] → [30] → null
                              ↑ TAIL

Want to insert 40 at TAIL:

Step 1: Create new node with value 40

[40] (new node, not connected yet)

Step 2: Traverse from HEAD to find TAIL

Visit [10] → not TAIL, continue
Visit [20] → not TAIL, continue
Visit [30] → next is null, this is TAIL!

Must visit every node - this is why it's O(n)!

Step 3: Point current TAIL's next to new node

HEAD → [10] → [20] → [30] → [40] → null
                              ↑ old TAIL  ↑ new TAIL

Result: If list has n nodes, must visit all n nodes - O(n)!

Optimization: Keep a tail pointer → makes this O(1)!

3. Delete HEAD - O(1)

Why O(1)? Just move pointer!

Starting state:

HEAD → [10] → [20] → [30] → null

Want to delete HEAD (10):

Step 1: Identify current HEAD

HEAD → [10] ← Delete this!
        ↓
       [20] → [30] → null

Step 2: Move HEAD pointer to next node

       [10] (will be garbage collected)
        
HEAD → [20] → [30] → null
       ✓ New HEAD!

Result: Done in 2 operations - O(1)! Old head is automatically garbage collected.

4. Search for Value - O(n)

Why O(n)? Must check each node!

Starting state:

HEAD → [10] → [20] → [30] → null

Want to find value 20:

Step 1: Start at HEAD, check value

HEAD → [10] ← Check: 10 == 20? No, continue
        ↓
       [20] → [30] → null

Step 2: Move to next, check value

HEAD → [10] → [20] ← Check: 20 == 20? YES! Found it!
               ↓
              [30] → null

Result: Worst case: value is at end or not found - must check all n nodes - O(n)!

Best case: Value is at HEAD - O(1)

Average case: Value is in middle - O(n/2) = O(n)

5. Delete TAIL - O(n)

Why O(n)? Must find second-to-last node!

Starting state:

HEAD → [10] → [20] → [30] → null
                              ↑ TAIL

Want to delete TAIL (30):

Problem: We need to set [20]'s next to null, but we can't go backwards!

Solution: Traverse to find second-to-last node

Visit [10] → next.next exists, continue
Visit [20] → next.next is null, this is second-to-last!

Step 2: Set second-to-last's next to null

HEAD → [10] → [20] → null
                      ↑ new TAIL
              
              [30] (will be garbage collected)

Result: Must traverse to find second-to-last - O(n)!

This is why doubly linked lists exist! They have prev pointers.

Key Insights

💡 Understanding the Patterns

O(1) operations: Work with HEAD directly (insert/delete at head)
O(n) operations: Need to traverse the list (anything with TAIL, search)
Why no backwards? Singly linked list only has "next" pointer, not "prev"
Memory trade-off: Each node needs extra space for the "next" pointer

The Code

"""
Singly Linked List - Basics
Foundation for all linked list problems
Time complexities for each operation included
"""

class Node:
    """Node in a singly linked list"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """Singly Linked List implementation"""
    def __init__(self):
        self.head = None
    
    def is_empty(self):
        """Check if list is empty - O(1)"""
        return self.head is None
    
    def insert_at_head(self, data):
        """Insert at beginning - O(1)"""
        print(f"Inserting {data} at head")
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        print(f"✓ Inserted {data} at head")
    
    def insert_at_tail(self, data):
        """Insert at end - O(n)"""
        print(f"Inserting {data} at tail")
        new_node = Node(data)
        
        if self.is_empty():
            self.head = new_node
            print(f"✓ List was empty, {data} is now head")
            return
        
        # Traverse to end
        current = self.head
        steps = 0
        while current.next:
            current = current.next
            steps += 1
        
        current.next = new_node
        print(f"✓ Inserted {data} at tail (traversed {steps} nodes)")
    
    def insert_at_position(self, data, position):
        """Insert at specific position - O(n)"""
        print(f"Inserting {data} at position {position}")
        
        if position == 0:
            self.insert_at_head(data)
            return
        
        new_node = Node(data)
        current = self.head
        
        # Traverse to position-1
        for i in range(position - 1):
            if current is None:
                print(f"✗ Position {position} out of bounds")
                return
            current = current.next
        
        if current is None:
            print(f"✗ Position {position} out of bounds")
            return
        
        new_node.next = current.next
        current.next = new_node
        print(f"✓ Inserted {data} at position {position}")
    
    def delete_head(self):
        """Delete first node - O(1)"""
        if self.is_empty():
            print("✗ Cannot delete from empty list")
            return None
        
        data = self.head.data
        self.head = self.head.next
        print(f"✓ Deleted head: {data}")
        return data
    
    def delete_tail(self):
        """Delete last node - O(n)"""
        if self.is_empty():
            print("✗ Cannot delete from empty list")
            return None
        
        if self.head.next is None:
            data = self.head.data
            self.head = None
            print(f"✓ Deleted only node: {data}")
            return data
        
        # Traverse to second-last node
        current = self.head
        while current.next.next:
            current = current.next
        
        data = current.next.data
        current.next = None
        print(f"✓ Deleted tail: {data}")
        return data
    
    def delete_value(self, value):
        """Delete first occurrence of value - O(n)"""
        print(f"Deleting value: {value}")
        
        if self.is_empty():
            print("✗ List is empty")
            return False
        
        # If head contains value
        if self.head.data == value:
            self.head = self.head.next
            print(f"✓ Deleted {value} from head")
            return True
        
        # Search for value
        current = self.head
        while current.next:
            if current.next.data == value:
                current.next = current.next.next
                print(f"✓ Deleted {value}")
                return True
            current = current.next
        
        print(f"✗ Value {value} not found")
        return False
    
    def search(self, value):
        """Search for value - O(n)"""
        print(f"Searching for: {value}")
        current = self.head
        position = 0
        
        while current:
            if current.data == value:
                print(f"✓ Found {value} at position {position}")
                return position
            current = current.next
            position += 1
        
        print(f"✗ Value {value} not found")
        return -1
    
    def get_length(self):
        """Get list length - O(n)"""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count
    
    def print_list(self):
        """Print list - O(n)"""
        if self.is_empty():
            print("List: (empty)")
            return
        
        current = self.head
        elements = []
        while current:
            elements.append(str(current.data))
            current = current.next
        
        print(f"List: {' -> '.join(elements)} -> None")
    
    def reverse(self):
        """Reverse the list - O(n)"""
        print("Reversing list...")
        prev = None
        current = self.head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        
        self.head = prev
        print("✓ List reversed")

# Example 1: Basic Operations
print("=" * 70)
print("Example 1: Basic Linked List Operations")
print("=" * 70)

ll = LinkedList()
print("\n1. Insert at head:")
ll.insert_at_head(3)
ll.insert_at_head(2)
ll.insert_at_head(1)
ll.print_list()

print("\n2. Insert at tail:")
ll.insert_at_tail(4)
ll.insert_at_tail(5)
ll.print_list()

print("\n3. Insert at position:")
ll.insert_at_position(2.5, 2)
ll.print_list()

print(f"\n4. List length: {ll.get_length()}")

# Example 2: Search Operations
print("\n" + "=" * 70)
print("Example 2: Search Operations")
print("=" * 70)
ll.print_list()
ll.search(3)
ll.search(10)

# Example 3: Delete Operations
print("\n" + "=" * 70)
print("Example 3: Delete Operations")
print("=" * 70)
ll.print_list()

print("\n1. Delete head:")
ll.delete_head()
ll.print_list()

print("\n2. Delete tail:")
ll.delete_tail()
ll.print_list()

print("\n3. Delete specific value:")
ll.delete_value(3)
ll.print_list()

# Example 4: Reverse
print("\n" + "=" * 70)
print("Example 4: Reverse List")
print("=" * 70)
ll.print_list()
ll.reverse()
ll.print_list()

# Example 5: Build from scratch
print("\n" + "=" * 70)
print("Example 5: Build List from Array")
print("=" * 70)

def build_list_from_array(arr):
    """Build linked list from array"""
    ll = LinkedList()
    for val in arr:
        ll.insert_at_tail(val)
    return ll

arr = [10, 20, 30, 40, 50]
print(f"Array: {arr}")
ll2 = build_list_from_array(arr)
ll2.print_list()

# Complexity Summary
print("\n" + "=" * 70)
print("Time Complexity Summary")
print("=" * 70)
print(f"{'Operation':<25} {'Time':<15} {'Why':<30}")
print("-" * 70)
print(f"{'Insert at head':<25} {'O(1)':<15} {'Direct pointer update':<30}")
print(f"{'Insert at tail':<25} {'O(n)':<15} {'Must traverse to end':<30}")
print(f"{'Insert at position':<25} {'O(n)':<15} {'Must traverse to position':<30}")
print(f"{'Delete head':<25} {'O(1)':<15} {'Direct pointer update':<30}")
print(f"{'Delete tail':<25} {'O(n)':<15} {'Must find second-last':<30}")
print(f"{'Delete value':<25} {'O(n)':<15} {'Must search for value':<30}")
print(f"{'Search':<25} {'O(n)':<15} {'Must traverse list':<30}")
print(f"{'Get length':<25} {'O(n)':<15} {'Must count all nodes':<30}")
print(f"{'Reverse':<25} {'O(n)':<15} {'Must visit all nodes':<30}")

# Linked List vs Array
print("\n" + "=" * 70)
print("Linked List vs Array")
print("=" * 70)
print(f"{'Operation':<25} {'Array':<15} {'Linked List':<15}")
print("-" * 70)
print(f"{'Access by index':<25} {'O(1) ✓':<15} {'O(n)':<15}")
print(f"{'Insert at head':<25} {'O(n)':<15} {'O(1) ✓':<15}")
print(f"{'Insert at tail':<25} {'O(1) ✓':<15} {'O(n) or O(1)*':<15}")
print(f"{'Delete at head':<25} {'O(n)':<15} {'O(1) ✓':<15}")
print(f"{'Search':<25} {'O(n)':<15} {'O(n)':<15}")
print(f"{'Memory':<25} {'Contiguous ✓':<15} {'Scattered':<15}")
print(f"{'Size':<25} {'Fixed':<15} {'Dynamic ✓':<15}")

print("\n* O(1) with tail pointer")

print("\n" + "=" * 70)
print("Key Takeaways")
print("=" * 70)
print("✓ Linked List: Dynamic size, O(1) insert/delete at head")
print("✓ Array: O(1) random access, contiguous memory")
print("✓ Use Linked List when: Frequent insert/delete at beginning")
print("✓ Use Array when: Need random access, memory locality")
print("\n✓ Master linked lists - foundation for stacks, queues, graphs!")

Output

Click Run to execute your code

Quick Quiz

Why is insert at head O(1) but insert at tail O(n)?

Show answer
Insert at head: Just create new node, point it to current head, update head pointer - 3 operations, O(1)! Insert at tail: Must traverse entire list to find last node - O(n) operations. (Can be O(1) with tail pointer!)
When would you use a linked list instead of an array?

Show answer
Use linked list when: (1) Frequent insert/delete at beginning, (2) Don't know size in advance, (3) Don't need random access. Use array when: (1) Need O(1) access by index, (2) Size is known, (3) Memory locality matters.

Complexity Analysis

Operation	Time	Why
Insert at head	O(1) ✓	Direct pointer update
Insert at tail	O(n)	Must traverse to end
Delete head	O(1) ✓	Move head to next
Delete tail	O(n)	Must find second-last
Search	O(n)	Must check each node
Access by index	O(n)	Must traverse from head
Space	O(n)	Extra space for pointers

Linked List vs Array

Feature	Array	Linked List
Access by index	O(1) ✓	O(n)
Insert at head	O(n)	O(1) ✓
Insert at tail	O(1) ✓	O(n) or O(1)*
Delete at head	O(n)	O(1) ✓
Memory	Contiguous ✓	Scattered
Size	Fixed	Dynamic ✓
Cache locality	Better ✓	Worse

* O(1) with tail pointer

When to Use Linked Lists

✅ Use Linked List When:

Frequent insert/delete at beginning: O(1) operations!
Unknown size: Dynamic growth
Implementing stacks/queues: Perfect fit
No random access needed: Sequential access is fine

❌ Use Array Instead When:

Need random access: Array is O(1), list is O(n)
Cache locality matters: Arrays are contiguous
Memory overhead matters: Pointers use extra space
Size is known: Arrays are simpler

Common Mistakes

❌ Losing References

# WRONG - loses rest of list!
head = head.next  # Old head is lost!

# RIGHT - save reference first
temp = head
head = head.next
# Can still access temp if needed

❌ Not Checking for NULL

# WRONG - crashes if list is empty!
print(head.data)

# RIGHT - check first
if head is not None:
    print(head.data)

💡 Key Takeaway

Singly Linked List is the foundation for dynamic data structures:

✅ O(1) insert/delete at head - faster than arrays!
✅ Dynamic size - grows as needed
✅ Foundation for stacks, queues, graphs
⚠️ O(n) access by index - slower than arrays
⚠️ Extra memory for pointers

Master pointers - they're everywhere in interviews!

Summary

The 3-Point Linked List Guide

Structure: Chain of nodes, each with data + next pointer
Strength: O(1) insert/delete at head, dynamic size
Weakness: O(n) access by index, no cache locality

Interview tip: Always check for null pointers! Draw the list on paper to visualize pointer changes. Most linked list bugs are from losing references or null pointer errors.

What's Next?

You've learned the basics! Next: Linked List Reversal - one of the most common interview problems!

Practice: Implement a linked list from scratch. Try reversing it. Practice on paper first - draw the pointers!

Previous Exponential Search

Next Linked List Reversal

The Chain of Nodes

What is a Linked List?

Node Structure

The Building Block

See It in Action

How Operations Work - Step by Step

1. Insert at HEAD - O(1)

Why O(1)? Only 3 steps!

2. Insert at TAIL - O(n)

Why O(n)? Must traverse entire list!

3. Delete HEAD - O(1)

Why O(1)? Just move pointer!

4. Search for Value - O(n)

Why O(n)? Must check each node!

5. Delete TAIL - O(n)

Why O(n)? Must find second-to-last node!

Key Insights

💡 Understanding the Patterns

The Code

Quick Quiz

Complexity Analysis

Linked List vs Array

When to Use Linked Lists

✅ Use Linked List When:

❌ Use Array Instead When:

Common Mistakes

❌ Losing References

❌ Not Checking for NULL

💡 Key Takeaway

Summary

The 3-Point Linked List Guide

What's Next?

Enjoying these tutorials?