3 ms·
I think you're confused. The list head exists outside of the structs that are in the list. The list links (next and prev) live in the struct, but not the head
by tedunangst 16y ago
I think you're confused. The list head exists outside of the structs that are in the list. The list links (next and prev) live in the struct, but not the head.
To answer the original question, you decide a list is empty when prev == next.
- ced 16y agoBut 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.