Linked lists and node identity

A pending-job queue stores linked nodes, and other parts of the app hold references to particular jobs. A customer category is disabled, so all matching jobs must leave the queue. Rebuilding a fresh chain with the same surviving values would leave those references pointing at the old objects.

This is why node identity matters. The task is to reconnect the existing survivors, including when cancelled jobs appear consecutively or at the head.

Removing cancelled jobs without replacing survivors

Filtering values and relinking nodes have different identity contracts. A new vector can reproduce values but cannot preserve the addresses of existing list nodes. Here each node exclusively owns its successor through unique_ptr. Removing a node must transfer its successor's ownership into the link that used to own it.

Reconnecting through the predecessor

In 2 → 5 → 5 → 7, removing category 5 means keeping the predecessor at 2 while bypassing both matching nodes. Advancing after the first removal would skip the second. A temporary sentinel before the head gives a head removal the same predecessor-based operation as every other removal. Return its next link, not the sentinel itself.

auto node=std::make_unique<Node>(7);
Node* observed=node.get(); // observer; never delete through this pointer
// Moving node transfers ownership while observed continues to identify the allocation.

What the links do not make cheap

A pointer to an owning link can express head removal and interior removal uniformly. Move the discarded node into a temporary owner before moving its successor, so destruction never reads a member of an already destroyed object. Raw pointers in tests observe identity; they do not own memory and are invalid after their observed node is removed. Unique ownership deliberately differs from a garbage-collected node model: removal destroys excluded nodes. Survivors must retain both address and relative order. The final result owns all retained nodes and ends in null.

For n nodes and b blocked values, building a hash set and scanning the chain takes expected O(n+b) time with O(b) set storage. Link editing itself needs constant pointer state. A value-to-node wrapper or a fresh copied list has its own allocation cost and cannot replace a node-identity requirement.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

Other components can keep their references to surviving jobs because those nodes were never replaced.