| Instead of allocating each element of the list individually you can do this one better. Allocate an array of elements. The prev and next don't point to memory but to indexes in the array. How do you handle empty elements? Have a special flag that means "this element is blank" and use prev and next to point to the empty elements in the list! (So you are essentially storing two interleaved lists as the same time.) Also store the first empty (and first full) element separately of course. You will need to initialize the memory before you use it, filling all the prev and next pointers for the empty elements. When you "allocate" an element you just update the prev and next pointers of all 5 elements, as needed. If you think about it - malloc also needs to store a list of unused memory areas, so despite being a bit more complex you can speed things up quite a bit by doing this. An optimization: Since filling all the empties can allocate memory, even if you might never use it, have an optimization that if the next pointer is 0 (or -1) that implicitly means the next array index, but an uninitialized index. By doing this you can allocate a 1GB array without worry, and allow the OS to only fault in pages as needed (i.e. there is no need to ever resize the array). |