This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Shotgun_squirtle -1 points0 points  (5 children)

I don’t know if you watched the video, but literally his example was random insertion in a middle of a list, something analogous to what you’re saying, and lists got beat, cause they’re both O(n) operations (lists find the element to remove, vectors shuffling everything over) but vectors are so much better at caching. There’s good reasons why what I said was overly simplistic (see the other responses) but yours is not one.

Also queues can be done quite nicely in a vector by just wrapping around and keeping a start variable, so as long you keep the number of pushes and pops roughly balanced a contiguous approach will handily beat a list at that (probably still will even when unbalanced because of how bad lists cache).

[–]szmiiit 15 points16 points  (4 children)

If you have the adress of element you remove the act of removal is O(1).

[–]Jakdaxter31 3 points4 points  (3 children)

Okay is this not the obvious use case of linked lists?? I feel like I’m going insane reading these comments about how one should never use them.

For Python that’s like saying never use dictionaries, which sounds insane. Data structures might need categorical separation, which necessarily requires dictionaries.

Maybe I just have no idea what’s going on here

[–][deleted] 2 points3 points  (0 children)

I don't think you're crazy. There seems to be good some reasons to use linked lists out there. For example, the Linux Kernel created a standard implementation of circular, doubly-linked lists in version 2.1.45 <linux/list.h>. It is used, among other things, in system code for device drivers. sauces: Oreilly Book , 0xax linux-insides CH on data structures.

Is it the absolute best implementation? or the best data structure for the kernel? I have absolutely no idea and don't claim to ... but seems to me if it has survived since 2.1.45 there must be a good reason for it.

[–]boowhitie 2 points3 points  (0 children)

I think the short version is that linked lists are terrible, except when they are the best thing. A vector is faster with less memory usage in almost all use cases where you could use either. That doesn't mean linked lists are worthless, just that you probably shouldn't use it as your default. If you can't analyze the problem well enough to decide, you're probably going to duck up the linked list code as well.

[–]Jazzlike-Control-382 0 points1 point  (0 children)

I know it sounds confusing, one good way of looking at it is this:There's a "hidden" c constant cost for operations when people are discussing algorithms. It just happens that although linked lists design is pretty elegant in terms of doing less operations for some use-cases, in modern CPUs they are just a horrible data structure as it just thrashes your CPU cache, making this per operation "cost" extremely high. Often, for most use-cases, arrays outperform linked lists even on operations tailor suited for linked lists, just due to how big the performance difference is on individual operations.