linked list

[Jonathan M Davis]

On Sunday 26 September 2010 11:38:35 Joel Christensen wrote:
> I normally use D's built in dynamic arrays. but it doesn't work with
> adding and removing with the foreach loop (like removing an object from
> the list while still going through the list).

I would point out to you that Bearophile seems strongly opposed to linked lists 
in general and seems to point out to people that arrays and vector/ArrayList 
types (Array in std.container) are faster on modern hardware whenever they come 
up. I can only assume that it's one of his pet peeves (we all have them - for 
instance, I hate it when people use post-increment or pos-decrement for instance 
when pre-increment or pre-decrement will do), but I don't think that he's 
necessarily right.

Classicly in computer science, if you have a data structure which you're going 
to be doing a lot of appending to, prepending to, or inserting into, you use a 
linked list. std.container currently has SList, which is a singly-linked list 
but no doubly-linked list. However, they don't have random access and they take 
up more memory than an array or an Array (thanks to all of those prev and next 
pointers). Bearophile objects to them, I believe, because they aren't a single 
block of memory and so they harm cache locality, resulting in poorer cache 
performance from the CPU. He may very well be right (in fact on some level, I'm 
sure he is), but that's the sort of thing that most people worry about when they 
find that their data structure has poor performance rather than reacting 
negatively to any suggestion of using a linked list.

Whether using a linked list is the best choice for your application, I don't 
know, but it is often the case that you can do the job just as well or better 
with an Array, tree, or hash table, depending on what you're trying to do and 
how you're trying to do it. However, if you constantly adding and removing from 
a container (especially if you're doing it anywhere other than the end), and you 
rely on insertion order (so you can't use a hash table) rather than sorted order 
(like you would with a tree), then a linked list is likely the best choice. It 
has cheap insertions and removals.

Certainly, in D, I would avoid having lots of appending to and removal from the 
end of dynamic arrays in your code because the GC isn't efficient enough and 
that's going to result in a lot of allocations and deallocations, but Array 
should solve that problem for the most part, since it uses an internal array 
which is larger than the Array's length so that it can reduce how often 
reallocation occurs (and if you've removed from the end, then it has more room 
for adding more to the end, so it shouldn't have the same problem as a built-in 
array).

In any case, from your description of having to remove from the middle of a list 
would indicate that a linked list is probably the best for what you're doing, 
but not knowing in detail, I'm obviously not in the best place to judge.

- Jonathan M Davis