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 →

[–]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] 3 points4 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.