News for hackers. Stuff that matters.
Re:Stop Using Linked Lists by betterunix on Wednesday May 22, 2013 @02:30PM (#5752829)
Instead of pointers, you would store an index in the array of nodes:

  struct node {
     void * data;
     uint32_t idx_next;
  };
You are still dereferencing pointers, of course, but you have better locality, even after doing a lot of insertions and deletions.
Re:Stop Using Linked Lists by marshray on Wednesday May 22, 2013 @03:02PM (#5753030)
It's even better with intrusive containers. As an extreme case, let's say we need a collection of 24 bit RGB triplets:

    struct node {
        uint8_t r, g, b;
        uint8_t idx_next;
    };
Of course, a contiguous array uint8_t[256][3] might still be faster.
Re:Stop Using Linked Lists by yyqux on Wednesday May 22, 2013 @05:56PM (#5754043)
This is a great optimization technique to have up your sleeve. The downside of course is that if you're dynamically allocating and freeing nodes you can end up having to write your own memory allocator.