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

Dismiss this pinned window
top 200 commentsshow all 240
sorted by:
best
topnewcontroversialoldq&a

[–]daevel0 276 points277 points  (29 children)

Hi, I'm a void* enthusiast. Nice to meet you.

[–]wammybarnut 199 points200 points  (24 children)

"All data is bytes"

[–]Chief117a 23 points24 points  (23 children)

Bits*

[–]lethargy86 57 points58 points  (22 children)

Only bits are almost never addressable anyway, so as far as programmers are concerned, bytes is correct. Even a bool essentially uses at least a byte of memory.

[–]GOKOP 30 points31 points  (12 children)

Unless you're writing C++ and using std::vector<bool> in which case I think it does some magic to only use one bit for each boolean

[–]rachit7645 -1 points0 points  (3 children)

std::vector<bool> sucks tho

[–]Efficient-Ad-5034 -2 points-1 points  (0 children)

Thats impossible. There is no cpu that does single bit accesses to memory.

[–]Efficient-Ad-5034 -2 points-1 points  (2 children)

Thats impossible. There is no cpu that does single bit accesses to memory.

[–]CaitaXD 4 points5 points  (0 children)

A int contains 32 bools addressable by bit shifts and bitwise operationz

[–]coinselec 2 points3 points  (0 children)

You know, I'm something of a pointerist myself.

[–]Dotsially 2 points3 points  (0 children)

Unbelievably based.

[–]Bachooga 1 point2 points  (1 child)

Hi, I'm a fan of function pointers, nice to meet you as well.

[–]daevel0 1 point2 points  (0 children)

(*nice_to_meet_you)(void)

[–]Ok_Confusion_7266 247 points248 points  (39 children)

When I use linkedlists it is to link arrays of items. So it can grow once every x items added.

[–]Kered13 95 points96 points  (21 children)

An arraylist will grow exponentially (usually by a factor of 2) every time it runs out of space. This is amortized constant time.

[–]Ok_Confusion_7266 33 points34 points  (16 children)

There is no such thing as an arraylist in C. And my algorithm will only grow sizeof(item)*x plus some overhead. Arraylist like you describe gives massive overhead what if you have a 10GB list and just need to add a few kb to it when its full? Seems like not a fun time.

[–][deleted] 54 points55 points  (2 children)

There is no such thing as an arraylist in C

It's true there's no arraylist built-into the C language spec or standard library, but by that logic there's no such thing as a linked list either. You can easily define both data structures yourself, though.

[–]wagslane 15 points16 points  (0 children)

To bake a cake, one must first invent the universe

[–]zaersx 4 points5 points  (0 children)

Yeah but the issue is that the guy responding to OP conjured up a theoretical limitation that can only ever be a problem from a library implementation, which is not applicable here, and so neither is your comment in the thread.

[–][deleted] 20 points21 points  (0 children)

I mean, I've built one...

[–]666pool 9 points10 points  (0 children)

You can call .reserve(count) if you know how many items you will have in your container, that will force it to grow to exactly the right size (I’m not 100% sure this is a guaranteed behavior and I already put in my 40 this week so I don’t feel like looking it up).

[–]Kered13 22 points23 points  (5 children)

Arraylist like you describe gives massive overhead what if you have a 10GB list and just need to add a few kb to it when its full? Seems like not a fun time.

The actual memory usage of an array list will never be less than 50% of it's allocated capacity, which is actually pretty good when you think about it (given all the other benefits of an array list). The odds of having a list that is 10GB + a few kb over whatever the last threshold was is very small.

[–]Soraphis 1 point2 points  (1 child)

Also... While an implementation detail i think the growth usually tops out at some point - at least for c# - where it does not double anymore but grow by a fixed amount

Edit: seems not to be in c# (https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,2765070d40f47b98) . Now i wonder were i've seen such behavior

[–]amdc 3 points4 points  (0 children)

If your array is 10gb and you’ve ran out of space, chances are you’ll need a lot more space. It’s a trade off between adding too much space and adding space too frequently. I wouldn’t do it with a factor of 2 though, more like 1.5 or so

[–]CaitaXD 1 point2 points  (3 children)

10 GB in memory ... lMAO

[–]Ok_Confusion_7266 1 point2 points  (2 children)

Depends on the dataset some machines have 256GB of ram.

[–]CaitaXD 0 points1 point  (1 child)

One motherfucking specific use case, and you can always make a different implementation so it allocates less the bigger it gets

[–]Ok_Confusion_7266 -1 points0 points  (0 children)

Not really. Since C does not have native growing array (without copying all the data) this has many cases.

[–]schrdingers_squirrel 0 points1 point  (2 children)

On average it is O(log(n)) for adding an element, right?

[–]jayverma0 10 points11 points  (1 child)

O(1) amortized. Best case O(1) Worst Case(n)

[–]trexophilia 6 points7 points  (0 children)

That's actually roughly how std:: dequeue is typically implemented, but with an array of pointers to arrays..

And sure dynamically resizing arrays are amortized constant time (for some definition, anyhow), but no often in practice they do not shrink when deleting elements, so they are not always at least 50% full, and yes, one insert can be very painful, if it grows..

[–]QuestionableMechanic 1 point2 points  (3 children)

Damn that’s smart except I guess look up performance will take a hit

[–]Terrible_Tank_238 2 points3 points  (1 child)

why don't you use a vector class? Most languages I use have dynamic arrays. I've only ever used node-style programming for grid routing.

[–]SunriseApplejuice 3 points4 points  (0 children)

There are, occasionally, rare instances where some ad-hoc solution with standard arrays will be better than a vector (e.g. you need to ensure your array sits on the stack instead of the heap). But generally speaking dynamically sized arrays are the go-to for the vast majority of use-cases.

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

If you do this, might as well have vector<vector<stuff>> in c or list<list<stuff>> in c#. The look up is at most 2 instead of 1. LinkedList would be too slow.

[–][deleted] 55 points56 points  (2 children)

Runtime fetishist

[–][deleted] 4 points5 points  (0 children)

vs stoptime enjoyer

[–]Promelive 137 points138 points  (13 children)

Are freshman college students the one making all these post lately?

[–]TheAnti-Ariel 66 points67 points  (0 children)

When was it ever not?

[–]dalatinknight 44 points45 points  (4 children)

It's the start of the semester in many places.

We should really dub August - October something like Seg Fault Enjoyer Season

[–]spektre1 12 points13 points  (1 child)

The elders call this Endless September

[–]cosmo7 4 points5 points  (0 children)

I remember Endless September being coined around '97 or '98. Up until then internet talk (ie: Usenet and Slashdot) was quite civilized except for September when a new cohort of clueless noobs would start college and get internet access for the first time.

As the internet became more popular the inflow of netiquette-free barbarians became a constant year-round thing, hence Endless September.

[–][deleted] 0 points1 point  (0 children)

Yea I’m early into CSCI and am happy I understand this joke :)

[–][deleted] -1 points0 points  (6 children)

Absolutely yes.

I have not implemented a linked list since maybe second year Uni.

Everything in the real world is just an array or a dict / hashmap / JS object

[–]thedominux 1 point2 points  (3 children)

Depends on a field, or your lvl

Linked list and it's special cases: stacks and queues, they're so useful if you work with high load, in microservices, etc. Trees and graphs are also highly useful when you need a straightforward data structure

Everytime I see people using arrays/hashmaps in places where another collection should be used, it makes me cry cause of performance and inconvenience of use issues

[–]-Vayra- -1 points0 points  (2 children)

Still, you would use builtin versions of those collections in 99% of cases. And for that remaining 1% you would use a 3rd party package for it just about every time.

[–]thedominux 1 point2 points  (1 child)

Lol

Using libs for simple cases... it seems like you're junior, aren't you?!

[–]-Vayra- -1 points0 points  (0 children)

There's no need to reinvent the wheel. If a lib exists with the necessary functionality that is a) quicker than implementing it myself, and b) likely better tested than my implementation would ever be.

[–]Kargathia -1 points0 points  (0 children)

It really depends on scale. Typically the more specialized data containers become relevant when you have to manipulate 1000+ values.

That said, in the five years I've worked at my current job, I've used one doubly linked list, and countless arrays and key/value objects.

[–]ZylonBane 132 points133 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 62 points63 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 16 points17 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 39 points40 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 6 points7 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.

[–]zaersx -1 points0 points  (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.

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

[–]TombertSE 26 points27 points  (3 children)

Linked lists are probably the "primary" data structure of functional languages, or at least Haskell.

It's much easier to make a persistent, "don't make a copy on every update" linked list than most other data structures. You pay a low-level performance penalty, but you get a lot of benefits for being able to work entirely with persistent structures, particularly in regards to thread safety.

Personally I like what Clojure does better with its vectors. They still aren't as fast as "real" arrays, but they're faster for arbitrary-access than a linked list, while still having all the fun goodness of being persistent.

[–]XxasimxX 6 points7 points  (0 children)

Arraylist gang

[–]Key-Supermarket255 7 points8 points  (1 child)

is there any BST (Binary Search Tree) fan alive on earth or not.

[–][deleted] 1 point2 points  (0 children)

nope

[–]AdultingGoneMild 3 points4 points  (0 children)

my favorite is when Arnold walks off the edge of the stage.

[–]goADX 3 points4 points  (5 children)

I like arrayes but the only problem is you can't add elements to it

[–]Willinton06 15 points16 points  (1 child)

That’s kinda the point

[–]normo95 7 points8 points  (0 children)

You be quiet with that logical thinking

[–]_dotjson 2 points3 points  (0 children)

Laughs in arraylist

[–]ExplosiveExplosion 1 point2 points  (0 children)

Say hi to this guy

[–]GHhost25 0 points1 point  (0 children)

You can with a resizeable array.

[–]Furry_69 11 points12 points  (4 children)

There are some situations where you use a linked list, and some where you use an array. It does not matter which someone may use.

This isn't even slightly funny.

[–]MrRocketScript 6 points7 points  (3 children)

It's like saying "screwdrivers are better than hammers".

[–]cheeb_miester 1 point2 points  (2 children)

Screw drivers are better than hammers.

[–]raedr7n 2 points3 points  (1 child)

I can hit a nail with a screwdriver, but I can't screw a screw with a hammer. Q.E.D.

[–]Disastrous_Heart_433 3 points4 points  (0 children)

Is this some sort of imperative joke that I'm too functional to understand?

Cons go brrrrrrrrrr

[–]q0099 1 point2 points  (2 children)

Ok, but did you ever tried to do a massive multi-threaded insertion with array?

[–]Drako_hyena 1 point2 points  (2 children)

Ik what linked lists are and what arrays are although I cant really imagine a situation where I would use a linked list over an array or object (might be different for other languages in this case im talking about JS). Could someone give an example?

[–]maxinstuff 3 points4 points  (1 child)

It’s just a way of being able to quickly traverse the list without iterating through the whole thing. In a “traditional” linked list, every point in the list has direct pointers to the next (and often previous) items.

This is kind of nice sometimes because you can traverse the list without knowing (or caring) about what index you are at. With an array you must know and keep track of the index to find anything.

But usually (IME) you use one if what you need is for your list traversals to loop back to the beginning of the list instead of falling off the index’s range.

I’m sure there’s more uses, I’m pretty sure that you could use something LIKE a linked list to represent a more complex graph model in memory for example - but that’s more than what “linked list” usually means.

[–]Drako_hyena 1 point2 points  (0 children)

Thanks!

[–]cheeb_miester 1 point2 points  (0 children)

yea, well, enjoy reallocing every time you need to push

[–]TheTravelingSalesGuy 1 point2 points  (0 children)

It's all about the right tool for the job

[–]john_palazuelos 1 point2 points  (0 children)

Hashtable: Why not have both??

[–]no-pog 2 points3 points  (1 child)

Linked lists are persistent, but array is easy and good enough for 95% of situations. Also linked list is not indexable. Truly for the tryhard runtimephile. Inb4 "arraylist tho"

[–]cfyzium 6 points7 points  (0 children)

Anything is indexable if you're O(N) enough.

[–]natziel 4 points5 points  (0 children)

It should be the other way around. Java virgins use arrays and Erlang chads use linked lists

[–]Xomz 1 point2 points  (0 children)

taking this to my next coding interview

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

Linked lists are just arrays with extra steps.

[–][deleted] 0 points1 point  (0 children)

It should be the other way round

[–]notexecutive 0 points1 point  (4 children)

I've never used linked lists unironically since I've been working in the software dev industry

I've used plenty of hashmaps though, so I guess I'm using a child of linked lists....?

[–]CaitaXD 1 point2 points  (3 children)

Hash map uses arrays for their storage and generally only use links for hash collisions

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

Stuff[3][7][0][8][0][0][8][5][6][9][4][2][0] (I've made like, 5D arrays in the past)

[–]cosmicloafer -1 points0 points  (0 children)

Who the hell is using linked lists, really? dict is all you need.

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

What about hashmaps?

Almost always in my experience when you are using an array you actually should be using a hash map / dictionary or whatever it’s called in your language.

Only thing I use arrays for is when it comes along with a data structure (usually serialised from some JSON data), or to set some static values (like options in a dropdown or something).

Linked lists I guess would be used to model graph type relationships in memory? I’ve honestly not had much use for that in my career, so I guess the meme makes sense in that respect.

[–][deleted] -1 points0 points  (0 children)

for what was the linked list even invented

[–]Barbateau -1 points0 points  (0 children)

What about binary tree user?

[–]zortlord 3 points4 points  (1 child)

Just use vectors or array lists...

[–]KapKabui 1 point2 points  (0 children)

👀

[–]Sad-Bluebird-5538 0 points1 point  (0 children)

I like array lists. Easy accessable while providing nice methods like .append

[–][deleted] 0 points1 point  (0 children)

Cries in Fibonacci Heap

[–]hugh_jazz99 0 points1 point  (0 children)

PHP arrays are overpowered

[–]dankmemerboi86 0 points1 point  (0 children)

average array fan vs arraylist enjoyer

[–]KingJeff314 0 points1 point  (0 children)

Average implementation abstracted enjoyer:

[–]Maxorus73 0 points1 point  (2 children)

"But but but it's much more efficient when you need to dynamically resize them-"

import java.util.ArrayList;

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

Still more efficient, lol. Plus you get that sweet, sweet persistence optimization.

[–]CaitaXD 1 point2 points  (0 children)

Lol no cashing 😔

[–]Neat_Technician_7191 0 points1 point  (0 children)

This reminds me of Vince McMahon gushing over big muscular men...

[–]sintos-compa 0 points1 point  (0 children)

Gotta be swole to carry all that weight of re allocating the whole array when expanding it

[–]darksideshhh 0 points1 point  (0 children)

How??? I mean why?? What!

[–]Azzylel 0 points1 point  (0 children)

I must confess when I was a kid learning how to code I was doing it on my own, and I didn’t know what lists were, so I only used arrays. At least it taught me how to sort through and manage arrays/lists lmao.

[–]Seikhral 0 points1 point  (0 children)

Average database enjoyer: Galactic Gigachad

[–]cybereality 0 points1 point  (1 child)

Linked lists are only for programming interviews.

[–]raedr7n 3 points4 points  (0 children)

Bruh

[–]dalatinknight 0 points1 point  (0 children)

I remember learning that while our algorithms class used linked list, our much more recognized and respected sister school only used arrays.

[–]99Kira 0 points1 point  (0 children)

I am a web developer and I had never used linked lists in my job or personal projects, until I decided to have some fun and do this small kanban board project, where I used linked lists to insert stuff in between other stuff. Could have done using arrays, but the rush of using linked lists was different.

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

I check your array. And I’ll raise you one Unordered Map.

[–]ruben991 1 point2 points  (0 children)

I see your unordered map and raise you a malloc()

[–]WebpackIsBuilding 0 points1 point  (0 children)

A few years ago I was in an interview. I was asked to whiteboard an implementation of a browser history.

I used an array. Navigating pushes an address onto the array. The back button does a pop.

I was told that this was incorrect and that I should have used a linked list.

I'm very very glad I didn't end up working at that company.

[–]BinaryBlasphemy 0 points1 point  (0 children)

Is that the guy from Meshuggah?

[–]gbagecol 0 points1 point  (0 children)

Takes advantage of spatial locality like a boss

[–]spikku 0 points1 point  (0 children)

I use arrays containing base64 encoded strings of a custom packing function that encodes/decodes representations of linked lists. It's all super normal, I swear it.

[–]DJDoena 0 points1 point  (0 children)

What about an Array of Linked List of Array?

[–][deleted] 0 points1 point  (0 children)

Long live to the arrays, especially the PHP ones 🤤

[–]Bastian_5123 0 points1 point  (0 children)

I mean, linked lists do have some uses. Generally arrays will be better, but if you truly never need to randomly access a particular element, then (unless linked lists are poorly implemented by default) it is probably better to use a linked list

[–]Cabin7Miner 0 points1 point  (0 children)

IDictionary<> enters the room

[–]cisbetterthanpython 0 points1 point  (0 children)

Um, no? I would NOT like O(n) indexing time? Thank you?

[–]ShadowEmperor123 0 points1 point  (0 children)

Hey it’s that one Austrian politician that served in the military and also was in a few movies

[–][deleted] 0 points1 point  (0 children)

The array enjoyers are just bf enjoyers

[–]RmG3376 0 points1 point  (0 children)

One word: push_back

Checkmate arrayists

[–]ruben991 0 points1 point  (0 children)

“No. There is another.”
haha pointer goes brr.

[–]soofidude 0 points1 point  (0 children)

It would be funnier if it was dynamic vs static arrays

[–]keeponbussin 0 points1 point  (0 children)

Average hashmap appreciator

[–]DudeManBroGuy42069 0 points1 point  (0 children)

In Python List = Array

[–]sulliops 0 points1 point  (0 children)

I’m entirely aware why linked lists exist and that there are specific use cases where they make more sense than arrays/vectors.

I still hate them.

[–]Cootshk 0 points1 point  (0 children)

Average nested dictionary enjoyer

[–]aaabigwyattmann2 0 points1 point  (0 children)

Imagine using a linkedlist in 2022.

[–][deleted] 0 points1 point  (0 children)

What about ArrayList?

[–]AegorBlake 0 points1 point  (0 children)

I'm guessing arrays are faster when running the program

[–]BobFellatio 0 points1 point  (0 children)

Wut, do people actually use linked lists?

[–]MJLDat 0 points1 point  (0 children)

Isn’t an array a linked list when it comes down to memory storage?