4 ms·
But isn't that true if the list has one element? Then A->A, thus prev==next, but the list still isn't empty. And if the head lives outside of the list proper,
by ced 16y ago
But isn't that true if the list has one element? Then A->A, thus prev==next, but the list still isn't empty.
And if the head lives outside of the list proper, then you would need special-case code to handle deletion of the first element in the list (since the head contains a pointer to it). It wouldn't be branchless.
- tedunangst 16y agoThere is a fake element that is the head. It doesn't count as part of the list, but it's always in the list. With one element, the list is H->next = A, A->next = H H->prev = A, A->prev = H
- ced 16y agoOh, that's a clever solution. Thanks.