Jump to content
  • Advertisement
Sign in to follow this  
fir

practica usability of linked lists

This topic is 2150 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 than arrays - are they realy

used ?

Edited by fir

Share this post


Link to post
Share on other sites
Advertisement

The only good reason to use linked lists is, IMO, if the size of the array isn't fixed and you have to resize it very frequently

Or if you need to insert or remove elements in the middle of the array very frequently while keeping the overall order of the elements (if the order doesn't matter removing an entry from an array is as easy as copying the last element to the position that you want to remove and decrement the size).

 

Most of the time (always) arrays will be faster due to better cache utilization and direct access to elements.

Edited by TiagoCosta

Share this post


Link to post
Share on other sites

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.

Edited by SimonForsman

Share this post


Link to post
Share on other sites

Stroustrup actually says that vectors are more efficient overall. Apparently the savings in insertion and deletion just don't add up to the cache misses that occur when traversing the list, or even the element search time to reach the insertion/deletion point. The vector can find an element and shove its data up or down very quickly, but the linked list takes a lot of cache-inefficient time to reach the element, and that outweighs the disadvantage of the shove.

 

Edited by Khatharr

Share this post


Link to post
Share on other sites

@up

 

so some say it is good to be used when there is a need for insertion when you need a specyfic order of records to be save -

but when in practice you really need correct order in such extent to use linked list ? - that is what I am asking about when you hold a characters or bullets or something like that you do not need an order (I never yet found such case ehere you need, and I am programming a couple of years)

Share this post


Link to post
Share on other sites

Linked lists are good when you have interconnected data structures with pointers to each other. You can delete one thing without having to re-shuffle, and thus invalidate all the existing pointers in to the data you re-shuffled.

 

Intrusive lists with cells allocated from a pool help make them nicer to the cache.

Share this post


Link to post
Share on other sites

Linked lists are good when you have interconnected data structures with pointers to each other. You can delete one thing without having to re-shuffle, and thus invalidate all the existing pointers in to the data you re-shuffled.

 

Intrusive lists with cells allocated from a pool help make them nicer to the cache.

 

this i could call maybe an array for content + list of pointers  not pure list maybe

 

When you would need such approach (interconnected with pointers) in practice ? Wouldnt it be easier rewrite it in array way stil?

 

(I am searching for the case when list is  really better than array because from my practic experiense it may seem, that it is a practically dead way of doing things - though maybe not, and I am writing oldschool c down here)

Edited by fir

Share this post


Link to post
Share on other sites

A common technique I use is an array containing the items and a next index. Using indices rather than pointers gives access as fast as a pointer (using unsigned so as to avoid sign conversion), and simple load/save since you can binary write and read the data without any pointer fix ups. For an example use case see this blog post.

 

I also tend to use a number of fixed sized arrays to contain the items, so the index now becomes a block-index and node-index. To add more memory you create a new block, which gives good cache locality and no need to copy data when growing the size of data.

Share this post


Link to post
Share on other sites

 

Linked lists are good when you have interconnected data structures with pointers to each other. You can delete one thing without having to re-shuffle, and thus invalidate all the existing pointers in to the data you re-shuffled.

 

Intrusive lists with cells allocated from a pool help make them nicer to the cache.

 

this i could call maybe an array for content + list of pointers  not pure list maybe

 

When you would need such approach (interconnected with pointers) in practice ? Wouldnt it be easier rewrite it in array way stil?

 

(I am searching for the case when list is  really better than array because from my practic experiense it may seem, that it is a practically dead way of doing things - though maybe not, and I am writing oldschool c down here)

 

 

I mean multiple lists of different objects, with each object having pointers to objects of the other types (in different lists). In my case, I have one list of physics objects, and another list of joints, with each joint having pointers to the 2 objects it joins. I.e. not pointers within a single list, but between lists.

Share this post


Link to post
Share on other sites
You probably going to use an array list over a linked list when you want to store list of something as a member variable, but understanding the idea of linked list is important because at times you need to implement the linked list data structure as part of an algorithm. The best example I can come up with is the memory heap. Free memory on the heap is stored as a doubly linked list. An array list would make memory allocation much more complicated and/or less dynamic. You will probably never implement a heap, but there are other examples.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!