3 ms·
An empty ring never needs to be presented. The point about the Linux list is that it lives inside another struct. If there are no instances of that struct, th
by rwmj 16y ago
An empty ring never needs to be presented. The point about the Linux list is that it lives inside another struct. If there are no instances of that struct, then there is no need to represent an empty list at all!
- ced 16y agoYeah, I thought about that. But he mentions "emptiness testing" a few times in the rest of the post. If there's no empty list representation, what's the point?
- tedunangst 16y agoI 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.