Speed question

This is a discussion on Speed question within the C++ Programming forums, part of the General Programming Boards category; I was wondering what the more efficient process was according to speed. A linked list, or an array. Anyone have ...

  1. #1
    Bioport Productions
    Join Date
    Oct 2005
    Posts
    215

    Speed question

    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?
    -"What we wish, we readily believe, and what we ourselves think, we imagine others think also."
    PHP Code:
    sadf 

  2. #2
    Unregistered User
    Join Date
    Sep 2005
    Location
    Antarctica
    Posts
    341
    well, access time for an array is O(1) and access time for a linked list is O(n).

  3. #3
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    Like any datastructure, it depends on what you want to do. Speed of what?

  4. #4
    Dae
    Dae is offline
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    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.
    Last edited by Dae; 10-05-2005 at 04:48 PM.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  5. #5
    Bioport Productions
    Join Date
    Oct 2005
    Posts
    215
    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.
    -"What we wish, we readily believe, and what we ourselves think, we imagine others think also."
    PHP Code:
    sadf 

  6. #6
    Dae
    Dae is offline
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    Quote Originally Posted by durban
    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).
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  7. #7
    Bioport Productions
    Join Date
    Oct 2005
    Posts
    215
    awesome, thanks for the advice Dae. That answers all my questions. Thanks again man.
    -"What we wish, we readily believe, and what we ourselves think, we imagine others think also."
    PHP Code:
    sadf 

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. another do while question
    By kbpsu in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2009, 12:14 PM
  2. Flight Simulator Wind Speed!!
    By Dilmerv in forum C++ Programming
    Replies: 6
    Last Post: 03-19-2006, 11:40 PM
  3. Replies: 6
    Last Post: 01-08-2006, 01:49 PM
  4. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 08:22 PM
  5. Question about view vector, position, and matrix speed
    By Silvercord in forum Game Programming
    Replies: 1
    Last Post: 02-03-2003, 11:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21