On Sun, 2008-03-23 at 03:46 -0400, Robert P. J. Day wrote: > On Sun, 23 Mar 2008, Manish Katiyar wrote: > > "Linux kernel development" - Robert Love has a nice detailed > > explaination of it. > > ironically, that's the very book i have open in front of me at the > moment and which is confusing me, since robert writes (near the bottom > of p. 347): > > "To traverse the list, simply pick an element and follow the pointers > until you get back to the original element. This removes the need for > a special head pointer." > > however, as you explain it, that "sentinel" element *is* a special > kind of head pointer. so how to explain this discrepancy? I think that Love is comparing circular linked lists to regular singly-linked lists, but it isn't very clear. We can compare the cases of how to traverse a list given some element in the list. With non-circular, singly-linked lists: We need a 'head' pointer so that we can access the elements before our element. I think this is the special head pointer that we don't need in the kernel implementation. With non-circular, doubly-linked lists: We no longer need a head pointer, because we can repeatedly use 'prev' to get to the start of the list, and then traverse. However, using a 'head' pointer would be faster. With circular, doubly-linked lists (or singly-linked, doesn't matter): Just start wherever you are, and traverse the list. You would have to make sure to skip 'head', as you noticed. However, there is no need for 'head' to traverse the list from any given location. In other words, there is no NEED for a special head pointer with a circular linked list, but the implementation still uses one to make things cleaner. Avishay -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
