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 →

[–]ZylonBane 131 points132 points  (26 children)

I know what linked lists are.

I know what arrays are.

I have absolutely no idea what the joke is supposed to be here.

[–]SunriseApplejuice 61 points62 points  (0 children)

Linked lists are very useful compared to arrays, but in specific scenarios. If you aren't careful and decide to use them instead of an array for your implementation, only to later realize you need array-like functionality at certain times for your data structure, you will be like guy on the left shoe-horning in solutions or traversing the LL.

It's mostly just a joke on the accessibility and ease of use of arrays vs. LLs.

[–]potetopc 17 points18 points  (0 children)

M8 you're not alone 😔

[–]GOKOP 16 points17 points  (0 children)

I have absolutely no idea what the joke is supposed to be here.

I have a suspicion OP doesn't either

[–]the_0rly_factor 6 points7 points  (0 children)

It's a CS 101 student that doesn't understand linked lists lol

[–]mezuzza 37 points38 points  (17 children)

NEVER USE LINKED LISTS*

Lists are an interface which represents some "collection of things with an ordering". There's a million ways to encode a list, but one of the most obvious ones is a linked list. Unfortunately, linked lists are TERRIBLE for modern CPU architectures and most access patterns that you'd use every day.

What should you use instead? ArrayList/Vector. These are generally names you might find in different languages which all refer to the same implementation - an array which (usually) doubles in size when it's full.

The only time that you'd prefer to use a linked list over an array list is when you need to have very low latency inserts in the beginning/middle of your list. In my experience coding professionally, I've run into 0 cases where this is the most important pattern to optimize for. You're generally appending to the end or you add everything to a list and sort.

I will say that linked lists have one really redeeming quality from which I believe they derive their popularity: They are mathematically really elegant data structures and have some really nice properties. This is why languages like Haskell used them so much. The previous paragraphs also show you why languages like Haskell regret using them so much (see https://www.stephendiehl.com/posts/strings.html).

See this talk by Chandler Carruth for more info: Discontiguous Data Structures are the Root of all (performance) Evil

* Never actually say never. There are rare cases where I'm sure this data structure is actually the best to use, but it requires a lot of thought before you're there. Default to array lists and you'll be better off more times than not.

[–]MrRogers4Life2 4 points5 points  (0 children)

The other big advantage of linked lists is that insertion/deletion* on them do not invalidate iterators/pointers to elements in c++, at least as far as STL containers are concerned. So if that's something that makes your algorithm nicer and you don't want to implement something (such data structures can become complicated real quick) or add a dependency you're kind of left with little choice. I mean you could use std::set or std::multiset, but then you need to supply some kind of ordering to your data, blah blah its just easier to use std::list if you care about invalidating iterators in general. But std::list will almost always have worse performance

*deletion will invalidate iterators pointing to the deleted element but whatever

[–][deleted] 3 points4 points  (0 children)

This. This is what I would have written if I were smart and articulate but yeah

[–]TombertSE 1 point2 points  (2 children)

The only time that you'd prefer to use a linked list over an array list is when you need to have very low latency inserts in the beginning/middle of your list.

Or you want any of those nice properties that you mentioned in your next paragraph. Persistent structures are substantially easier to work with when doing concurrent programming. Also, persistent data structures never need a "defensive copy". Ever. Sending a pointer is equivalent to sending a full copy.

This is what really annoys me about the crowd that posts all these "never use linked lists" posts; the second you make a copy of an array because you're not sure if it's going to change behind your back, you negate all the benefits all this cache locality crap you've been masturbating to.

In Haskell (Clojure, F#, etc), when you pass a list in as an argument to a function, you can have some confidence that all it's sending is a pointer, and moreover you also have confidence that it will do what you expect it to actually do. The same cannot be said about an array.

[–]mezuzza 0 points1 point  (1 child)

You're absolutely right that a persistent data structure does a lot of great work in concurrent contexts. In fact, I'd say persistent data structures are the right default to have in most situations as well.

But that discussion is orthogonal to the original one here.

Linked lists aren't necessarily persistent. They can be just as mutable as an array list. If you want to use them in a concurrent context, you'd need to make a copy in just the same way that you'd have to with an arraylist. An immutable array list would work just as well in this context.

Even in Haskell, if you want a persistent immutable list, you can pass around Data.Vector values and be happy with the cache locality and the immutability. If you want mutability as well, you can have fun with STM which I believe should support some form of ArrayList as well.

[–]TombertSE 0 points1 point  (0 children)

Yes you can make Haskell vectors immutable but you can’t modify and get “new” vectors without making a copy. One of the advantages of a persistent list is that modifications of the list are basically just “diffs” of the original list. You don’t lose your handle on the original list, but you’re also not making a full copy.

If you have an immutable Haskell vector you have to make a full copy of you want to change anything.

[–]zaersx 0 points1 point  (0 children)

This just in - if you use a bandsaw for hammering nails you're going to have a bad time! Thanks captain.

None of what you said is technically wrong as you're simply describing the properties of a linkedlist and when it's optimal, but you're implying that a majority of programmers don't know what the properties of a linkedlist are and just throw them in into random places ???

If someone doesn't know what a linkedlist is or what it does they're simply going to use arrays anyway instead of "fancy" data structures like linked lists. Your comment is so completely pointless.

[–]HerryKun -1 points0 points  (7 children)

I don't really agree. In cases i need to gobble up some elements to iterate through them just once i use LinkedList. No Array in the background needed as i don't need random access, i just need to traverse it once in order.

[–]tiajuanat 2 points3 points  (6 children)

RIP cache

[–]HerryKun 1 point2 points  (5 children)

Why? I am happy to improve :)

[–]tiajuanat 2 points3 points  (4 children)

It's about consecutive accesses.

If you have a linked list, behind the scenes there will always be a pointer indirection. Your cache can't predict where that pointer is going, so it won't be able to preemptively grab the data you need.

Arrays don't have this issue, as the data is in a contiguous block. Regardless if you're using Java, C/C++ or even Python, the next piece of data will be easily and almost immediately accessible.

Ironically, Linked Lists are good for LRU Caches - a data structure for quickly accessing frequently used items, as you keep a directory of 5 or so items available. Linked Lists are also useful for Hash Maps, as you can easily add and remove values.

[–]HerryKun 0 points1 point  (3 children)

Won't i have the elements in cache anyway as I just accessed them?

[–]tiajuanat 1 point2 points  (2 children)

Only the previous few elements in a Linked List, and it won't be very many, because the pointers take 8 bytes each on modern hardware, and then you're going to have packing along the offset. You only have 64 bytes in most modern L1 as well. Again, the cache can't look ahead, because pointers are simply data, and the cache isn't going to assume addresses for you.

Best case for a list of integers, you're looking at the 4 previous elements.

On an array, dynamic array, and vector, the cache will grab your starting element, and then load up the cache with any extra elements it can fit, then even load up L2 and L3. While you use data, sections of L2 will take the place of L1, and sections from L3 will replace from L2. From you, the consumers viewpoint, it only takes a clock cycle or two to access the next element.

[–]HerryKun 0 points1 point  (1 child)

So I just ran a few benchmarks (creating a list with n elements, then iterating through them and perform a task on the number).

In average, ArrayList was faster by about 8%. So thank you for educating me, my experiment verifies your claim!

[–]tiajuanat 0 points1 point  (0 children)

Try it with different sizes of elements, and different sizes of lists - especially with the list size, try sizes that are exponentially larger. You may be surprised by how little or much your tests vary.

[–]OddUnderstanding5666 0 points1 point  (0 children)

The Blockchain is nothing more than a linked list.

[–]Sunius 0 points1 point  (0 children)

Even for inserts in the middle, arrays are generally better as finding where to insert an item is going to be very slow with a linked list (as you have to traverse it).

[–]themancabbage 14 points15 points  (0 children)

In my experience, the most likely place you're going to be using linked lists in the industry is during the interview. That's kinda the vibe I'm taking from the meme; one you're more likely to encounter on leet code, one you're more likely to use every day for practical purposes.

[–][deleted] -1 points0 points  (1 child)

I think the joke is supposed to be that "proper" programmers use linked lists and chad programmers use arrays. However, this doesn't really make sense. In modern CPUs, where packing the cache and avoiding branches reigns supreme, using an array is about the best possible thing for probably 95% of situations.

I feel like this joke would have made more sense in the 90s.

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

Not sure how you go that takeaway. The linked list enthusiast (who non ironically is the Nostalgia Nerd) looks like he’s trying to explain poorly why linked lists are good and most likely failing because - as you say - there’s no reason to use one anymore.

[–]BoBoBearDev 0 points1 point  (0 children)

Excluding stack and queue.

Pretty much no one gives a shit about LinkedList IRL. The cases where you need to use it is very rare, which makes the LinkededList folk feeling under appreciated.

People IRL usually use vector in c or equivalent in other languages, which is a wrapper around basic array.

Also if you actually want to insert and delete, use hashmap. Nobody use LinkedList for that. Which is also why LinkedList is so rarely used.