18  Linked Lists

19 Linked Lists

Week 8, Session 2. CSS 342.

19.1 Warmup

Reverse Linked List (#206). Given the head of a singly linked list, reverse it and return the new head.

struct ListNode {
  int val;
  ListNode* next;
  ListNode(int v) : val(v), next(nullptr) {}
};

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

The pointer dance: save next, redirect curr->next, advance prev and curr. If you can write this from memory by week 9, you have internalized linked lists.

19.2 Learning objectives

  1. Implement a singly linked list with insert, delete, and traversal operations.
  2. Manage heap memory for nodes correctly (no leaks, no dangling pointers).
  3. Implement the Rule of Three for a linked list class.
  4. Compare linked list vs. std::vector operation complexities.
  5. Draw a pointer diagram representing a linked list state before and after mutation.

19.3 Why a linked list?

A vector is a contiguous array. Inserting at the front shifts everything — O(n). A linked list is a chain of nodes, each pointing to the next. Insert at the front: change one pointer — O(1).

Operation vector linked list
Index access O(1) O(n)
Insert at front O(n) O(1)
Insert at back O(1) amortized O(n) (unless you keep a tail pointer)
Insert at middle O(n) O(n) to find, O(1) to insert
Delete at front O(n) O(1)
Memory locality Excellent Poor

In practice vector wins almost always — the memory locality gap is huge on modern hardware. But linked lists are the right shape for many algorithms (LRU caches, undo stacks, BFS/DFS state), and they are the entry point for understanding trees and graphs.

19.4 The Node

struct Node {
  int data;
  Node* next;
  Node(int v) : data(v), next(nullptr) {}
};

A struct is a class where everything is public by default. For tiny data-holding types like Node, that is what we want.

A chain of three nodes, drawn:

head → [10|·] → [20|·] → [30|·] → nullptr

Each box is a node. Each · is the next pointer.

19.5 Insert at front — O(1)

void insertFront(Node*& head, int value) {
  Node* newNode = new Node(value);
  newNode->next = head;
  head = newNode;
}

Notice the parameter type: Node*&. It is a reference to a pointer. We need this because we modify head itself — we change which node it points to. Without the &, we would modify a copy.

Node* head = nullptr;
insertFront(head, 30);    // head → [30] → null
insertFront(head, 20);    // head → [20] → [30] → null
insertFront(head, 10);    // head → [10] → [20] → [30] → null

19.6 Insert at back — O(n)

void insertBack(Node*& head, int value) {
  Node* newNode = new Node(value);
  if (head == nullptr) {
    head = newNode;
    return;
  }
  Node* curr = head;
  while (curr->next != nullptr) curr = curr->next;
  curr->next = newNode;
}

The traversal is what makes this O(n). You can avoid it by keeping a tail pointer, but then every operation that might be the new tail has to update it.

19.8 Delete a value — careful with the head

void deleteValue(Node*& head, int value) {
  while (head != nullptr && head->data == value) {
    Node* tmp = head;
    head = head->next;
    delete tmp;
  }
  Node* curr = head;
  while (curr != nullptr && curr->next != nullptr) {
    if (curr->next->data == value) {
      Node* tmp = curr->next;
      curr->next = curr->next->next;
      delete tmp;
    } else {
      curr = curr->next;
    }
  }
}

Two phases: first peel off any leading matches (because head might change). Then walk the rest looking ahead one node, since to delete curr->next we need to modify both curr->next and the pointer that pointed to it.

The classic linked-list bug: deleting a node whose next you have already overwritten. Always save the doomed node in a temporary, redirect pointers around it, then delete the temp.

19.9 Memory management — the destructor

void deleteAll(Node*& head) {
  while (head != nullptr) {
    Node* tmp = head;
    head = head->next;
    delete tmp;
  }
}

That is the walk. If your linked list is wrapped in a class, the destructor calls this on the head pointer. Without it, every node leaks when the list dies.

19.10 A linked list class

class IntList {
 public:
  IntList() : head_(nullptr) {}
  IntList(const IntList& other);
  IntList& operator=(const IntList& other);
  ~IntList();

  void insertFront(int v);
  void insertBack(int v);
  bool contains(int v) const;
  void print() const;

 private:
  Node* head_;
};

The Rule of Three applies. Copy constructor:

IntList::IntList(const IntList& other) : head_(nullptr) {
  if (other.head_ == nullptr) return;
  head_ = new Node(other.head_->data);
  Node* dst = head_;
  Node* src = other.head_->next;
  while (src != nullptr) {
    dst->next = new Node(src->data);
    dst = dst->next;
    src = src->next;
  }
}

Copy assignment uses copy-and-swap or the explicit delete-then-rebuild pattern. Destructor walks and deletes.

19.11 Try it

Implement IntList::contains(int v) const returning true if v is in the list. One-liner with the iteration idiom:

bool IntList::contains(int v) const {
  for (Node* curr = head_; curr != nullptr; curr = curr->next) {
    if (curr->data == v) return true;
  }
  return false;
}

19.12 Self-check

1. Why must insertFront take Node*& (reference to pointer)?
d. Same principle as pass-by-reference for any out-parameter.
2. Inserting at the front of a linked list is:
b. One new node, two pointer assignments. No traversal needed.

19.13 Challenges

  1. Middle of the Linked List (#876) — fast/slow pointers.
  2. Linked List Cycle (#141) — Floyd’s tortoise and hare.
  3. Merge Two Sorted Lists (#21) — the merge from chapter 14, on linked lists.
  4. Palindrome Linked List (#234).

19.14 Where this fits

Linked lists are the simplest dynamic data structure. The next chapter generalizes them — a node can have two children instead of one, and we get trees.

You are here Coming up
Singly linked list, Node, pointer dance, Rule of Three for lists Chapter 17: binary trees