Thanks again for the reply Jonathan. I'm using doublely linked list I made for a game where ships and there lazer bolts are in the same list. Without linked list I couldn't do things like create a lazer bolt or remove one while trans-versing the linked list. I had to use my own linked list, having a next and prev node in each object that goes in the list.

Joel Christensen:

> Thanks again for the reply Jonathan. I'm using doublely linked list I made for a game where ships and there lazer bolts are in the same list. Without linked list I couldn't do things like create a lazer bolt or remove one while trans-versing the linked list. I had to use my own linked list, having a next and prev node in each object that goes in the list.

I am looking for use cases of singly|doubly linked lists, I (nearly) never need them in my code. Few questions:
1) What's a typical (or average) length of your list?
2) Are items sorted (like from the bigger to the smaller one)?
3) Is the item order important (so is it OK to shuffle them in some other ways)?
4a) How often/many do you need to add items to the list?
4b) How often/many do you need to remove items to the list?

Bye,
bearophile

> I am looking for use cases of singly|doubly linked lists, I (nearly) never need them in my code. Few questions:
> 1) What's a typical (or average) length of your list?

Thanks for your interest bearophile.

I haven't used linked list much more than just trying them out. And my game is at its earlier stages.

Not very much, 2 players, mines ad lazer bolts are added and removed when used. I guess around 10.

> 2) Are items sorted (like from the bigger to the smaller one)?

I've got the player objects fixed at the head of the array.

> 3) Is the item order important (so is it OK to shuffle them in some other ways)?

I'm thinking of having then sorted as objects are added. I'm also thinking of having a pointer to the start and end of each kind of object (like sub lists).

> 4a) How often/many do you need to add items to the list?

My game is only small at the moment, so not a good sample. I guess every time a player fires a lazer bolt or lays a mine, but those objects don't last long.

> 4b) How often/many do you need to remove items to the list?

About as often as I add them, eg. the mines and lazers are added and taken away often. How many, two at a about the same time with two players.

Joel Christensen:

> Not very much, 2 players, mines ad lazer bolts are added and removed when used. I guess around 10.

I see, then use a dynamic array, plus append, and few functions like remove. It's faster and simpler. In most situations today (in a language that allows mutability) linked lists are the wrong data structure to use.

Bye,
bearophile

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).

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

Jonathan M Davis:

> I can only assume that it's one of his pet peeves (we all have them -

This is a long story, and I don't have time now, I am sorry. Something related: http://tinyurl.com/3yrawox

Bye,
bearophile

Thanks for the long winded reply Jonathan.

I don't know how to avoid using my own linked list, I have next/prev in each class (Ball, Lazer and Mine ) in the list.

Thanks bearophile, I had a bit of a look at that site.

My game is simple so just maybe the easiest way is the way to go, though if I use the most tightest way and so my game would be an prototype for bigger games to reference.

On Mon, 27 Sep 2010 10:27:36 +0400, Joel Christensen <joelcnz@gmail.com> wrote:

> Thanks for the long winded reply Jonathan.
>
> I don't know how to avoid using my own linked list, I have next/prev in each class (Ball, Lazer and Mine ) in the list.
>

That's called intrusive linked list, and I find using it quite viable:
zero-allocation O(1) add/removal is a very strong characteristics.

They are very useful especially for lock-free algorithms.

On Sun, 26 Sep 2010 04:38:36 -0400, Joel Christensen <joelcnz@gmail.com> wrote:

> Thanks again for the reply Jonathan. I'm using doublely linked list I made for a game where ships and there lazer bolts are in the same list. Without linked list I couldn't do things like create a lazer bolt or remove one while trans-versing the linked list. I had to use my own linked list, having a next and prev node in each object that goes in the list.

Not sure if dcollections could be of use:

http://www.dsource.org/projects/dcollections

And the linked list class:

http://www.dsource.org/projects/dcollections/browser/branches/d2/dcollections/LinkList.d

One thing my lib supports is removal while traversing via foreach.  See the purge function.

Sorry about lack of online docs, I need to figure out how to automatically generate them (the D1 docs are auto-generated, but I haven't put in any time to figure out how to generate the D2 version).

-Steve