Linked lists

Do you need:

* random access to elements ?
* contiguous storage for C array compatibility ?
* pointers to elements to always remain valid ?
* fast insertion/deletion at the beginning/end ?
* fast insertion/deletion at any point ?

---

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” — Brian W. Kernighan (C programming language co-inventor)

It really depends on what you will be doing with your objects. If you will just be going through each object on every frame and calling an update function, then a link list will work. However, it you want fast access to a certain object, then it will be better to go with a dynamic array/matrix.

[-ouch, fruny beat me to it]

[edited by - Jbs on January 18, 2004 6:09:10 PM]

The objects are explosions which are particle based. I dont know how many of these objects are to be rendered at the same time.

Ok, I''d go with a combination C++ vector/free list.

---

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” — Brian W. Kernighan (C programming language co-inventor)

Could you explain Fruny please??

I feel obligated to point out this snippet from MSDN:

Dynamically allocated linked lists can reduce program performance because when you search for an item or when you traverse a list to the end, each skipped link could miss the cache or cause a page fault. A list implementation based on simple arrays might actually be much faster because of better caching and fewer page faults—even allowing for the fact that the array would be harder to grow, it still might be faster.


[EDIT] Using code tags was a bad idea.

[edited by - Promit on January 18, 2004 6:41:00 PM]

That all depends on your allocator though..
You might for instance use a memory pool as your allocator, which would make for much better cache consistency

Ok. First thing you have to keep in mind is that programming is all about tradeoffs. Depending on the type of container you choose, some operations will be cheap, but, conversely, some other operations will have to be more expensive.

So, take for example the C++ std::vector class. It actually implements a dynamic array. When it runs out of space, it allocates a larger chunk of memory and copies all the old data to the new chunk. This means that accessing any individual element is cheap - it just involves a bit of pointer arithmetic, but inserting/removing elements in the middle of the vector is expensive, because all the elements that follow must be moved down/up one position.

In comparison, a linked list, like std::vector, will give you very fast insertion/removal - it just involves manipulating the previous/next pointers of the elements adjacent to your insertion/removal point. The price you have to pay for that is that, if you want to access an element in the middle of the list, you have to start from one end and walk down the list, element by element, until you have reached the one you wanted. Storage is also not contiguous, you pay some overhead for each element (the next/previous pointers) and since the elements are individually allocated, you may lose spatial coherence, which will degrade your cache''s performance.

Choosing one over the other is therefore a question of figuring out which is most important to you: cheaply looping over the objects or cheaply adding/removing objects. In the general case of particle systems, any particle may become ''dead'' at any time, which means you may have to remove particles from the middle of the container - which is something vectors are not great for. But on the other hand, you also want your render loop to be as cheap as possible - which is something lists are not great for.

So what I suggested above is to combine the two. Each particle will contain a flag that tells whether it is a valid particle or not (e.g. a valid particle has a non-zero lifetime). If the particle is valid, its data represents whatever data you need for your particle system. If the particle is invalid, its data only contains the index of the next invalid particle (a pseudo ''next'' pointer) in the container, or some fence value for the last particle in the free list. That way, when a particle becomes invalid, it is trivial to put it on the free list, and when a new particle is created, it is trivial to take it off the free list (you need to keep track of the index of the head of the list). If the list is empty and you need more particles, you can let the container grow normally.

Of course, that''s just an optimisation that assumes you can already deal with dynamic storage in general. If you dont, just pick either std::vector or std::list depending on your perception of what the critical operations for your system are.

Additionally, if you know that all the explosions have the same life time, you can use a simple queue (using the std::deque class), which gives you access properties similar to that of vector. The difference there is that, since you know that all the particles have the same life time, the first to be created will also be the first to die. Which means that, if you always insert new particles at one end of the deque, you can always remove them from the other end - both of which are operations for which deque is optimized (unlike vector which is only optimized for insertion and removal at the end).

If you have particles with a small number of different lifetimes, it is easy to have one queue for each specific value.

You can''t choose a data structure until you know precisely how you are going to use it.

---

“Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” — Brian W. Kernighan (C programming language co-inventor)

For particles, go an array with a static size. Its the type of thing thats so small in size the the overhead of pointers would be bigger then the actual particle data.

As for linked list, the concept is real easy, you keep one pointer, the "head" that points to the first data element. Each data element has a next pointer, that contains the location of the next data element. Heres a generic linked list class, the void*pointer is quite arbitrary.

struct linked_list {
  void *data;
  struct linked_list *next;
}

struct linked_list *head;

void add_item( struct linked_list *p_item; ) {
  if ( head ) {
    struct linked_list * traverser=head;
    while ( traverser->next )
      traverser = traverser->next;
    traverser->next = p_item;
  }
  else {
    head = p_item;
  }
}
 

This code just depends on null(0) pointers being used. A double linked just means you have a tail and a pointer in the other logical direction.