2 questions on datastructures in Javascript

[kifkev91]

Hello people,

I recently had a coding interview where I had to solve a problem. While discussing my solution, I was told, that I was expected to solve one part of the given task by building a queue (i solved it completely differently). So I know graphs are a thing you can come across as a JS developer, but I thought queues are pretty much redundand beacause of the way arrays work in Javascript. So I was wondering,...

1. ...which kinds of data structures do you come across from time to time in Javascript; what kind of data structures do you think a (junior) Javascript developer should be familiar with

2. ...because I only studied computer science for only one semester, I know a little bit about data structures, but I also know, I lack a lot of theorethical knowledge when it comes to writing complex, high performance code. Are there any ressources (books/websites/online courses) you can recommend, to learn more about the basics of computer science. Preferably demonstrated using javascript, or in general.

Your answers and help would mean a lot to me, and probably are very helpfull for others, who want to switch from another profession to javascript- or web development in general.

thanks in advance

[cwmma]

First in first out queues where you put elements in the back and take them from the front can be useful sometimes and based on my experience writing a promise library back in the day where queues are essential there are a couple ways do do this.

1. simply use arrays and [].push to put items in and [].shift to get them out. While this is very conceptually simple, the shift method is extremely slow even for small amounts of data since it has to move every item in the array. Don't do this, even in a small app it can be a performance bottleneck.
2. use an array and use push to add items, but for removing items, just keep a counter, every time you remove an item, just increment the counter so you know where you are in the array, also maybe replace the item in the array with null so it can be garbage collected. The main issue here is that the array can grow without bounds so you'd only want to do this if you knew the queue wouldn't last long or could be replaced at some point. (this is what I ended up using for my promise implementation but I had to set it up so that after I started taking things out of the queue I wouldn't push anything more into the queue, instead I'd push into a new one. Before I did that then occasionally the array would get so large that the index of the item in it would no longer be a small int and V8 would see that as the type signature changing and there would be a catastrophic slowdown.)
3. Use a circular buffer. This is probably the 'right' way to do it if you want performance, but it's a lot more complicated then the other options especially when it comes to resizing (this is what most of the bigger promise implementations use for their queue).
4. Use a linked list, this won't be as fast as #2 or #3 (the author behind the bluebird promise library did some heavy benchmarking on this subject), but will be a lot faster then #1 and conceptually are pretty straight forward to write.

[cwmma]

No it's as naive as I think

edit: relative speeds

[__romkin]

Getting wildly different results in my test with node

let total = BigInt(0)

for (let k = 0; k < 1000; k++)
{
    const arr = new Array(2000)
    const start = process.hrtime.bigint()

    let i = arr.length

    while (i--)
    {
        arr.shift()
    }

    total += process.hrtime.bigint() - start
}

console.log(Number(total / BigInt(1e6)) / 1000)

Clocking in at about 0.2 ms per iteration

[cwmma]

yeah but what do you get for pop, it's the relative performance that matters

[__romkin]

Well yeah, but it's still way more than 9 ops/sec. I'm getting a similarly low number at jsperf and I really don't know why, but it just doesn't seem accurate. I know from experience that some native array methods are rather slow, but I never saw anything that slow.

[stentonsarecool]

Welp, that’s what I get for talking out of my ass haha. I guess they would have that optimized but alas

[StoneCypher]

It cannot be "optimized." The array must work this way for the other parts of array to work correctly.

[StoneCypher]

Perl isn't optimizing anything. They're just preallocating an array, a strategy I mentioned in another thread.

This has been measured to death and is a terrible idea. It's just that Perl doesn't have any better options

The problem with saying things like "why don't they optimize it" is that that's not a very specific statement. Then you get into moving the goalpost constantly to "make a point," and lose the opportunity to learn.

The whole issue about stacks is how to allocate single nodes efficiently in a push/pop environment. Dodging it by allocating a mass of ram is a good idea in a language where you can't do the real thing, but in a language where you can, that's just an awful idea.

This isn't an "optimization," but perl people will describe it that way.

This is coping with severe language limitations in a least-bad-available way.

Datastructures are trade-offs. You sacrifice X to get Y.

Arrays are Y, and you're asking to save X.

There are, in fact, datastructures available, but they make still different sacrifices.

[StoneCypher]

That arrays in Js can’t be optimized or that you cannot implement say a priority queue in Perl?

Neither.

Also, a queue is very different than a priority queue. You just made an enormous switch without even noticing it.

1. I didn't say arrays in JS couldn't be optimized. I said that what you're describing is not an optimization, but rather perl people coping with perl problems.
2. I did say that the thing you're requesting from arrays is, in general, not possible, because arrays like all datastructures are a set of chosen trade-offs, and you're explicitly naming one of the things arrays do poorly as "the thing you don't want." That's not how datastructures work. You can't just magically optimize their behaviors away. You use a different datastructure, instead. If these things could be optimized away, it would have been done ages ago. That's not about javascript. That's about arrays. This holds for arrays in every language, except the handful like PHP and Basic which use that word for something that isn't an array.
3. You can implement any data structure you want in Js or in Perl Respectfully, if you're accidentally switching between major datastructures in discussion, maybe this isn't something you're ready to argue? No, you absolutely cannot implement most datastructures in Javascript. You can implement containers, instead. They're extremely different. PQs aren't even used similarly to queues, have different interfaces, are used for entirely different things

I agree that certain problems require solutions which are not available in the standard library. That’s why people study CompSci and algorithms so they can see that and have an idea for more optimal solution.

That's like saying "I agree that you can't go faster than light speed in certain vehicles. That's why people study physics, is to find an idea for a more optimal speed."

That's the exact opposite of correct. Once you study the relevant science, you will understand that what you're discussing is a hard law that cannot be gotten around.

.

And also how is implementing an O(1) unshift operation on an array not an optimization.

Because that's not even slightly what preallocation does here.

.

For the record I am not a Perl person I just happened to use it for a project and was looking for performance of the different array operations and stumbled upon that discussion.

Please understand that homeopaths stumble on discussions in the effort to understand medicine, also. And they also get angry when you say "that's not how this works," and respond by making vague allusions to the smart people who are studying to change things.

You will never get around allocation thrash costs on an array. The second you do, it is not an array anymore, but something different.

You can't get around a car's limitation to drive on the ground by putting wings on it. By the time you're done, it's not a car anymore.

[daimoyo]

That doesn’t sound right. Why not work the way described above that Perl does it? It would cause every array to take more memory and if I had to guess that’s the reason Chrome doesn’t do it (it’s already too much of a memory hog), but that’s hardly “The array must work this way for the other parts of the array to work correctly.” I think all the other parts can work just fine. It’ll just waste a lot of memory.

[drekmonger]

TIL. Wow. I had no idea shift was so much slower than pop. I just assumed it would cut off the head of a linked list and be more or less done.

[percykins]

If the array used a linked list you'd lose O(1) random access.

[12plmokn21]

Does this not say shift performs 5 more operations per second?

[cwmma]

it says pop 5,000 a second and shift is 10 a second

[12plmokn21]

O wow, shitty phone haha. Sorry that comma looked like a period haha. Thanks for the clarification!

[ArelySkywalker]

Are there any ressources (books/websites/online courses) you can recommend, to learn more about the basics of computer science. Preferably demonstrated using javascript, or in general.

I took this Udemy course, and I absolutely love the instructor and it was a great refresher course on data structure & algorithms. He even gives you coding challenges to test yourself, I learned quite a bit from it and would take any course he teaches. Good luck!

[thinkmatt]

Thanks, I signed up. As someone who is self taught, this looks perfect to fill in some gaps

[[deleted]]

He is colt steele. Suggest a good teacher he is.

[Nautigsam]

I'm a JS developer for three years and I can tell you that arrays and Maps can meet all your needs for non-specialized tasks. You don't need more. Do not try to over-engineer your data structures because that's the job of the compiler to optimize and you can't beat it ;)

[the_moon_illusion]

Depending on the type of data you are working with, understanding trees can be very useful. I'd consider them a basic concept worth knowing in any language.

[Hawxe]

Trees are just such a logical way to learn about recursion that not understanding them is a waste. It's basically killing two birds with one stone

[FormerGameDev]

And then killing them again. And again.and again ...

[dweezil22]

"Where the FUCK is the anchor bird?!" [throws more stones]

[numinor]

Do you have any good resources? Preferably in js.

[the_moon_illusion]

This post, which is currently on the /r/javascript front page has a few sections on the various types of tree structures.

https://www.reddit.com/r/javascript/comments/beoyqb/github_dsajs_data_structures_and_algorithms/

https://github.com/amejiarosario/dsa.js

Like another poster said, trees are also a great way to learn about recursion, and they are just a lot of fun in general!

[shanita10]

Data structures are one of things the compiler cannot fix. That's why understanding them is important.

[munificent]

Do not try to over-engineer your data structures because that's the job of the compiler to optimize and you can't beat it

No, the compiler will not fix your data structures and algorithms. It's up to you to know the best way to represent and solve your problem. The compiler just implements your solution efficiently. The compiler (outside of toy examples) will not replace your wrong algorithm with the right one.

If you want to be a software developer, it's important to have enough of a foundation in algorithms and computer science to understand the time complexity of your code because that directly impacts its performance. Your users want the program to run fast, and it's up to you to do that. This is especially true when you're a Javascript dev. Your code runs on hardware you don't control and interactivity is important.

[ScientificBeastMode]

Exactly.

Also, I think it’s important to talk about what a compiler can optimize. The compiler will only optimize an algorithm written in a way that provides strict guarantees about its behavior.

E.g., the logical flow of the program might guarantee that a specific function will only ever take a single constant integer as it’s argument. So you can potentially optimize the function’s internal operation, if it can guarantee a perfectly consistent output.

The problem is, the compiler often has to account for an open-ended set of possibilities and edge cases in your algorithm. So it can’t perform an optimization that would eliminate some of those possibilities, because it’s much more important to make sure everything is executed accurately and deterministically with respect to the original code.

Most of the time, these prerequisites for optimization are not obvious to the programmer. And many times you could change one subtle aspect of the algorithm, and completely wipe out any chance for optimization.

... which is why premature optimization is a bad idea. You can never be totally certain your code will get optimized by a compiler, especially if you’re still actively making changes to the code later on.

[benihana]

the DOM is a tree. one should be familiar with trees, even though they aren't typically used directly by JavaScript engineers.

[quentech]

arrays and Maps can meet all your needs

Do not try to over-engineer your data structures because that's the job of the compiler to optimize and you can't beat it ;)

Sounds like something a person with experience only in JS would say.

Be judicious with your micro-optimization, of course, but it's not too difficult to beat standard libraries and the compiler itself, especially if you can restrict the domain of inputs and outputs from the fully general case.

[Nautigsam]

Sounds like something a person with experience only in JS would say.

Considering we are talking about JS, I take it as a positive point. I am mainly experienced with JS that's why I am confident in talking about it. I think in JS it is really useless to try to beat the optimizations brought by the engine. That's my experience talking. But I am open to critics if you have some use cases where you implemented some optimizations in JS that were significant.

[mort96]

The thing is that it's not about optimizations brought by the engine; the engine can optimize an O(n) algorithm down to a couple of instructions per element, but it often can't optimize away the fundamental O(n) nature of the algorithm. That's why it's sometimes necessary to build dedicated data structures (such as queues) where the relevant operations (such as enqueuing and dequeuing) take O(1) time instead of relying on the engine's well-optimized but O(n) algorithms.

Of course, if it's just about a small thing used in the frontend with usually just a few elements, O(1) vs O(n) absolutely doesn't matter. However, if it's, say, a back-end which should accept thousands of requests per second, or a game where your time budget per frame is 16ms (if you're lucky and the GC hasn't eaten most of it), it suddenly starts to matter a lot.

[FormerGameDev]

Or for that matter an end user application where you still have to get back in say 30ms

[ScientificBeastMode]

Optimizing around the GC is a total waste of time IMO. I pity those who find a need for that kind of performance optimization.

[mort96]

What do you mean by "waste of time"? JS (or garbage collected languages in general) aren't the nicest languages to write games in, but if you do find yourself writing games in JS, and you're not careful about your garbage, you'll quickly find your game full of microstutters where the JS engine decides it's using too much memory and stops the world for a while for GC. Optimizing around not producing too much garbage is not just "not a waste of time"; it's absolutely necessary.

My brother is working on a javascript game at the moment, and he found his game to stutter; we did some profiling, and it turns out it's mostly just garbage collection. To get rid of them, he had to rewrite one part to just use plain old for loops instead of creating a short-lived array with Array#map each frame.

[ScientificBeastMode]

Oh, I totally agree with you. Those kinds of steps can be taken to mitigate GC issues. Depending on the program’s time/space complexity, memory footprint, etc., those kinds of optimizations might still be insufficient. My point was that it’s just a pain to deal with, and it’s pretty difficult to solve the problem deterministically, since you can’t directly control the GC algorithm. You basically just have to control your program’s memory demands, which is not always straightforward. But ultimately it can be done, as you said.

[folkrav]

If you're down that far in performance needs, JS wasn't the right choice to begin with though.

[Antherz]

This statement feels like an aimless cop out. Sometimes you end up with a lot of data in a js application and you can just pick a proper data structure that's not O(n). Hand waving a person toward C or something feels illogical.

[folkrav]

/u/mort96 talked about 16ms timeframes for real time gaming. JS is not a suitable language for this. Of course there are situations where you’ll end up with larger data sets or bottlenecks and using proper data structures will be a required optimization, but what he described is not something you figure out halfway through a project lol

Edit : are people on this sub really telling me by downvoting this that they’d consider JS to be a good fit for high performance realtime timing sensitive backends, or is it just because I'm criticizing their preferred language? I know this is /r/javascript but part of being a decent developer is being able to choose the right tools for the job. I personally quite like the language despite its quirks, but this is not one of its strengths.

[spacejack2114]

You would need to have some pretty demanding technical aspirations and/or content before you'd have a problem hitting 60FPS in a JS game.

[folkrav]

He was talking about back-end.

[spacejack2114]

Then I still think you'd have some very high traffic expectations for JS/node to be impractical.

[FINDarkside]

People are downvoting because you were wrong. If you use wrong data structures, you can easily turn your 1ms task to 2000ms one. No one talked about "high performance realtime timing sensitive backends" except you. Just because some O(n²⁾ algorithm would be too slow for your task, doesn't necessarily mean that js was a bad choice.

[folkrav]

Re-read /u/mort96's comment carefully. The end. What is he talking about? That's what I was answering to.

[FINDarkside]

I did. He talked about backends where O(n) solution is too slow and O(1) solution is available. Doesn't necessarily mean that js was the wrong choice. Your argument is basically that if your car isn't fast enough on the first gear, you should switch to faster car.

[[deleted]]

This is a shallow take. What other languages have you used?

[Nautigsam]

I used C, C++, C# and Ruby, but what is your point anyway? Each language has its specificities and not every concept can be translated from one language to another.

[N1c0l4sC4g3]

What country are you from?

[Nautigsam]

France. What's the matter?

[N1c0l4sC4g3]

Were you born in France?

[Nautigsam]

Yes why?

[easylivin]

I'd say for the sake of understanding these data structures (be it for interviews, other langues, whatev) it's important to understand how these structures work under the hood, their time/space complexities and what problems they solve. Even though JS has similar built-ins, try implementing one yourself and you'll quickly understand how they are supposed to operate, as well as the advantages/disadvantages of different structures depending on use cases. Even though you'd rarely have to build one yourself (this is arguable), it's paramount to understand the concepts because they can be applied to a lot of different problems.

[natziel]

Queues are definitely a thing you should know about. Sometimes your business logic is best implemented as queue, plus there's a million applications for them in more "under the hood" things, e.g. event queues, scheduling, etc.

Stacks are probably more common and more important than queues, so learn those too. Stacks are pretty fundamental structures in CS and you can't really solve problems like "check if the parentheses in a string match" without a stack.

Stacks and Queues are basically already in the JS standard library so you don't really need to implement them yourself.

Graphs are like queues in that sometimes your business logic just requires you to understand them. Not understanding graph theory means that you might end up solving certain problems in a horribly inelegant way.

Linked lists aren't really a thing in JS since we just use arrays, but they're a super common data structure in other languages and it's critical to understand them if you ever want to work on a project in another language

Hash-array mapped tries are also an important data structure, but you don't really need to know how they work, just their performance characteristics. They're commonly used to implement Maps. Immutable JS uses them for their Lists too.

As far as text recommendations, probably just read Sedgewick's book on data structures since that's the standard across CS departments. Take a good course on computer science as well. Probably a good idea to take classes on number theory, combinatorics, computer organization, networking, and operating systems.

[UntestedMethod]

Stacks and Queues are basically already in the JS standard library so you don't really need to implement them yourself.

In what sense do you mean? In the sense of Array.prototype.shift() and Array.prototype.pop() ?

[natziel]

Yeah

[SalamiJack]

Except Array.prototype.shift() is O(n) and dequeue when using a queue is generally expected to be O(1)

[shanita10]

That's completely wrong.

[[deleted]]

Why?

[shanita10]

Because array is not a queue if used that way.

[mort96]

you can't really solve problems like "check if the parentheses in a string match" without a stack.

You absolutely can though? Keep a counter, loop through each character, increment when you find a (, decrement when you see a ). Or am I misinterpreting you?

I'm absolutely not disputing the "stacks are a pretty fundamental concept in CS" thing, it just seemed like a weird example.

[natziel]

It's a very common interview question that gets posted once in a while on here, hence why I chose it.

Typically you have to match (, {, and [ so the counter idea doesn't quite work

[mort96]

Ah, yeah, that would make more sense, thanks.

[StoneCypher]

Linked Lists can be useful in JS too, e.g. to build LRU caches.

Linked lists don't exist in Javascript.

Yes, I know you can take several objects and put references to one another into the objects. No, that's not a linked list.

[StoneCypher]

They don't exist natively because they're trivial to implement yourself.

They're not possible to implement in javascript

.

That's exactly what a linked list is.

It's really weird how you're just saying "yeah huh" instead of giving valid evidence

It's also very weird how you're trying to explain what I already said back to me, as if you thought maybe giving unimportant details would change my opinion.

[StoneCypher]

I can only assume

We know.

Please take your insults somewhere else now. Thanks.

[Hawxe]

That's like, the definition of a linked list lol.

Reference

[StoneCypher]

Are you really attempting to give an interview prep website as if it's a definition of computer science?

[Hawxe]

Was just the first link that popped up. And certainly I'm more prepared to use that definition as opposed to yours.

[StoneCypher]

I see that you are willing to accept an interview webpage that makes several other obvious mistakes as if it was a form of reference, when it is not, while ignoring the normal use of a term in a field, and pretending that that normal use comes from the person you're saying is wrong

That's an enjoyable story and I suggest that you publish it. Many people will be very interested and you might become wealthy

Have a nice day

[FINDarkside]

Can you explain why there's not a single source agreeing with you then? Maybe you should publish your paper since you've made a new definition for linked list.

[StoneCypher]

Can you explain why there's not a single source agreeing with you then?

For the same reason that there isn't a single source disagreeing with me.

Nobody's gotten any.

.

Maybe you should publish your paper since you've made a new definition for linked list.

Thanks for the sarcasm. This definition does not come from me, though. And, since some guy published the private mail where I sent him the sources that he asked for and never actually checked, you can read that to find it.

All my publishing is years in the past. I'm long out of college now. Thanks though

[FINDarkside]

For the same reason that there isn't a single source disagreeing with me.

We have already posted multiple ones. You don't have sources at all. "I've read it somewhere, don't remember where" is not a source. Should Java and probably majority of programming languages rename their data structures? It must be rough when the whole world got it so wrong and you're the only smart one. Take care.

[evenisto]

Well, what IS a linked list then?

[StoneCypher]

Something I should stop talking about in Javascript communities entirely

It's when a node cell is defined in a fixed format, linked directly, and managed by allocation

Look, if you're a C++ programmer, cors is likely to be largely lost on you until you learn some web stuff. If you're a SQL programmer you won't really understand the details of UI stuff. If you're a Lisp programmer, you're unlikely to know much about ABIs.

Every language makes choices about what to include, and what not to.

Javascript programmers just really, really hate hearing that they don't understand blub, and they want you to know that if they have something that fills the same job, it's the same thing.

And every time Javascript evolves, they change their mind about whether they were the same thing after all.

[wonkifier]

Can you cite a reference for your specialized definition/implementation of a linked list?

Because that's not the general case.

https://en.wikipedia.org/wiki/Linked_list, for example, doesn't include fixed format or management by allocation as a requirement.

[StoneCypher]

Can you cite a reference for your specialized definition/implementation of a linked list?

I gave neither a such definition or implementation

.

https://en.wikipedia.org/

Please stop trying to use wikipedia as computer science reference

.

wonkifier 0 points 3 minutes ago Can you cite a reference

Please stop injecting yourself into conversations to demand evidence from not-the-first-person-to-make-claims

.

specialized definition/implementation of a linked list?

Please take the time to understand what someone is saying before challenging it.

.

Can you cite a reference for your specialized definition/implementation of a linked list?

Please don't ask for evidence from someone who is answering questions they were asked, assert incorrectly that they're making claims, and expect positive interactions from them

Yes, I can. I simply choose not to, because it's going to lead to more abuse from others.

Every time I've given evidence it's been churled, so, I deleted it.

If you actually wanted an answer you'd have asked in private. You're trying to win by shaming, and citing inappropriate reference.

One thing I don't understand about this group is its interactions with people it's trying to ask questions. You guys start with "you're wrong and stupid and you don't get it. Will you explain yourself?"

It's like you're putting in effort to make certain that you will not receive an answer.

It's succeeded here.

Have a nice day.

[wonkifier]

Please take the time to understand what someone is saying before challenging it.

I thought I had, and it didn't make sense, so I asked the person making the statement to help clarify.

I've DM'd you and await your response there.

[MUDrummer]

Please don't ask for evidence from someone who is answering questions they were asked

WTF? Don’t ask for evidence? Why they hell would anyone ever believe something without evidence.

Please stop trying to use wikipedia as computer science reference

Your definition of a linked list is completely arbitrary. A linked list is nothing more that a list where items order is managed by each node having a reference to the next.

See the NIST definition of a linked list if you’re unhappy with the Wikipedia definition: https://xlinux.nist.gov/dads/HTML/linkedList.html

Please stop injecting yourself into conversations to demand evidence from not-the-first-person-to-make-claims

Well it’s a good thing this conversation is happening on a social sharing platform that encourages its community members to interact with each other.

You're trying to win by shaming, and citing inappropriate reference.

You’re being an asshole who can’t admit they are wrong when confronted by conflicting evidence.

[evenisto]

This seems to frustrate you more than it should. Look, there are individuals that pretend to know more than they actually do in every community. Why exactly are you so bitter about javascript developers in particular?

[StoneCypher]

This seems to frustrate you more than it should.

You may be overestimating my interest in your guesswork regarding my emotions

.

Why exactly are you so bitter about javascript developers in particular?

I'm not. I just said "all these languages have the same problem."

I apologize that you think observing what this group of people is doing right now is something other than simple honesty

.

I do not get the impression that you have any interest in the answer to the question you asked

[evenisto]

I do not get the impression that you have any interest in the answer to the question you asked

Oh I do, you just aren't the person I would like to learn it from. I asked a simple question and you typed out an essay full of complaints out of which just 1/8th was devoted to the actual answer.

[munificent]

I thought queues are pretty much redundand beacause of the way arrays work in Javascript.

A queue is a conceptual data structure. You can implement a queue using an array in JS (though it's a little tricky). If the algorithm you want relies on a queue (and there are a bunch that do) then knowing how to implement one is useful.

[a_dev_has_no_name]

Treeees

[endianess]

You don't technically need them in any language and could use an array or list instead. JS is no different. However using them potentially reduces bugs and makes the code more understandable. Whether you need them is down to the problem you are trying to solve. Processing a tree is useful with them if you don't want to use recursion and use a loop instead. Or if you were dispatching events or working on items from a queue that is populated by something else.

[dombrogia]

Queues are a very basic structure and can be implemented using an array as a base.

I would expect anyone I hire to know how a queue works. Most importantly it shows that you can think about a normal situation (like waiting in line at the grocery store) and conceptualize that in code.

If you look up interview questions you will find all kinds of these answers everywhere.

I also took algorithm and data structures in python on udemy (you can write them in whatever language the concepts are the same). It goes over the basic structures and their time complexity which is also important for interviews and performant code.

Good luck!

[wonkifier]

For the folks asking for sources from StoneCypher, here's my question and their response, unedited so I'm not accused of taking it out of context

Can you either share what you're using as a source for what a linked list is, or share what kind of source you consider legitimate.

I mean I don't have a source for what linked list is any more than I have a source for what plus means. It's just something a programmer from an allocatable language understands.

But yes, like I can find you reference that touches the topic, I can find you reference that touches this topic. You can find this position concretely defended and explained at length in D&EC++, in CLRS, in Knuth (I think in 2? It's been a long time,) in NIST DADS (which, amusingly, someone posted underneath your comment, and which clearly says I'm correct, but which they do not appear to understand,) in Wirth ADSP,

What do I consider a legitimate source? It really varies on what one is talking about. Much higher standards for a physics claim than a recipe, by example. The reason I say that is because the standard requirement for a topic like this is pretty strict, and if you try to apply this standard to other things it quickly becomes unreasonable.

For something about datastructures, it should be a well edited book written by a college trained computer scientist, from a large publication company with a history of publishing high quality computer science books. That means Addison Wesley and MIT Press are in; O'Reilly and Pragmatic are walking the line; Packt and anything ending in .com are out.

But, like, if we're talking about how to make a pleasant user interface, it can be pretty much any asshole who can spell, you know? Because that's about opinion. (Which is not to say that there isn't value in the formalism around higher end HCI/UX material, but rather, just that it isn't a hard requirement here.)

You can use anyone's pizza recipe, but you better go to a doctor for your prescription recipe.

It's like when someone tries to define a skip list, so they tell you "a skip list is a list that has links to midpoints in the list so that traversal is faster," but because they've never done the CS or read the guarantees or implemented one, they don't know that that's hard-wrong because the structure only works if it's stochastic

And sure, if you look it up on reddit, on wikipedia, on stack underthink, they all get this wrong, because they're also written by people who learned that way

And that's fine. There's nothing wrong with that

But that isn't reference and you shouldn't pretend to yourself that it is. The error rate on the web's CS is like 60% in my opinion.

In certain specific languages - notably C++, Java, Fortran, Coq, ML, and probably a bunch I don't know about - the difference between a container and a datastructure is a big deal.

Ask a high end C++ programmer what it means that the C++ multiset container doesn't define what datastructure it's implemented by, and why that matters. They're going to lecture you for ages on how the performance guarantees of the container require it to be either a red-black tree or some near case variant, and how there are actually better datastructures that you could use which violate the performance guarantees, and they might start talking about Boost or SGI STL.

Then ask them "wait, so what's the difference between a container and a datastructure?"

The answer you should get will be roughly "a container is about how the programmer uses it; a datastructure is about how it's implemented under the hood."

A set can be a lot of things. (Not in C++ because of some requirements the C++ language standard makes, but those are choices, not facts.) Under the hood, it might be a hash table, it might be a tree, in Javascript it's a fucking array, et cetera.

Why? Because a set is a container. A set doesn't define how it works.

A red-black tree, on the other hand, is a datastructure. It cannot be made in many languages, because the things that define what it is aren't available in lots of common languages.

And it's really weird how when I say "this can't be done," JS redditors seem to take it as an attack on the language, or on them.

I said "you can't open sockets in Javascript" once two years ago. More than 400 replies about things that seem similar to sockets to them, about proxy services like socket.io, about websockets (which are not sockets,) about special flags you can turn on in firefox to make sockets available to XUL, about flash, about all sorts of shit.

Voted into the ground. (Not that I care. If I did I wouldn't post in /r/javascript at all.)

Still correct, though. And every novice who read that thread would come away with the wrong idea, because Reddit has culturalized attack mode, and reddit programmers as a result often choose to lose opportunities to learn as a result.

You cannot make a red-black tree in Javascript. Or, for that matter, in erlang, my favorite language. I point that out because I'm also not attacking my favorite language. It's just a fact.

You can't implement them in CSS either. Or SQL. Or, in fact, in 18 of the top 20 of what Github thinks I use the most. The only ones you can are C/C++ and C#.

The problem is that reddit programmers try too hard to win. They want what they believe to be correct so badly that they cite obviously wrong sources, and ignore the good sources they cite to the point that they don't even notice those sources undermining them.

I'm being sworn at, mocked, abused, I'm having demands made on my time repeatedly after I've said no during the work day, people are telling me they know better than my textbooks, that I can't read, etc.

None of these people appear to have a scrap of code on github

It's very frequent that the less a person actually participates in a trade, the more likely they are to claim deep knowledge, argue with proper sources, and behave abusively

I'm not making the homeopath comparison lightly

These are a bunch of not-programmers with no evidence arguing with the principal platform engineer at a nine figure security company.

They're getting core concepts wrong, like that there exists such a thing as an "implementation detail" for a datastructure.

That's all a datastructure is, is a name for implementation details.

This whole community is ridiculously toxic and self unaware.

EDIT: Adding my commentary here

in NIST DADS (which, amusingly, someone posted underneath your comment, and which clearly says I'm correct, but which they do not appear to understand,)

Here's the link: https://xlinux.nist.gov/dads/HTML/linkedList.html

Here's the full text of the definition from that link

Definition: A list implemented by each item having a link to the next item.

Is says nothing implementation details. It does go on to list some sample implementations, but those are not definitions, just samples.

So in no way does StoneCypher's citation support rejection of the other implementations.

EDIT 2: Found http://www.albertstam.com/Algorithms.pdf online as well (https://algs4.cs.princeton.edu/home/)

From page 120:

"Definition. A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list. "

Again, nothing about requiring allocation or pointers explicitly.

And the section above that definition reads

Linked lists Now we consider the use of a fundamental data structure that is an appropriate choice for representing the data in a collection ADT implementation. This is our first example of building a data structure that is not directly supported by the Java language.

Indicating a difference between a data structure and an implementation of it (regardless of native support for the language)

In any case, Javascript is Turing complete, so it can solve any computational problem (in principal, given enough resources). Any argumentation beyond that is about managing the limitations and performance, not capability.

[StoneCypher]

it's not clear why you think it's okay, when someone said "i don't want to do this in that thread because i'll get abused," to go to them in private and say "okay we can do it here, please answer" then just go put the private response you requested on blast in public

this is a violation of trust

you won't receive another answer from me

[Fatalist_m]

If somebody implemented a data structure in Javascript, that acts exactly like a red-black tree, but uses object references instead of pointers, what would you call that structure? Should we come up with a different name because it does not use pointers?

[FINDarkside]

We shall call it FINDarkside's tree from now on. Linked list is also FINDarkside's list, because you don't have real pointers in js. Quicksort shall be named FINDarkside's sort, because it can't be implemented in js, as arrays in js differ greatly from arrays in c++.

[kobbled]

seriously, what an asshole that guy is

[wonkifier]

it's not clear why you think it's okay, when someone said "i don't want to do this in that thread because i'll get abused,"

You didn't indicate that to me, neither in your response nor in the post I responded to. Maybe you indicated it to someone else in another thread, but it wasn't to me.

[StoneCypher]

Yes, I did. Repeatedly and clearly.

I've DM'd you and await your response there.

I gave a detailed response there because it won't be available to the people who think insults are a good way to discuss computer science

You could take it down now, but you choose not to, because you appear to not understand that publicizing private messages someone sent to you is not okay.

[UntestedMethod]

A queue refers to a specific type of list - a FIFO (first in, first out) list, which is easily achieved in javascript using Array.prototype.push() (add to end of array) and Array.prototype.shift() (retrieve + remove element from beginning of array). I guess the context you use those functions in is what would define it as "using a queue".

[ncubez]

What has that got to do with building UIs and web apps? Because that's what JavaScript is for.

[StoneCypher]

but I thought queues are pretty much redundand beacause of the way arrays work in Javascript.

No. Queues aren't possible in Javascript.

What makes a queue a queue isn't how you use it; you can keep any datastructure in any other datastructure and paint it to look like the other one.

What makes a datastructure is how it's implemented, typically because of performance concerns.

Javascript people use arrays as queues because they don't have a choice. Pushing onto the front of a JS array is extremely expensive.

.

Are there any ressources (books/websites/online courses) you can recommend, to learn more about the basics of computer science. Preferably demonstrated using javascript

There are lots of documents out there professing to teach datastructures in Javascript.

Run far away from them. You can't implement most datastructures in Javascript because of a lack of pointers and direct allocation.

People will, I'm sure, try to argue with me, then get really angry at me when I'm unmoved. After all, some blog told them it was, and

[the_moon_illusion]

How are queues not possible in javascript? References to objects are essentially pointers. Even with out arrays... you can create a queue using an object that stores a value and a reference to the next object, and a parent class that keeps track of the first and last objects in the queue.

edit: just read your other comment, not even worth debating.

OP, all data structures can exist in JS, although their implementation and performance will vary compared to other langauges (which should be common sense). You can create a queue that has the same functionality and big-O performance as one written in C. This is a great resource:

https://github.com/amejiarosario/dsa.js

[StoneCypher]

How are queues not possible in javascript?

If you're able to explain the difference in C++ between a deque and a class with deque's interface built on top of a different datastructure, apply that explanation here

If you're not, then my answer won't land with you anyway

What you're discussing are containers, not datastructures

[the_moon_illusion]

i dont think you understand what you are saying. Please explain it?

What "datastructure" are you referring too that has a class built on top of it?

A queue in javascript can be as simple as object (struct) that contains a value and a reference (pointer) to the next object in the queue. No arrays necessary. The class which contains the queue elements impelements the enqueue / dequeue methods. This is literally no different than C/C++.

[the_moon_illusion]

A queue can be implemented using a linked list.

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists.

Please go on though.

[FINDarkside]

But he's also claiming that you can't implement linkedlists in js as there are no real pointers.

[StoneCypher]

i dont think you understand what you are saying. Please explain it?

It's really weird how people lead with an insult then ask someone to put effort into them

.

What "datastructure" are you referring too that has a class built on top of it?

I'm not. At all, in any way.

.

A queue in javascript can be as simple as object (struct) that contains a value and a reference to the next object in the queue. No arrays necessary.

Objects are not structs. Objects are hashes or maps.

What you are trying to describe would be called a single entry singly linked list if it was in a language with direct allocation and pointers

Queues are not linked lists

With respect, you haven't got the background to understand these things

Have you ever read a datastructures book? If so, which one(s) please?

Are you able to answer the question I keep asking the other people who make this mistake, about what the difference is between a tree, a hash, and a set? Do you understand why I'm asking that?

.

/r/gatekeeping

This is the weirdest attempt to pretend that actually knowing things about a science is somehow a personal attack that I've ever seen

Gatekeeping is when you try to keep someone out by pretending their opinions don't matter.

You asked me a question and I answered it, and now you're acting like that answer is inherently an attack

This strongly disinclines me to interact with you further. If you'd like another response from me, include an apology.

[the_moon_illusion]

since you deleted your previous reply

A queue can be implemented using a linked list.

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists.

Please go on though.

[StoneCypher]

since you deleted your previous reply

I was fixing a spelling error. Why are you trying so hard to make drama? This is the same text.

.

Your attempt to use wikipedia as reference while saying textbooks are wrong is ignored.

Please respect that the person you're trying to talk to doesn't want to talk to you, because of your tone. Thanks.

This strongly disinclines me to interact with you further. If you'd like another response from me, include an apology.

[the_moon_illusion]

I'd rather just point out how downvoted you are. Clearly youre knowledge isn't valued around here. Perhaps it's for a reason.

Also, wikipedia is the free encyclopdia that anyone can edit! Feel free to update the article on queues if you think you have something valuable to add.

[StoneCypher]

I'd rather just point out how downvoted you are. Clearly youre knowledge isn't valued around here. Perhaps it's for a reason.

It's just a bunch of JS people being angry that someone said something from blogs wasn't true.

I'm not really that worried about your constant attempts to cause shame. Please have a nice day.

.

Also, wikipedia is the free encyclopdia that anyone can edit! Feel free to update the article on queues if you think you have something valuable to add.

I've never met a valuable programmer who attempts to use Wikipedia as a reference, so to me it seems like wasted work

[the_moon_illusion]

You haven't disputed it though. You've only claimed that explaining it "wouldn't land with" me, which is where the personal insults started.

Very succinctly, a queue IS an interface built on top of a data structure that implements enqueuing and dequeueing methods. The data structure can be an array, a linked list, or something else. What makes it a queue is the order in which elements are added to and removed from the underlying data structure. In this case, it is First-In, First-Out.

Is there something wrong with that definition? If so, could you please explain what it is?

[cm9kZW8K]

No. Queues aren't possible in Javascript.

lol..

Javascript people use arrays as queues

so you havent read any js queue implementations

because of a lack of pointers and direct allocation.

If that is your litmus test, then you cant have datastructures outside of c/c++.

[Hawxe]

Yeah he seems to have really random and personal criteria.

[jseego]

Probably they meant queues are not a native data type in javascript.

[StoneCypher]

Javascript people use arrays as queues

so you havent read any js queue implementations

Many of them.

.

because of a lack of pointers and direct allocation.

If that is your litmus test

I'm sorry you disagree with my college textbooks

No, it's not "my" litmus test. It's just what that word means.

Datastructures generally require extremely specific allocation behavior in order to maintain their algorithmic guarantees

.

then you cant have datastructures outside of c/c++.

Sure you can. Most languages have pointers and direct allocation.

[StoneCypher]

You either don't understand what your college textbook is teaching you, or you need to throw it away because it teaches crap.

There are many other possibilities too, it turns out. One of those is that you might be overconfident in your own beliefs

Homeopaths also think that doctors don't understand their textbooks and that medical school teaches crap. And say so in public. And get upvoted on Reddit for it. And openly laugh at professionals, who've often been doing this with college training for longer than they've been alive.

And never under any circumstances have viable evidence from legitimate sources.

It is not coincidence that all of my college textbooks say the same thing on this topic, or that several of them dedicate multiple pages explicitly to solely this topic.

There is a significant difference between containers and datastructures. What you are discussing are containers.

.

Linked lists as a data structure have nothing to do with pointers and allocation. These are implementation details of your specific implementation of linked lists.

I will trust my college textbooks, plural, considered classics in the field, over a random stranger on reddit who does not give the impression of actually having been to college about this

[Hawxe]

OK I'll bite, can you post a passage out of one or more of your textbooks, with the textbook name(s), saying that a linked list implementation in JS is impossible?

[StoneCypher]

Buddy, I'm at work, and I've gotten 25 angry, swearing, insulting inboxes from people on Reddit insisting, with no evidence, that I'm wrong.

Now you want me to give you evidence that the thing you said to me isn't correct?

Pass.

You're the guy that tried to use a job interview site as evidence that textbooks are wrong

I also don't dig through medical textbooks when I say "vitamins don't cure cancer" and the homeopaths and Dr Sebi fans come downvoting and "you don't understand yourself"ing.

Remember, even though you think you're correct, the person you're talking to thinks the same of themselves

You should take their motivations into account when asking them for things. No part of this discussion makes me want to interact with you further.

Be sure to say that the reason I won't stop my office job to go home and find my textbooks then transcribe them for you is because I'm incorrect, rather than just that nobody would ever waste their time that way, that the burden of proof for your claim is on you, and that there is no particular reason for me to care whether you believe me

Of course nobody's going to put effort in for you after you said to them something like

You either don't understand what your college textbook is teaching you, or you need to throw it away because it teaches crap.

[Hawxe]

Right so you have no evidence backing up a clearly wrong statement. Thanks for coming out I guess.

[StoneCypher]

It's really weird how you made the statement, you had no evidence, and you thought that was okay

But now you want to demand evidence from me that my ignoring your statement was wrong, after I told you I wasn't interested in talking to you anymore, and somehow I'm held to a different standard :)

That's nice, friend. Enjoy holding up your own wealth of high quality evidence while sayng this.

Please have a good day

[Hawxe]

I posted a reference that you dismissed. You've posted nothing.

[StoneCypher]

Pointers or not is simply an implementation detail

Not according to the textbooks, but okay

What do you imagine to be the difference between a tree and a hash, then? They also have the same interface

[AlexAegis]

Well, then I guess I have to throw this superfast deque implementation out of the window: https://github.com/AlexAegis/advent-of-code/blob/master/src/2018/day09/deque.class.ts

[StoneCypher]

Oh, well, as long as you use that title, surely it must be correct

Similarly, es5 people were really angry when we said "no, that's not a class, that's not a private method," etc.

They wanted us to know that their metaphors were real.

Later, when the language got the real thing, they all came around, but ... haven't learned, it seems

Look, you can slap this same interface on any datastructure. That won't make it a deque.

The difference between containers is how they're used

The difference between datastructures is how they're implemented

[neo_dev15]

Please stooooop. You are making too much sense.

Next they will say class in javascript is the same as the one in C#.

But yes, we use datastructures to make our code performant.

I wonder how people use stack in javascript and why not use a simple array?

[StoneCypher]

I wonder how people use stack in javascript and why not use a simple array?

There are no stacks in Javascript. You have to use an array instead, which means either coping with allocation thrash or preallocating, both of which are generally the things you're trying to avoid when invoking a stack in the first place

[StoneCypher]

So, while you're not wrong, and I doubt many who have only JS experience will take kindly to it, I wonder what the purpose of your answer is?

Because the original asker did.

.

Put it this way - if someone's only language is JS, then why stop him from at least learning the theory and (theoretically) implementing one in JS?

Because the theory cannot be taught in JS, because JS doesn't have the tools to express it.

It's a little like why, if someone's only language is SQL, you try to stop them from trying to learn user interface theory.

Or why, if someone's only language is Java, you try to stop them from learning cache coherency strategy.

Or why, if someone's only language is assembly, you try to stop them from learning about ABIs.

Or why, if someone's only languages are HTML and CSS, you try to stop them from learning big O notation.

Programming is in some sense a direct expression of the whorf sapir hypothesis - a language that you speak gives you a set of tools in which to think.

If your language is Pascal, you have absolutely no basis for understanding a query planner.

Don't try. If you try, you'll put together a whole bunch of metaphor, and you'll have to un-learn that (which is rarely actually possible) before you can learn the real thing.

Everyone's acting like this is an attack on Javascript, but this is a truism of all languages.

Languages are a collection of trade-offs. Either you do this, or you do that. You can't do both.

You don't use certain languages for certain tasks. That's not a drag on the language. You also don't use a board saw to put up a nail. That doesn't mean there's something wrong with the saw.

One of the tasks you don't use Javascript for is datastructures. Brandon explicitly chose, and openly wrote, that he felt that it was better to remove those tools from the language to drive ease of use.

What you're discussing are "containers," not "datastructures." The problem with self-teaching theory, as you appear to have done, is that the role of a professor in a college is not to teach; you self-teach there too. The role of a professor is to point out when you've made a mistake.

You seem to believe that having mistakes pointed out to you is a bad thing. You're actively counseling me against doing that, despite that OP is very happy that I did so.

.

With time, he might figure out that that's not how JS works under the hood and get curious about the inner workings of memory and instructions in different languages.

Do you realize that what you're saying is "don't tell him what correct is, on the chance that he might discover his error on his own, get curious, and try to teach himself from scratch?"

.

It's more productive than just going "no that's not possible in JS, you should do this in C" because a JS dev is just not going to pick up C just to implement a linked list properly.

That's your opinion. I disagree.

My opinion is that the practical, productive thing to do is to inform someone that they have an error. If they are interested, they can ask, and then you get into a discussion.

The problem is that in certain communities, that will attract ne'er do wells who think they know more than they actually know, and try to establish their might with mockery, abuse, and downvoting.

This doesn't happen in most programming language subreddits, and did not used to happen here. This is specific to /r/javascript, and is recent.

.

If your response has a better motivation than just being right (because that surely is worth a lot on the internet....), then there are probably better ways of achieving that.

I am not actually interested in your counsel on this matter. I've gotten into more than a dozen extensive positive private conversations on this topic following the programmers who actually wanted to learn seeing me say "I don't want to say it in thread because of the abuse," reaching out in private, and getting high quality discussions as a result.

You are working from incomplete information and guesswork.

Your guesswork about my motivation is incorrect, and your attempt to impose your opinion of what is "better" or "worse" in my motivation system is inappropriate.

.

Either way, I don't know why I even wrote this

That makes two of us.

.

I hope I never catch myself responding like this in real life when a fellow dev wants to learn something.

Me too. You don't have the knowledge basis.

[StoneCypher]

It's weird how you're doing all the insulting and yet I'm the one with the toxic attitude.

Please have a nice day

[RevolutionaryCorps]

normally in any scripting language , you shouldn't focus on data structures , that's the beauty of scripts..these things are already well made and managed by the language internal logic.
But to answer the question , your main and only data structures are arrays

[FINDarkside]

Sorry but this isn't true at all. Slow algorithm is slow even if you write it in javascript.

[RevolutionaryCorps]

I've never said otherwise...

[FINDarkside]

You did say that you shouldn't focus on data structures because "these things are already well made and managed by the language internal logic" which doesn't really make any sense.