Archived

This topic is now archived and is closed to further replies.

Forcas

Arrays vs. Linked lists

Recommended Posts

Hey.... I''m thinking of creating a new 2d engine, and I was wondering it''s better to hold sprite frames in an array, or a linked list. I know linked lists save memory, but I suspect that transversing them every 30th of a second could eat up CPU. Arrays take up way more memory, but on the other hand, you don''t need to transverse them.

Share this post


Link to post
Share on other sites
I would think they would take up the same amount of memory, the problem lies in KNOWING ahead of time how many elements you need. If you know exactly (which in this case I assume you would since you are using the memory storage for sprite animation) how much memory you need then using arrays is the way to go because you dont need to traverse the list. However if you didn''t know how much memory you would need (at run time) then use a linked list.



~ Boltimus ~

Share this post


Link to post
Share on other sites
There are always different factors in the array versus linked list decision. I have found linked lists good for data that grows slowly but to an unknown size. For example, I would keep a linked list of all the clients connected in a server program.

Linked list suffer from the overhead of new and delete. So if you keep adding and deleting at a rapid pace the linked list is not as good a choice. For small sets of data I would say use an array.

And you are right about the access time. Arrays are O(1) which is a constant time while linked lists are usually O(n).

The best thing is to try both and see which is easier to use and which performs better .

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
actually lists take up more memory. Lists are made up of nodes, each node has a next pointer and possibly a prev pointer. Arrays do not have that overhead. Additionally dynamically allocatted objects need a little information to help delete clean them up. Since an array is one object it will only need one extra piece. Lists will need an extra piece for every node. So I''m going to estimate that a list of pointers takes four times the memory that an array of pointers takes up.

However that should only be a minor factor in your decision, unless every single object has to maintain its own frames, as opposed to maintaining a set of frames for a type of object, or a pointer to a set of frames.

The real issue is how you are using the data. Arrays are used when the data in them is fairly static or when you need to be able to access or swap out random elements at constant time. Lists are used when you want to insert or remove elements (as opposed to swap) often.

Thus the clear choice for your situation is the array, because I doubt that you are going to frequently change the frames that make up an animation, it just isn''t what people do. Instead you are going to have a stable set that you iterate through.

If you are using C++ consider using a vector instead.

Share this post


Link to post
Share on other sites
Linked lists are only O(n) if you''re trying to access random nodes. If you''re just adding them and using them as-is (no sorting) then I don''t see how they''d be any slower than an array.

But for this case, yes, an array makes the most sense...

Share this post


Link to post
Share on other sites
Dynamic Arrays!

  
sprite* frame_buffer = new sprite[number_of_frames];
...
frame_buffer[5]->render(); // easy to access!

...
delete [] frame_buffer;


Something along those lines, right?

-----------------
The Goblin (madgob@aol.com)
-----------------
"Before critisizing somebody, walk a mile in their shoes. That way, when you do critisize them, not only will you be a mile away, but you''ll also have their shoes!"

Share this post


Link to post
Share on other sites
I completely agree with Anonymous Poster. Use the STL's vector to hold pointers to your sprites; count up the number of sprites you need to load and call reserve to allocate that much space in the vector to hold the pointers, then just add the pointers using push_back.

Using a linked list (or the STL's list) will eliminate the need to count the sprites before loading them, but the amount of time it will take to count up the sprites is probably less than it takes for the linked list to allocate all of the nodes necessary, since they can't all be allocated in bulk like with an array or vector.

So, again, use a vector or, if you don't like the STL, go with Goblin's suggestion of dynamically-allocating an array for it which, of course, will require counting.

But use vector.

Edited by - merlin9x9 on July 26, 2001 6:43:23 PM

Share this post


Link to post
Share on other sites
Well, just don´t forget one thing. Arrays are O(1) if, and only if, you know where each element is. If you know how many elements you have and use an array with that size, you will still have the problem of finding an element in a array.

I´m not saying you should use linked list, im just telling you that if your going to use arrays you better have some sort of way of having that constant O(1) access time.

Of course, you can still use an Hash Table, but it means you will have to take more memory.

Share this post


Link to post
Share on other sites
quote:
Original post by wolverine
Well, just don´t forget one thing. Arrays are O(1) if, and only if, you know where each element is. If you know how many elements you have and use an array with that size, you will still have the problem of finding an element in a array.

I´m not saying you should use linked list, im just telling you that if your going to use arrays you better have some sort of way of having that constant O(1) access time.




This is true. The access time for a random element in an array is O(1) but O(n) for a linked list. If you are doing a search/sort or someother manipulation on it then it's different depending on what trick you use to sort it. It also depends a lot on the information that is in the data structure. Looking back at the original question, he's not doing any searches and the data is in order. He's just moving to the next element in the list. So both an array and a (circly) linked list would perform about the same. Just keep an index/pointer of where you are in the array/list.

-------
Andrew



Edited by - acraig on July 28, 2001 4:10:55 PM

Share this post


Link to post
Share on other sites
Linked list are less efficeint in thier memory use than arrays are, but if you are considering a list, that implies you do not know for certain the maximum number of elements. In order to be safe with an array you need to allocate more space than is needed, a list will allocate as it is needed. That is why list, in the end, use less total memory.

For sprite frames, I''d use a dynamic array. The stl vector would work good.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
When using arrays and each time one becomes full, you could alloc certain number new elements (for example, 10 for sprite list) to overcome new/delete overhead problem (so new memory allocation is not necessarily needed every time new entry is added to the list). This way, both memory usage and new/delete overhead stay consistent.

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
Linked list are less efficeint in thier memory use than arrays are, but if you are considering a list, that implies you do not know for certain the maximum number of elements. In order to be safe with an array you need to allocate more space than is needed, a list will allocate as it is needed. That is why list, in the end, use less total memory.

For sprite frames, I''d use a dynamic array. The stl vector would work good.


STL vectors, if I recall correctly, by default will reallocate by doubling their size when necessary. Thus, if you know the exact number of elements you will be using, you should pass that in when you''re defining the vector. I''m not sure of the exact technique for that, though.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Here''s the fastest way to get this done, and will also give the best performance.

Create the array with the new operator when you load the frames.

For each object structure that will use an animation, add ONE SINGLE pointer to a frame.

Set this pointer to the address of the first element in the array.

To get the next frame of animation, increment the pointer.

Do NOT access the frame through an index variable. Keep some index variables floating around to keep up with animation length, etc., but use the pointer to access the frames.

Accessing array elements with a pointer eliminates the offset calculation, if you don''t believe me try it both ways and check the assembly output.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
Here''s the fastest way to get this done, and will also give the best performance.

Are you sure? I am not sure if you''re even really answering the question. You say ''the array'' without detailing how large to make it, which I believe was a key part of the original problem.
quote:
Do NOT access the frame through an index variable. Keep some index variables floating around to keep up with animation length, etc., but use the pointer to access the frames.

Accessing array elements with a pointer eliminates the offset calculation, if you don''t believe me try it both ways and check the assembly output.

From what compiler? And for what platform? Unless I''m mistaken, recent processors have instructions that can process array offsets just as quickly as they would process any other indirect addressing (eg. dereferencing a pointer).

Anyway, even if pointer access is quicker than indexing, I doubt an offset calculation is going to be a big deal in relative terms when you''re just about to perform a blit anyway.

Write good code first, optimal code later...

Share this post


Link to post
Share on other sites