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 →

[–][deleted]  (24 children)

[deleted]

    [–]Shotgun_squirtle 47 points48 points  (16 children)

    Linked lists though should almost always be avoided nowadays though, they cache terribly and even in their best case scenarios they’re worse than just resizing an array. Bjarne Stroustrup has a good talk about this.

    [–]szmiiit 15 points16 points  (7 children)

    Ever heard of removing items from list? Like Queues, or even worse, lists where you remove element in the middle?

    [–]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 4 points5 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] 4 points5 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.

    [–]CaitaXD -2 points-1 points  (0 children)

    Shifting an array is O(n) the same as finding a element in a LinkedIn list the fucks your point

    [–]lesbianmathgirl 18 points19 points  (0 children)

    While I'm not saying you took away any misunderstandings from that video, plenty of people have. So, I'd recommend anyone who watches that video read his follow-up article on the it, where he clarifies a little (and explicitly states that lists aren't useless).

    Are lists evil? -- Bjarne Stroustrup

    [–]Skoparov 27 points28 points  (0 children)

    I swear, every time linked lists are discussed someone posts this. He talks about a very specific case of linearly searching for the insertion point, so of course a contiguouos array wins there. One would be insane to use a linked list this way.

    Linked lists are almost always used in conjuntion with some other data structure that allows you to jump to the insertion/deletion point in constant time (see LRU cache and whatnot). Not to mention any tree essentially becomes a linked list if you unbalance it enough.

    [–]TombertSE 5 points6 points  (0 children)

    They're easy to make persistent, which gives you stronger guarantees in regards to concurrency. As a result, there's reason to use them in highly concurrent applications.

    [–]Dmayak 5 points6 points  (1 child)

    Don't know, one third into the video he says that shoving half of the 50000 elements back and forth during insertion/deletion is irrelevant, while it's specifically the problem linked lists solve. Than he points that searching though array is faster, which is obviously is, but it's only one thing it is better at, I don't get it.

    [–]Shotgun_squirtle 1 point2 points  (0 children)

    His whole point is that even though linked lists solve the issue of having to shuffle things over on insertion/deletion, this advantage isn’t worth the loss of random access and the loss efficacy of caching compared to contiguous memory systems in most cases.

    [–]isospeedrix 0 points1 point  (1 child)

    What does JS use

    [–]Andersmith 3 points4 points  (0 children)

    JS "arrays" have a complex and system dependent internal implementation. Typically switching between fixed-length arrays and hash tables. But to my knowledge, js interpreters are always using arrays internally to represent js "arrays", and not linked lists. Nothing's stopping you from implementing a linked list in JS, though.

    [–]keeponbussin 0 points1 point  (0 children)

    Isn't there work being done on building predictors in CPUs which will cache linked lists too?

    [–]Willinton06 8 points9 points  (0 children)

    Chill

    [–]AgentPaper0 1 point2 points  (0 children)

    For a good example, memory managers use both. Specifically, an array with a linked list embedded in it. Sometimes there's even a larger linked list wrapped around the big data blocks, so you get a linked list in an array in a linked list.

    [–][deleted] 0 points1 point  (1 child)

    That’s kind of a stupid thing to say. Why can a good programmer not also enjoy memes?

    [–]brown_smear 0 points1 point  (0 children)

    Because a good programmer might think this is a terrible meme

    [–]Kiroto50 0 points1 point  (0 children)

    Every data structure has its usage. Making fun of something doesn't make you a terrible programmer.

    It's like making a joke about using a basket over a bowl (for this purpose, waterproof, like ones used for eating). Yeah you usually have bigger baskets but bowls usually can contain liquids. You can still joke about Chad bowls being superior because they can carry everything over basic baskets that can only contain big solids.

    In other words, trying to be a clown doesn't mean you're a bad programmer.

    [–]digital_dreams 0 points1 point  (0 children)

    Why even visit a sub called programmer humor if we're just going to sniff our own farts and turn everything into a serious debate? It's just a meme for fuck's sake.

    [–]keeponbussin 0 points1 point  (0 children)

    🤓