Module 3.1 ⏱ 35 min read ⚡ Pointer-Based Structures

Singly & Doubly Linked Lists

Kick off Module 3 by exploring non-contiguous memory allocations, pointer manipulation mechanics, and classic traversal algorithms.

1. Node Structure & Memory Mechanics

Unlike arrays that require continuous blocks of RAM, a linked list consists of independent nodes scattered across memory. Each node stores data along with one or more references (pointers) to neighboring nodes. Because elements are not indexed adjacently, random access requires $O(n)$ linear traversal.

Singly vs. Doubly Linked Lists: Singly linked list nodes contain a single `next` pointer pointing forward. Doubly linked lists add a `prev` pointer, enabling bidirectional traversal and $O(1)$ deletions given a direct node reference at the cost of extra memory overhead.

2. Insertions, Deletions & Finding Midpoints

Inserting or deleting nodes at the head of a linked list takes $O(1)$ time because you only need to reroute pointer references. Finding the midpoint of a list without knowing its length ahead of time is efficiently achieved using the fast and slow pointer technique.

3. Cycle Detection (Floyd's Tortoise and Hare Algorithm)

To determine if a linked list contains a circular loop, Floyd's cycle-finding algorithm deploys two pointers traversing at different speeds: a slow pointer moving one step at a time and a fast pointer moving two steps. If the pointers meet, a cycle is guaranteed to exist.

// C++ Solution: Reverse a Linked List In-Place
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};
            

# Python Solution: Reverse a Linked List In-Place
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev
            

// Java Solution: Reverse a Linked List In-Place
public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}
            

4. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for reversing a linked list and detecting/removing cycles using Floyd's algorithm.

Quick Check: Test Your Intuition

What is the time complexity of reversing a singly linked list iteratively in-place?