DSA Fundamentals: Linked Lists - Mastering Dynamic Data Structures

Linked Lists are fundamental data structures that overcome key limitations of arrays, particularly when it comes to insertion and deletion operations. This comprehensive guide explores linked list theory and demonstrates essential patterns through practical LeetCode solutions.

Understanding Linked Lists: Core Concepts

What is a Linked List?

A Linked List is a linear data structure where elements (nodes) are stored in non-contiguous memory locations. Each node contains:

• Value: The data being stored
• Pointer: Reference to the next node in the sequence

This non-contiguous memory allocation is the fundamental difference from arrays, enabling efficient insertions and deletions.

Linked List vs Array Comparison

Operation	Array	Linked List
Random Access	O(1)	O(n)
Search	O(n)	O(n)
Insertion at Beginning	O(n)	O(1)
Insertion at End	O(1)*	O(n) or O(1)**
Deletion at Beginning	O(n)	O(1)
Memory	Contiguous	Non-contiguous

*Amortized for dynamic arrays
**O(1) if tail pointer is maintained

Types of Linked Lists

Singly Linked List:

• One-directional traversal (head → tail)
• Each node points to the next node
• Less memory overhead

Doubly Linked List:

• Bi-directional traversal
• Each node has next and prev pointers
• More flexible but requires more memory

# Singly Linked List Node Definition
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Doubly Linked List Node Definition
class DoublyListNode:
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

Essential Linked List Patterns

Pattern 1: Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list and return the reversed list.

Approach: Use three pointers (prev, curr, tmp) to iteratively reverse the direction of each node's pointer.

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        prev = None
        curr = head

        while curr:
            tmp = curr.next      # Save next node
            curr.next = prev     # Reverse pointer
            prev = curr          # Move prev forward
            curr = tmp           # Move curr forward

        return prev  # prev is the new head

Key Insight: Reversing requires maintaining three pointers to avoid losing references during pointer manipulation.

Pattern 2: Detect Cycle (Floyd's Tortoise and Hare)

Problem: Given a linked list, detect if the list has a cycle.

Approach: Use two pointers moving at different speeds. If there's a cycle, the fast pointer will eventually catch up to the slow pointer.

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Floyd's Cycle Detection Algorithm
        # Use two pointers: slow (1 step) and fast (2 steps)

        slow, fast = head, head

        while fast and fast.next:
            fast = fast.next.next  # Move fast by 2
            slow = slow.next       # Move slow by 1

            if slow == fast:       # Pointers met = cycle exists
                return True

        return False  # fast reached end = no cycle

Key Insight: Floyd's algorithm is elegant because it uses O(1) space instead of a hash set, and the fast pointer will always catch the slow pointer if a cycle exists.

Pattern 3: Merge Two Sorted Lists

Problem: Merge two sorted linked lists into one sorted list.

Approach: Use a dummy node and compare values from both lists, attaching the smaller node to the result list.

Time Complexity: O(n + m)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return None

        # Dummy node to simplify edge cases
        dummy = ListNode()
        curr = dummy

        # Compare and merge
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                curr = curr.next
                list1 = list1.next
            else:
                curr.next = list2
                curr = curr.next
                list2 = list2.next

        # Attach remaining nodes
        curr.next = list1 if list1 else list2

        return dummy.next  # Skip dummy node

Key Insight: The dummy node technique simplifies handling edge cases and eliminates special logic for the first node.

Pattern 4: Remove Nth Node From End

Problem: Remove the nth node from the end of a linked list.

Approach: Use two pointers with a gap of n+1 nodes. When the fast pointer reaches the end, the slow pointer will be at the node before the target.

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head

        slow, fast = dummy, dummy

        # Create gap of n+1 between pointers
        for _ in range(n + 1):
            fast = fast.next

        # Move both pointers until fast reaches end
        while fast:
            fast = fast.next
            slow = slow.next

        # Remove the nth node
        slow.next = slow.next.next

        return dummy.next

Key Insight: The two-pointer technique with proper gap allows single-pass removal without knowing the list length.

Pattern 5: Add Two Numbers

Problem: You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.

Time Complexity: O(max(n, m))

Space Complexity: O(max(n, m))

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy
        carry = 0

        while l1 or l2 or carry:
            l1_val = l1.val if l1 else 0
            l2_val = l2.val if l2 else 0

            curr_sum = l1_val + l2_val + carry
            carry = curr_sum // 10
            digit = curr_sum % 10

            curr.next = ListNode(digit)
            curr = curr.next

            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

Key Insight: Handle carry properly and continue while any value exists (l1, l2, or carry).

Pattern 6: Reorder List

Problem: Given a singly linked list L: L₀ → L₁ → ... → Lₙ₋₁ → Lₙ, reorder it to: L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → ...

Approach:

1. Find middle using fast/slow pointers
2. Reverse second half
3. Merge two halves alternately

Time Complexity: O(n)

Space Complexity: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Step 1: Find middle
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # Step 2: Reverse second half
        curr = slow.next
        prev = slow.next = None  # Split the list

        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp

        # Step 3: Merge two halves
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next, second.next = second, tmp1
            first, second = tmp1, tmp2

Key Insight: Combines three patterns: find middle, reverse list, and merge lists.

Pattern 7: Copy List with Random Pointer

Problem: A linked list has both next and random pointers. Create a deep copy of the list.

Approach: Use a hash map to store old → new node mappings, then connect pointers in a second pass.

Time Complexity: O(n)

Space Complexity: O(n)

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: 
            return None

        # First pass: Create all nodes and store in hash map
        h_map = {}
        curr = head

        while curr:
            new_node = Node(curr.val)
            h_map[curr] = new_node
            curr = curr.next

        # Second pass: Connect next and random pointers
        curr = head
        while curr:
            if curr.next:
                h_map[curr].next = h_map[curr.next]
            if curr.random:
                h_map[curr].random = h_map[curr.random]
            curr = curr.next

        return h_map[head]

Key Insight: Two-pass algorithm separates node creation from pointer connections, simplifying complex pointer relationships.

Common Linked List Techniques

1. Dummy Node Pattern

• Simplifies edge cases (empty list, single node)
• Eliminates special handling for head node
• Used in: merge lists, insertion, deletion

2. Two Pointer Pattern

• Fast/Slow (Floyd's algorithm): cycle detection, find middle
• Gap pointers: remove nth from end
• Different speeds reveal structural properties

3. Reversal Pattern

• Essential for many problems
• Can reverse entire list or subsections
• Often combined with other patterns

4. Hash Map for Complex Pointers

• Track node relationships
• Deep copy problems
• O(n) space tradeoff for simpler logic

When to Use Linked Lists

Advantages:

• ✅ Efficient insertions/deletions at beginning (O(1))
• ✅ Dynamic size (no pre-allocation needed)
• ✅ Efficient memory usage for sparse data
• ✅ Natural fit for queue/stack implementations

Disadvantages:

• ❌ No random access (must traverse from head)
• ❌ Extra memory for pointers
• ❌ Poor cache locality
• ❌ Traversal is O(n) for any position

Practice Strategy

1. Master the basics first:

   • Reverse Linked List
   • Detect Cycle
   • Merge Two Lists

2. Learn pointer manipulation:

   • Practice drawing pointer diagrams
   • Understand null checks
   • Handle edge cases (empty, single node)

3. Recognize patterns:

   • Dummy node usage
   • Two-pointer techniques
   • When to use hash maps

4. Advanced problems:

   • Combine multiple patterns
   • Handle complex pointer relationships
   • Optimize space complexity

Key Takeaways

1. Linked Lists excel at insertions/deletions but sacrifice random access
2. Non-contiguous memory enables O(1) modifications without shifting elements
3. Two-pointer techniques are powerful for cycle detection and finding middle
4. Dummy nodes simplify edge case handling
5. Practice pointer manipulation through visualization and careful null checking

Linked lists may seem simple, but mastering pointer manipulation and recognizing common patterns is crucial for technical interviews and real-world applications like LRU caches, undo functionality, and graph representations.

---

Continue your DSA journey by exploring more data structures and algorithms. Practice these patterns on LeetCode and gradually increase problem difficulty to build mastery.