How will linked lists ever recover?
Old: >>55047417
Who cares when superior data structures like skip lists exist?
>>55062866
this didn't need a new thread you fucking mong
>>55062976
There's still people on /g/ who use linked lists
Friendly anons don't let other anons use linked lists
>>55062866
>>55063023
FUCK OFF and kill yourself, we do NOT need another thread full of what is probably the STUPIDEST fucking retards I've even seen on /g/.
Please delete this fucking thread.
>>55063070
I bet you're a triggered freshman who thought he was hot shit for his knowledge of linked lists and babby big oh but had his dreams crushed by the realization that cache utilization actually matters
>>55062940
Skip lists are vastly overated.
They suffer from shit locality too.
>>55062866
Fake graph is fake
I will keep using lists when processing Lisp-language, writing macros and such.
If you plan on storing thousands of items in list then you should reconsider because it's not the fastest data structure.
>>55062866
when OP learns how to make a better memory allocator for the linked list
>>55063154
Only if you use a shit architecture that complicates things with caches
>>55062866
>repeatedly and frequently traversing the linked list
son, you've gone full retard.
>>55063180
I see the linked list internet defence force has arrived
>>55063123
I'm not a retard who thinks the cache doesn't matter, so no I'm not who you think I am.
>>55063242
So why are you so pissy then?
>>55063214
Without extensive caches and other memory tricks (most of them don't even work without a cache) your modern CPU wouldn't be much faster than chips from the 90s.
>>55063261
Because there are retards out there who think copying large blocks of memory is an O(1) operation.
>>55063391
Dem gigabit wide data buses tho famalam
>>55063391
>what is amortized analysis
Oh, so you are actually retarded
>>55063494
No amount of buzzwords will change the fact that copying data blocks larger than the largest register size on your CPU will require fucking iteration.
amazing how many people don't know when linked lists are appropriate; it's like they can't reason at all
>>55063522
>amortized analysis is a buzzword now
you can't invalidate things just by calling it a meme
When are linked lists better than vectors?
>>55063522
BUZZWORDS?
Amortization is a thing you fucking Muppet
>>55063770
When you need to insert and remove elements only at the front or back, and never need random access
i.e. a FIFO or LIFO.
>>55063770
When you have large objects that have an identity and can only be part of one list or "queue" at a time.
You might have lists of running and waiting processes, or open tabs and recently closed tabs.
Even then, it might be better to have an array of pointers to them instead.
>>55063713
>>55063780
Warping your view doesn't somehow make the operation less expensive.
>>55063833
It's really not about what you're using them for but how you use them. A list is no different from an array in that it lets you store elements. These days you really don't need to worry about what you're storing anymore.
And storing pointers to things is shitty in almost all cases for the obvious safety reasons. An array of dangling pointers is an atomic bomb without an on/off switch.
>>55063791
i can make O(1) LIFO and FIFO using a single array.
they can be amortized to O(1) if you want rhem dynamic but max fixed size is always prefered unless needed.
>>55063859
its less expensize compared to the ops your linked list will rape your cache with
Put your linked lists in arrays and stop worrying m8s.
>>55063791
>or back
no, appending to an array is faster
>FIFO or LIFO
they're both better with arrays
>>55063833
>can only be part of one list or "queue" at a time
why? an object can be part of multiple lists/queues at the same time
>>55063866
>storing pointers to things is shitty
>array of dangling pointers
you're clearly incompetent
>>55063868
A FIFO and LIFO implies dynamic sized storage. The whole point of them is constant time growth on either end.
Of course in fixed size you can duplicate that as an array but then you've missed the point.
And a dynamic size array that lets you modify at either end in amortized constant time is both impractical and esoteric as fuck.
In other words, be quiet and use a deque.
>>55063894
>no, appending to an array is faster
No it isn't. Both are constant time and a list is faster if you need to resize the array, you piece of dumb shit.
>FIFO or LIFO
>they're both better with arrays
In what way?
>>55063894
What do you think you gain by allocating in one place and storing pointers in another? You're actually just wasting memory.
>>55063881
That doesn't make in O(1) fucktard.
>>55063969
Correct, it makes it amortized O(1)
>>55063908
it doeant necessarily tho. just look at routers. Alot of shitty ones will use a fixed size FIFO inplemented as an array.
using something that could grow indefinitely kills routers when under stress as the load gets worse as the queue grows and the customers will feel the packets never making it
>>55063988
I'm talking about what the data structure allows you to do efficiently, not actual uses of it.
And in the case you listed you could use a deque just as good as a fixed size array.
>>55063908
>dynamic size array that lets you modify at either end in amortized constant time is both impractical and esoteric
your lack of programming experience is showing
>use a deque
can be efficiently implemented with an array
>>55063931
>and a list is faster if you need to resize the array
have you tested it? you'd be surprised
>In what way?
they're more efficient
>>55064027
I'm not even going to respond to this, you clearly don't understand a thing I've said.
>>55064048
well I don't know which retard you are, but considering you're a retard anyway, I don't give a shit about your answers
>>55064025
except its not. theres no reason to use a deque in a router where the queues have fixed sizes that can be easily implemented as a circular array at no cost.
>>55064082
>circular array
whoooa, easy with the "impractical and esoteric" implementations, you might scare this shitter >>55063908
>>55063979
Which is completely and utterly useless because it doesn't represent the actual time complexity of the operation.
Get your shit memes out of here.
>>55064159
you dont know what amortized means do you?
i bet you think they are doing copies and increases every insert
>>55062866
Is there a good reason for yet another thread on the same subject?
>>55064223
Because janny is too busy fapping to traps to notice bait threads.
>>55064151
Struck a nerve, have I?
:3
For my game, it doesn't make much of a difference to use an array over linked lists for entities, since entities act as containers for components and cache locality is a moot point with that much indirection. Speed improvements would be negligible, since an array would have to hold pointers to entities anyway. The pointers would be contiguous in memory and that's it.
Linked lists, on the other hand, benefit from ease of implementation and insertion/removal of elements during iteration, which happens quite frequently when regrouping entities depending on game state.
Also, a well designed program should be able to have any list implementation replaced with a different kind with little effort. Premature optimization is a waste of time. Get it working first, THEN tweak for performance.
>>55062866
>space-time tradeoff
LOL fUcKiN.kill.self.com!!1 you FUCKING kike
>>55064449
It's no tradeoff
You get better both with vectors
>>55064397
You could allocate your entities from a contiguous block of memory.
>>55064671
That's probably what I'll end up doing later on. It'd actually be a pool allocator for the various components though, since entities are just eight byte UUIDs with an optional convenience class as a wrapper for frequent operations.
>>55064397
I implemented a generic dynamic array in less than 50 lines of C yesterday
It's trivial to implement
>>55062866
wow you dont fucking say, nice 1st year cs assignment
>>55062866
Hash lookup master race !
>>55065287
I remember doing something similar first year. We had to implement treaps as well and do comparisons.
>>55063070
>>55063242
>>55063391
>>55063522
>>55063859
>>55063969
>>55064159
neck yourself m8, and take CS101 again.
>>55063908
>And a dynamic size array that lets you modify at either end in amortized constant time is both impractical and esoteric as fuck.
It's actually a very simple thing to implement, roughly 25 lines of code in C. Unless you consider remainder or bitwise and to be 'esoteric' in which case you need to go back to grade school. Speed of array implementation is much better than linked list due to better data density and cache locality; plus the constant trips through alloc and free needed by the dynamic list implementation makes its performance even worse than you can imagine.
>>55064182
>you dont know what amortized means do you?
it's pretty clear he doesn't.
>>55062866
>std::list insert at beginning
bullshit.
