Arrays vs. Linked lists
Author
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.
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 ~
~ Boltimus ~
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
.
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
.
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.
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.
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...
But for this case, yes, an array makes the most sense...
Dynamic Arrays!
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!"
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!"
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
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
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.
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.
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
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.
For sprite frames, I''d use a dynamic array. The stl vector would work good.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
