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.

I have been writing C++ since the early 1990s. I am still surprised how often students hand me a linked list when a vector would do. Read the problem statement twice. If you do not need O(1) insert at the front, use a vector.

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.7 Print all

void printAll(Node* head) {
  for (Node* curr = head; curr != nullptr; curr = curr->next) {
    cout << curr->data << " ";
  }
  cout << endl;
}

The iteration idiom for linked lists: for (Node* curr = head; curr != nullptr; curr = curr->next). Memorize 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)?

• a. Speed.
• b. Required by C++ syntax.
• c. To save memory.
• d. Because the function changes what head points to; without the &, we'd modify a copy.

d. Same principle as pass-by-reference for any out-parameter.

2. Inserting at the front of a linked list is:

• a. O(n)
• b. O(1)
• c. O(log n)
• d. Amortized O(n).

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