Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualSimonForsman

Posted 13 September 2013 - 03:13 PM

I am writing programs a couple of years (in c) but I never ever

used a linked list - it is always arrays - arrays are sufficient and

more efficient than linked list (as many say but i do not measure the

thing) Are there a real practical cases where usage of linked list 

would be better from efficiency reason han arrays - are they realy

used ?

 

The main advantage linked lists have is that you can remove or insert items in them at any position and still preserve the order of the data without having to move other data around, there are situations where that makes them more efficient than arrays or vectors.

 

Arrays and vectors on the other hand have the advantage of having all their memory in one large continous block which allows you to quickly access any element (as long as you or the compiler knows the size of each element you can calculate the adress for any element in the array) and as long as you don't store pointers the linear memory layout of the array will be far more cache friendly. (if you store pointers in an array you'll get the cache benefit when accessing the pointer but lose it when you try to access the data the pointer points at)

 

For games most data does not need to be sorted and when it has to be sorted you usually won't need to remove or insert elements in the middle of the set all that often, resizing arrays/vectors is however also very expensive but you can avoid that by allocating more memory than you need.

 

That said though, you should still learn about datastructures, there are far more ways to store data than arrays and linked lists and in games there are tons of situations where other structures are far more suitable.


#1SimonForsman

Posted 13 September 2013 - 03:11 PM

I am writing programs a couple of years (in c) but I never ever

used a linked list - it is always arrays - arrays are sufficient and

more efficient than linked list (as many say but i do not measure the

thing) Are there a real practical cases where usage of linked list 

would be better from efficiency reason han arrays - are they realy

used ?

 

The main advantage linked lists have is that you can remove or insert items in them at any position and still preserve the order of the data without having to move other data around, there are situations where that makes them more efficient than arrays or vectors.

 

Arrays and vectors on the other hand have the advantage of having all their memory in one large continous block which allows you to quickly access any element (as long as you or the compiler knows the size of each element you can calculate the adress for any element in the array) and as long as you don't store pointers the linear memory layout of the array will be far more cache friendly. (if you store pointers in an array you'll get the cache benefit when accessing the pointer but lose it when you try to access the data the pointer points at)

 

For games most data does not need to be sorted and when it has to be sorted you usually won't need to remove or insert elements in the middle of the set all that often, resizing arrays/vectors is however also very expensive but you can avoid that by allocating more memory than you need.


PARTNERS