I was wondering what the more efficient process was according to speed. A linked list, or an array. Anyone have any explanations why 1 or the other is faster to loop through?
Printable View
I was wondering what the more efficient process was according to speed. A linked list, or an array. Anyone have any explanations why 1 or the other is faster to loop through?
well, access time for an array is O(1) and access time for a linked list is O(n).
Like any datastructure, it depends on what you want to do. Speed of what?
Resize: list > array (list is very fast here)
Insertion: list > array
Removal: list > array
Append: list > array
Prepend: list > array
Remove tail: list < array, doubly linked list == array
Remove head: list > array
Access random index (you do this alot): array > list (array is very fast here)
Thats the list according to Data Structures for Game Programmers, however list is barely faster than array in these situations, and in depends on the number of items.. e.g. resize would take a very long time in an array if the thing had many items.
Great, thanks alot Dae. That's sums it up nicely. Can I ask a bit of advice on a subject really meant for game programming. I'm making the Node class of my engine, where I need to scan through all the meshes(alot) and convert them to a smaller dataform so I can scan through them very quickly in the render loop. Would this scan be quicker with an array or a linked list? Keep in mind I don't need to access a random index, they could hold just one datatype, and I'm just scanning through all of them.
It wouldn't matter, if all you are doing is scanning, and you dont need random index (meaning you can just increment ++) then neither linked list or array would be faster. If you had functions to that node only necessary for linked lists, you would be using more space. I see how random index isnt necessary for the convert, or scanning.. but you would think you wouldnt be scanning the meshes, but using them by id, in which case I'd use an array.. but if you are scanning for some reason instead, of course wouldnt matter which (as you implied).Quote:
Originally Posted by durban
awesome, thanks for the advice Dae. That answers all my questions. Thanks again man.