K
Keith Thompson
Sourcerer said:Yes, that is my default assumption, because this is the most common in
my experience. I'm not trying to be infinitely accurate.
There's no need to be "infinitely accurate". Just acknowledge the
assumption. For example, something like "This requires 8 bytes per
node (assuming 4-byte pointers)" is perfectly fine.
[...]
True, you save memory and it can be faster than realloc(), but still
memory consumption remains proportional to the length of the list. But
these are the only options - either modify the list, or consume
memory. So, which will it be is purely an engineering decision - weigh
the alternatives and choose the best one.
As it turns out, those aren't the only options. Chris Torek posted a
solution that neither modifies the list nor allocates O(n) memory --
but it requires O(n**2) time. (I think you could speed up Chris's
method by a constant factor by allocating a fixed-size array of
pointers, reversing the list in chunks rather than one element at a
time.)