[gosu]

The correct way to do linked lists is to store the list traversal fields next to the data. In C, this would mean storing next/prev pointers inside of the structs which will be placed on lists.

In light of this, the things in the OP are often non-issues because you'll need the data in cache immediately after the list operation anyway (or during the traversal, for O(n) operations like list_find). In fact, vectors of pointers are worse for the hardware because you'll need to load in more cache lines than with lists, in order to traverse the array.

Lists aren't clearly the better option when the data will need to live exactly as long as the data exists in the container. In this case, you can store the data itself in a vector's backing array (and so the data will be invalid as soon as it's removed from the vector).

[yason]

Who the heck puts the payload into a separate allocation?

I'm pretty sure I've never seen such an implementation. Not once. I could imagine seeing something like that in textbooks where they use graphical diagrams to illustrate how a linked list works but who would actually implement it like that -- I don't know.

The canonical way is to do:

  struct listnode {
    struct listnode *next;
    struct listnode *prev;
  };

  struct your_own_data_node {
    struct listnode node;
    int x, y, z;
  };

which ensures that you can have a set of functions that operate on struct listnode * and you can use them for all of your lists.

[gosu]

I wouldn't call that canonical. You can take a further step, as in the Linux version that someone posted below:

http://kernelnewbies.org/FAQ/LinkedLists

[cygx]

Anecdotal evidence to back up your claim: Mergesorting an intrusive linked list can outperform quick or heap sorting an array of pointers.

[ternaryoperator]

That's a very interesting refinement. Dangit, now I've got to go and code it up and profile it. Unless you've done this legwork?

[nteon]

What he describes is how the Linux kernel implements linked lists: http://kernelnewbies.org/FAQ/LinkedLists