On Thu, 7 May 2015, Huaicheng Li wrote:

Hi Robert,

You got my point and I’m sorry for not stating it in a clear way. You are right about the "prev-to-left" and "next-to-right" when drawing the line. At that time, I just wanted to show which node they were pointing at. Anyway, you solved my puzzle. Also thanks for your excellent article.

it's a moderately common mistake to not realize that the "head" of a list is represented by just another "struct list_head" like all the other elements in the list, but it's a special list_head in the sense that it does ***not*** represent a valid enclosing data payload, and should never be dereferenced. the way i normally demonstrate this is to show the following macro from include/linux/list.h: /** * list_for_each - iterate over a list * @pos: the &struct list_head to use as a loop cursor. * @head: the head for your list. */ #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next) note well how iteration over a list starts from "(head)->next" and continues until returning back to "(head)" while *not* including that last address to be dereferenced. this also has the (obvious) consequence that you can never forget which element in a list is the head; otherwise, you'll never know which element you're not supposed to dereference. rday -- ======================================================================== Robert P. J. Day Ottawa, Ontario, CANADA http://crashcourse.ca Twitter: http://twitter.com/rpjday LinkedIn: http://ca.linkedin.com/in/rpjday ========================================================================

From: kernelnewbies-bounces@kernelnewbies.org [mailto:kernelnewbies-bounces@kernelnewbies.org] On Behalf Of Mulyadi Santosa Sent: Thursday, May 07, 2015 3:53 AM To: Huaicheng Li Cc: kernelnewbies Subject: Re: About head of kernel linked list structure On Wed, May 6, 2015 at 5:39 PM, Huaicheng Li <lhcwhu@gmail.com<mailto:lhcwhu@gmail.com>> wrote: In my understanding, the head initialised using LIST_HEAD_INIT or defined by LIST_HEAD corresponds to no *real* data field. But it *does* have its own _next_ and _prev_ pointers. The _next_ pointer points to the first real node in the doubly linked list, and the _prev_ pointer points to the last real node. I'm wondering if the picture shown at the very bottom of http://kernelnewbies.org/FAQ/LinkedLists is wrong about this. Because I believe head's _prev_ should point to the last node, which is at the very right. And the last node's _next_ should point to the head. Just as shown like the red line. Am I right? [cid:image002.png@01D089A8.8896F550] Hi Huachieng AFAIK, if the linked list is not circular one, the last node's next should point to NULL, so does the head prev's. This is done so you know when you hit head i.e if !(head.prev) { // we're at head } Just pointing out that these lists are circular. Back in the old days we used to call them "rings".

From list.h:

183 /** 184 * list_empty - tests whether a list is empty 185 * @head: the list to test. 186 */ 187 static inline int list_empty(const struct list_head *head) 188 { 189 return head->next == head; 190 } Jeff Haran