[cdman]

Hmm, are you sure that this (linked lists with small elements) is a good example which you should tell people about?

Linked lists are bad because they have big overhead (8 bytes for every element in your case - which dominates by a large margin if you store an int in each node for example) and they are really bad for CPU caches (they have very little spatial locality), thus slowing down your code.

I much rather prefer the "growing array" approach.

[jbooth]

Yeah, but they have some unique characteristics related to inserting/deleting from the middle or beginning of the list. They're actually used in a few places in the linux kernel, for performance reasons, in spite of cache locality issues.