title: Two ways of implementing a linked list: which is better?
body: <p>I know generally two ways to design a generic linked list datastructure in C. And I'm wondering which is better. Before asking the question, I'll introduce both methods shortly:</p>
  
  <p>One method is to build functions around a structure like the following:</p>
  
  <pre><code>struct list_element {
      struct list_element *prev;
      struct list_element *next;
      void *data;
  };
  </code></pre>
  
  <p>Obviously, the data pointer points to the payload. The list element struct is outside the payload. This is e.g. how glib has designed its double linked list facility: <a href="http://library.gnome.org/devel/glib/2.26/glib-Doubly-Linked-Lists.html" rel="noreferrer">http://library.gnome.org/devel/glib/2.26/glib-Doubly-Linked-Lists.html</a></p>
  
  <p>Another method is the way how it's done in the Linux kernel: <a href="http://isis.poly.edu/kulesh/stuff/src/klist/" rel="noreferrer">http://isis.poly.edu/kulesh/stuff/src/klist/</a>. There is no void pointer to the payload in the list element struct. Instead the list element struct is included in the payload struct:</p>
  
  <pre><code>struct list_element {
      struct list_element *prev;
      struct list_element *next;
  };
  
  struct person {
      char name[20];
      unsigned int age;
      struct list_element list_entry;
  };
  </code></pre>
  
  <p>A special macro is used to get a pointer to the payload struct given a pointer to the list_entry, its name withing the payload struct and the type of the payload struct (the list_entry() macro).</p>
  
  <p>Finally, <strong>here is the question:</strong> What is the advantage of the latter of the two methods of constructing a linked list? A few times I've heard people say the second is more 'generic' than the first, but why? I would even argue that the first method is more generic because the payload structures are list implementation agnostic, which isn't the case with the second method.<br>
  One more downside of the second method is if you want to place the payload in more than one list, you should a struct list_element member for each list in the payload structure.</p>
  
  <p>Edit:
  To summarize so far I saw two answers which were important for me:</p>
  
  <ul>
  <li>With the first method: removing a payload from the list involves looping through the complete list until the list element pointing to the payload is found. You don't need to do this with the second method. (Answer from Patrick)</li>
  <li>With the first method you have to do two malloc()s for each element: one for the payload and one for the list element struct. With the second method one malloc() is sufficient. (Answer from Roddy)</li>
  </ul>