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 ?
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.
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.
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.
@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)
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.
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)
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.
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.
