4 ms·

Exactly. Also, pointers are just an implementation detail of linked lists. You can implement an array based linked list and avoid "scribbling all over memory",

Exactly. Also, pointers are just an implementation detail of linked lists. You can implement an array based linked list and avoid "scribbling all over memory", which really is a valid concern raised in the article.

stormbrew 13y ago
What exactly would an array based linked list be but either an array or an array deque? These things have names for a reason.
- betterunix 13y ago
  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.
  - marshray 13y ago
    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.
  - yyqux 13y ago
    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.
- marshray 13y ago
  If you know in advance, say, that you will never have more than 2^(multiple of 8) items in the list, you can use a index smaller than the pointer size.
- zwieback 13y ago
  traditional linked list: { l * next; x * data; } or { l * next; x data; } array-based linked list would be an array where each element also has the index (or pointer) of the next element. { int next; x data; } [1000]; Now all your elements are packed together in a memory space that you can control. I think of (array) deque as something that allows me to operate on the front and back, not necessarily traverse and insert/delete in the middle.
  - stormbrew 13y ago
    This strikes me as heap management more than a 'linked list implemented as an array'. The heap itself is, after all, equivalent to a giant array. But it doesn't get you the same locality as an array at any rate. The idea is that, assuming your elements are smaller than a cache line and your array as a whole is larger, what you're avoiding with an array is N/M cache misses while you traverse rather than potentially (or even probably, depending on various other factors) having a cache miss on every nextItem(). You'll also miss more often because of the expansion of the elements.

stormbrew 13y ago

What exactly would an array based linked list be but either an array or an array deque? These things have names for a reason.

betterunix 13y ago
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.
- marshray 13y ago
  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.
- yyqux 13y ago
  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.
marshray 13y ago
If you know in advance, say, that you will never have more than 2^(multiple of 8) items in the list, you can use a index smaller than the pointer size.
zwieback 13y ago
traditional linked list: { l * next; x * data; } or { l * next; x data; } array-based linked list would be an array where each element also has the index (or pointer) of the next element. { int next; x data; } [1000]; Now all your elements are packed together in a memory space that you can control. I think of (array) deque as something that allows me to operate on the front and back, not necessarily traverse and insert/delete in the middle.
- stormbrew 13y ago
  This strikes me as heap management more than a 'linked list implemented as an array'. The heap itself is, after all, equivalent to a giant array. But it doesn't get you the same locality as an array at any rate. The idea is that, assuming your elements are smaller than a cache line and your array as a whole is larger, what you're avoiding with an array is N/M cache misses while you traverse rather than potentially (or even probably, depending on various other factors) having a cache miss on every nextItem(). You'll also miss more often because of the expansion of the elements.