Sentinels and removal

Questions 1 to 5 of 8

1. 1. In removeAll from the lesson, why is Node* next = cur->next; written before the if block and not after the delete?

   delete cur would not compile if a variable still pointed at the nodeAfter delete cur, reading cur->next reads freed memory, so the next node must be saved firstThe compiler warns about unused variables unless next is declared before the ifSaving next makes prev point at the node after cur
2. 2. A DList with a sentinel has no null checks at the ends. Why does popFront still start with if (empty()) return false;?

   On an empty list, sentinel_.next is nullptr, and erase cannot take nullptrerase is public, so it would be called from outside the class by mistakeThe sentinel's value must be read before a pop can happenWithout the check, erase would receive the sentinel, which is not a heap node, and delete would fail
3. 3. This program is the lesson's ring with a sentinel. What does it print? ``cpp #include <iostream> struct Node { int value; Node* prev; Node* next; }; Node sentinel{0, nullptr, nullptr}; void insertAfter(Node* where, int v) { Node* n = new Node{v, where, where->next}; where->next->prev = n; where->next = n; } void erase(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; delete n; } int main() { sentinel.next = &sentinel; sentinel.prev = &sentinel; insertAfter(sentinel.prev, 5); insertAfter(sentinel.prev, 6); insertAfter(sentinel.prev, 7); erase(sentinel.next->next); insertAfter(&sentinel, 4); int count = 0; for (Node* p = sentinel.next; p != &sentinel; p = p->next) { ++count; } std::cout << "front " << sentinel.next->value << ", back " << sentinel.prev->value << ", count " << count << '\n'; return 0; } ``

   front 5, back 6, count 3front 4, back 5, count 2front 4, back 7, count 3front 6, back 7, count 3
4. 4. What does this program print? ``cpp #include <iostream> struct Node { int value; Node* next; }; void removeAll(Node*& head, int target) { Node* prev = nullptr; Node* cur = head; while (cur != nullptr) { Node* next = cur->next; if (cur->value == target) { if (prev == nullptr) { head = next; } else { prev->next = next; } delete cur; } else { prev = cur; } cur = next; } } int main() { Node* head = nullptr; for (int v : {7, 2, 5, 2, 2}) { head = new Node{v, head}; } removeAll(head, 2); int count = 0; int sum = 0; for (Node* p = head; p != nullptr; p = p->next) { ++count; sum += p->value; } std::cout << count << " nodes, sum " << sum << '\n'; return 0; } ``

   2 nodes, sum 124 nodes, sum 162 nodes, sum 53 nodes, sum 9
5. 5. This loop should remove every target value. On the list 2, 2, 1 with target 2 it writes into freed memory. What is the bug? ``cpp Node* next = cur->next; if (cur->value == target) { if (prev == nullptr) head = next; else prev->next = next; delete cur; } prev = cur; cur = next; ``

   next is read after cur is deleted, so the saved pointer is wronghead is passed by value, so the caller never sees the new first nodeprev = cur; runs even for removed nodes, so prev can point at a freed node, and prev->next = next then writes into freed memorycur = next; should be cur = head;, so the walk never restarts