[Aloisius]

Why would you though given there are so many implementations that have nice features like sentinels, freelists and are optimized for cache locality, thread-safe and potentially even lock-free?

(a simple struct for your linked list isn't really the implementation for the linked list operations. obviously in C you would define your own next pointer. i seriously doubt this guy had trouble with that part of it.)

[pandaman]

For example, one of the ways to implement order independent translucency involves a linked list of fragments in a render target. You cannot really use some external library in a HLSL/GLSL/Cg/whatever shader language you use. Even if you could - since all you need is the very basic list, any overhead from a library would be unacceptable.

Linked lists are ubiquitous in programming, hooking up a library every time you need a linked list is as same as using some library for loops. Sure, you can get some fancy loops with guards and Duff's device built-in, but in some fields of programming you will be laughed out of the job if you ever try to do this.

[salgernon]

Because some large percentage of candidates can't handle pointers. If you can't come up with a viable "delete a node from the middle of a linked list" during an interview where you are supposed to program in c then you don't get the job. No, you probably won't need to implement a linked list, but you will need to dereference pointers, and the linked list is an adequate proxy for your ability to understand the most fundamental of systems programming tasks.

[Aloisius]

Pfft. I feel like I could teach pointers to someone who had a firm grasp of any iterative language in less than 15 minutes.

Heck, I'm pretty sure I could teach pointers to someone who has only worked in matlab occasionally by cut-and-pasting others code in less than 30.

And teaching someone something new during an interview and seeing if they can understand it and then turn around and use it is far more valuable for interviewing the types of people I want to hire than asking them random questions they could find the answer to on google in less than a minute.

[jimmaswell]

    void delete_nodes(struct node n) {
     if (n.next)
      delete_nodes(n->next);
     free(n.next);
    }

like that?

[mortehu]

I mostly use linked lists when I need to allocate a bunch of stuff and it doesn't have to be contiguous, so I can avoid the cost of the mremap happening in a realloc() call. Linked lists aren't exactly a commonly used data structure by C or C++ programmers, due to their large storage overhead (usually one heap object and two pointers per item) and awful cache locality (heap object headers and list pointers between successive items).

You seem to suggest that there's a wide variety of linked list implementations whose existence you agree with, so at least you agree that some programmers should be making linked list implementations.

[bnolsen]

the problem with linked list is the cost of cache misses from memory fragmentation killing any iteration. On a current x86 processor a linked list is death for performance. For light insert/deletions work vectors still outperform. However there's always the possibility that "linked list with a twist" may provide a unique solution to a specific problem.