Jonathan M Davis: >Uncommon? Sure, if you don't need the ability to arbitrarily add and remove >elements from a container, then a vector type is definitely better than a >linked list. However, there are _plenty_ of cases out there where the ability >to arbitrarily add and remove elements from a container is a necessity. It >depends entirely on the algorithm that you're using and what you're trying to >do.<
In many cases the items you have to remove are not so specific, so you can just pop the last item of a dynamic array. The same for adding items. If you have to remove specific items you often don't need to keep their order, so you can move the last item to the array slot that now is free, and shorten the array length by one. You can take a look here: http://www.fantascienza.net/leonardo/ar/list_deletions.html Dynamic arrays can contain references or pointers, so you can swap items around efficiently using their index. Modern CPUs have two or more cache layers, this means that today following link chains worsens the access pattern inside the cache lines, and pointers need memory that increses cache pressure. In most of your algorithms you can replace linked lists with *good* dynamic arrays (D ones are not good enough in their append performance) with a general performance and memory improvement. And the code can become simpler. There are few situations where linked lists are useful, but today they are uncommon. Even if you use linked lists often, this doesn't mean they are the often better than using a dynamic array. Bye, bearophile
