Post by Scott McPhillips [MVP]With an array you get very fast access to every element (indexing) but
inserting or deleting an item is quite inefficient (requires mass copying).
With a list you get slow access to most elements (no indexing) but
inserting or deleting an item is efficient (no copying required).
In general this is true. However, in certain situations things can change.
If your array/list is only storing atomic data (i.e. ints, floats, etc)
then the array is probably a better bet. The reason being is this wonderful
little thing that is entirely ignored in all algorithms analysis: the cache.
If you do an experiment with random insertions into an array and a list
(using integers, for example) you will find that up until about 8000
elements or so, the list and the array are pretty close in terms of speed.
When you get over that number of elements things change drastically.
The array becomes way faster than the list, which is somewhat counter
intuitive.
If you take a closer look at it though it becomes clear why the array is
faster. The array is stored linearly in memory, so searching through it
and even copying large parts of it are all cache friendly. The list on
the other hand is not cache friendly at all. Elements in a list are
stored all over memory so every element access can potentially cause a
cache miss. The array, even with its big memory copy, is still faster
because you waste a whole whack of time just finding the location to
do the insertion with the list. Also with a list you must store extra
data along with what you are storing in the list, namely a pointer to
the next element (at a minimum).
Storing complex structures and classes in an array or list may change
things slightly. If you consider that the time it takes to
construct/destruct your class will be the same for both the list and
the array, you can pretty much ignore that part. The part that
matters is how complex your copy constructor/operator is for your
class. This is the part that could kill the performance of the array
because, for a random insertion/deletion it needs to do a block copy.
But if you have a complex class as your elements it can't use something
simple like memcpy() to do the work.
So just be aware that there are other issues besides what the data
structure was designed for. You might not care about this either,
but a list can really fragment your memory. On a windows PC this
isn't really an issue, there is usually lots of memory. On
something like a game console or cell phone, fragmenting your
memory is a really good way to kill your application.
2 cents worth.
Murrgon