Linked lists on suicide watch thread #2

How will linked lists ever recover?

Old:

Who cares when superior data structures like skip lists exist?

this didn't need a new thread you fucking mong

There's still people on Sup Forums who use linked lists

Friendly anons don't let other anons use linked lists

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 Sup Forums.
Please delete this fucking thread.

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

Skip lists are vastly overated.
They suffer from shit locality too.

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.

when OP learns how to make a better memory allocator for the linked list

Only if you use a shit architecture that complicates things with caches

>repeatedly and frequently traversing the linked list

son, you've gone full retard.

I see the linked list internet defence force has arrived

I'm not a retard who thinks the cache doesn't matter, so no I'm not who you think I am.

So why are you so pissy then?

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.

Because there are retards out there who think copying large blocks of memory is an O(1) operation.

Dem gigabit wide data buses tho famalam

>what is amortized analysis
Oh, so you are actually retarded

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

>amortized analysis is a buzzword now
you can't invalidate things just by calling it a meme

When are linked lists better than vectors?

BUZZWORDS?

Amortization is a thing you fucking Muppet

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.

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.

Warping your view doesn't somehow make the operation less expensive.

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.

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.

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.

>or back
no, appending to an array is faster
>FIFO or LIFO
they're both better with arrays
>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
>storing pointers to things is shitty
>array of dangling pointers
you're clearly incompetent

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.

>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?

What do you think you gain by allocating in one place and storing pointers in another? You're actually just wasting memory.

That doesn't make in O(1) fucktard.

Correct, it makes it amortized O(1)

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

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.

>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
>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

I'm not even going to respond to this, you clearly don't understand a thing I've said.

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

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.

>circular array
whoooa, easy with the "impractical and esoteric" implementations, you might scare this shitter

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.

you dont know what amortized means do you?

i bet you think they are doing copies and increases every insert

Is there a good reason for yet another thread on the same subject?

Because janny is too busy fapping to traps to notice bait threads.

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.

>space-time tradeoff
LOL fUcKiN.kill.self.com!!1 you FUCKING kike

It's no tradeoff

You get better both with vectors

You could allocate your entities from a contiguous block of memory.

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.

I implemented a generic dynamic array in less than 50 lines of C yesterday

It's trivial to implement

wow you dont fucking say, nice 1st year cs assignment

Hash lookup master race !

I remember doing something similar first year. We had to implement treaps as well and do comparisons.

neck yourself m8, and take CS101 again.

>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.

>you dont know what amortized means do you?
it's pretty clear he doesn't.

>std::list insert at beginning
bullshit.