JavaScript Algorithms and Data Structures (2018)

2021-10-2017:4711530github.com

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings - GitHub - trekhleb/javascript-algorithms: 📝 Algorithms and data structures implemented…

Show article

This repository contains JavaScript based examples of many popular algorithms and data structures.

Each algorithm and data structure has its own separate README with related explanations and links for further reading (including ones to YouTube videos).

Read this in other languages: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana, Bahasa Indonesia, Українська, Arabic, Deutsch

☝ Note that this project is meant to be used for learning and researching purposes only, and it is not meant to be used for production.

Data Structures

A data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

B - Beginner, A - Advanced

Algorithms

An algorithm is an unambiguous specification of how to solve a class of problems. It is a set of rules that precisely define a sequence of operations.

B - Beginner, A - Advanced

Algorithms by Topic

Algorithms by Paradigm

An algorithmic paradigm is a generic method or approach which underlies the design of a class of algorithms. It is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program.

How to use this repository

Install all dependencies

Run ESLint

You may want to run it to check code quality.

Run all tests

Run tests by name

Troubleshooting

In case if linting or testing is failing try to delete the node_modules folder and re-install npm packages:

rm -rf ./node_modules
npm i

Playground

You may play with data-structures and algorithms in ./src/playground/playground.js file and write tests for it in ./src/playground/__test__/playground.test.js.

Then just simply run the following command to test if your playground code works as expected:

Useful Information

References

▶ Data Structures and Algorithms on YouTube

Big O Notation

Big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On the chart below you may find most common orders of growth of algorithms specified in Big O notation.

Source: Big O Cheat Sheet.

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

Big O Notation	Computations for 10 elements	Computations for 100 elements	Computations for 1000 elements
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

Data Structure Operations Complexity

Data Structure	Access	Search	Insertion	Deletion	Comments
Array	1	n	n	n
Stack	n	n	1	1
Queue	n	n	1	1
Linked List	n	n	1	n
Hash Table	-	n	n	n	In case of perfect hash function costs would be O(1)
Binary Search Tree	n	n	n	n	In case of balanced tree costs would be O(log(n))
B-Tree	log(n)	log(n)	log(n)	log(n)
Red-Black Tree	log(n)	log(n)	log(n)	log(n)
AVL Tree	log(n)	log(n)	log(n)	log(n)
Bloom Filter	-	1	1	-	False positives are possible while searching

Array Sorting Algorithms Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Bubble sort	n	n²	n²	1	Yes
Insertion sort	n	n²	n²	1	Yes
Selection sort	n²	n²	n²	1	No
Heap sort	n log(n)	n log(n)	n log(n)	1	No
Merge sort	n log(n)	n log(n)	n log(n)	n	Yes
Quick sort	n log(n)	n log(n)	n²	log(n)	No	Quicksort is usually done in-place with O(log(n)) stack space
Shell sort	n log(n)	depends on gap sequence	n (log(n))²	1	No
Counting sort	n + r	n + r	n + r	n + r	Yes	r - biggest number in array
Radix sort	n * k	n * k	n * k	n + k	Yes	k - length of longest key

Project Backers

You may support this project via ❤️️ GitHub or ❤️️ Patreon.

Folks who are backing this project ∑ = 0

ℹ️ A few more projects and articles about JavaScript and algorithms on trekhleb.dev

Page 2

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Read the original article

Comments

By me_bx 2021-10-2214:102 reply

Similar collection of data structure for JavaScript, with a focus on performance: Mnemonist [1].

[1]: https://yomguithereal.github.io/mnemonist/

By maga 2021-10-2215:34

And another one: Structurae[1]

[1]: https://github.com/zandaqo/structurae

By mirekrusin 2021-10-2219:53

Also somehow related prelude [0].

[0] https://github.com/preludejs

By game_the0ry 2021-10-2214:303 reply

Do we really need yet another list of algorithms to memorize for interviews? Is another list going to make a better JavaScript engineer? Will help me understand JavaScript better? Will it help me on the job? Will it make me a faster and better React developer?

The obvious answer to all of the above rhetorical questions - fuck no.

That being said, it is still a topic of interviews, so I will up-vote bc this is pretty good implementation, even though this repo has been submitted to HN at least 4 times in the past.

Someone also mentioned Mnemonist [1] - that one is nice too.

[1] https://news.ycombinator.com/item?id=28957373

By Waterluvian 2021-10-2214:442 reply

Reciting algorithms is reverse gatekeeping. If an employer wants to grill you on them, get out of there.

By diroussel 2021-10-239:57

Are you saying it’s not important to know what a binary search is?

If I interview someone I don’t go deep into algorithms but I want to know that they know how about binary search or hashmaps. Ignorance of these shows ignorance of the basics of computation.

By imbnwa 2021-10-2217:282 reply

Doesn't GOOG go hard in the paint with those questions though?

By game_the0ry 2021-10-2217:371 reply

Not just GOOG, but all of FAANGMULAetc... and smaller start ups as well. Robinhood asked me a dynamic programming leetcode question for their web engineer (front end) role and Bloomberg asked me a OOP design question (asked to code in Python, even though I do not have Python on my resume...interviewer was a Python developer) for a javascript role - both were 1st round phone screens.

The tech industry has normalized to the state of asking such question - its rare to be interviewed on domain expertise, unless you are interviewing at a fortune 500 big corp.

By Waterluvian 2021-10-2221:51

I’ve never been interviewed in any of these nonsense ways.

I’m sure it’s popular. But it’s not everywhere.

By JasonCannon 2021-10-2217:34

Like he said. Get out of there.

By hungryforcodes 2021-10-2218:111 reply

I've wondered about this -- are such data structures useful? Interviews aside?

By dolni 2021-10-2219:142 reply

Being able to rattle off exactly how any particular data structure is implemented isn't useful for most developers. Being able to reason about algorithms and data structures _is_ useful in day-to-day development. And that does start with having a basic understanding of some subset of them.

You can clearly see the impact of computational ignorance on the modern web. JS engines have been optimized to hell and back and there are _still_ sites out there that are godawful slow for no good reason at all.

By hungryforcodes 2021-10-2313:57

Thanks for your response -- I think you're probably right, but alot of JS's slowness seems to just be all the junk a typical page needs to pull in via HTTPS for all the ads, frameworks and what not. Also videos that autostart themselves, obnoxious pop-ups that take your full screen up after you scroll 20% into an article, etc. That's not necessarily JS's fault. Also algorithms wouldn't help there. :p

By ape4 2021-10-2214:302 reply

Is there any practical reason use, say, a linked list from this library vs javaScript's native growable array. You can use unshift() to delete in the middle.

By wffurr 2021-10-2214:362 reply

Only the usual reasons to use a linked list. E.g. if you want to store stable references to cells in the linked list as in a linked hash map.

By filoeleven 2021-10-231:33

Are there practical reasons for using a linked list in JS? This is an honest question. I’ve taken immutability to heart, so storing a stable yet presumably mutable reference to a cell seems like a bad idea to me. (If it’s immutable, you can keep and use the cell’s value instead of caring that it came from a list.)

By oweiler 2021-10-2218:401 reply

That would be JavaScripts native Map, no?

By wffurr 2021-10-2219:10

TIL ES6 Map is guaranteed to iterate in insertion order. That always made me crazy in C++ too; the structure that I usually actually want is std::unordered_map not std::map.

There are other algorithms and use cases for a stable iteration into an ordered sequence, but I can’t think of any off-hand. It is true that it’s rare to prefer a linked list on modern CPU architecture.

By dahfizz 2021-10-2215:244 reply

Presumably, inserting and removing from the middle of a linked list is much faster than from an array.

By dehrmann 2021-10-2216:25

This property is only helpful if you have a reference to the node or are only making head/tail updates. If you have to do any amount of iteration, you're usually better off just rebuilding the list. It takes less memory, and is better on the cache.

The one other time a linked list is really good is if the list is large, and you can't afford the chance that you need to resize the array backing the vector.

By lostcolony 2021-10-2215:44

Though, weirdly, the author lists the deletion BigO as O(n). I would have thought maybe they meant traversing to the item to be deleted, but that would imply insertion is also O(n), since you'd have to traverse to the point of insert. Unless they are treating deletion as deleting from an arbitrary location, and insertion only at the head. Very strange.

But, yes; while real life performance characteristics vary (cache locality can lead to surprising wins for arrays even on insertions/deletions), at least theoretically, there are use cases where a LinkedList will win out.

EDIT: Huh. They also list the insertion and deletion cost of a hash table as being O(n). That...is not right. I mean, they call out "in the case of a perfect hash function it would be 1", but treating the literal worst case as the actual runtime is like saying quicksort runs in O(n^2) (which the author does not do).

By mirekrusin 2021-10-2220:21

I did some quick benchmarks the other day between sorted array vs red black tree of https://github.com/preludejs and it looked like rb tree had better generic performance for N > 20k - ie. memcpy is better for most cases/cases that fall under 20k. You should measure of course for your use case. Libraries/your implementation should make it easy to switch between underlying representation.

Hacker News