📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings

Overview

JavaScript Algorithms and Data Structures

CI codecov

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

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

npm install

Run ESLint

You may want to run it to check code quality.

npm run lint

Run all tests

npm test

Run tests by name

npm test -- 'LinkedList'

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:

npm test -- 'playground'

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.

Big O graphs

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 n2 n2 1 Yes
Insertion sort n n2 n2 1 Yes
Selection sort n2 n2 n2 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) n2 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))2 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

Comments
  • German translation

    German translation

    hey hey, great project! I would like to make a german translation. So I have a reason to look deeper into the texts. I'll collect the information about the translation process from the other issues, but if I have questions I can ask them here, right?

    opened by denizbinay 14
  • quick sort problem

    quick sort problem

    i am writing quick sort algorthm, and when i testing my code, the result makes me confused.

    RangeError: Maximum call stack size exceeded at Array.push ()

    let arr = [0,-1,1,0,1,-1,100,23,17,56,39,47,23,-34,-56];

    export default function quickSort(array){
        let len = array.length;
        if(len <= 1) return array;
    
        let piviot = array.pop();
    
        let left = [], right = [];
        for (let i = 0; i < len; i++) {
            if(array[i] < piviot){
                left.push(array[i]);
            }
            else{
                right.push(array[i])
            }
        }
        return quickSort(left).concat(piviot,quickSort(right));
    }
    

    when i change for loop to forEach, problem is disappeared, but i don't know why.

    
    export default function quickSort(array){
        let len = array.length;
        if(len <= 1) return array;
    
        let piviot = array.pop();
    
        let left = [], right = [];
        array.forEach(item => {
            if(item < piviot){
                left.push(item)
            }
            else{
                right.push(item);
            }
        });
        return quickSort(left).concat(piviot,quickSort(right));
    }
    
    opened by Facefall 6
  • Add in-place sort to QuickSort.js

    Add in-place sort to QuickSort.js

    I've always been a big fan of the in-place variation of the Quicksort algorithm. Not sure if you were looking for variations on existing implementations, but I thought it was different enough to warrant a pull request if you are interested.

    It was also more performant when testing on arrays of 10,000 elements for integers between 0-10,000:

    /*
    const testTime = (callback) => {
    	let time1 = performance.now();
    	callback();
    	let time2 = performance.now();
    	return time2 - time1;
    };
    
    const arrOne = new Array(10000).fill(null).map(el => Math.floor(Math.random() * 10000));
    const arrTwo = new Array(10000).fill(null).map(el => Math.floor(Math.random() * 10000));
    
    const inPlace = testTime(() => QuickSort.sortInPlace(arrOne));
    const nonInPlace= testTime(() => QuickSort.sort(arrTwo));
    
    console.log(inPlace);
    //=>9.799999999813735
    
    console.log(nonInPlace);
    //=>50.00000004656613
    */
    
    opened by robtaussig 6
  • issue while running program

    issue while running program

    Hi i dont know why but i am not able to run your program , i am new to js please help me

    Error
    > [email protected] test ......\javascript-algorithms
    > jest "-t" "playground"
    
    'jest' is not recognized as an internal or external command,
    operable program or batch file.
    npm ERR! Test failed.  See above for more details.
    

    image

    opened by Krish-bhardwaj 5
  • Opening for Full Stack JS Developer

    Opening for Full Stack JS Developer

    Hello, Igor! I`ve checked your profile and I can see you work with Javascript. Our company has very interesting opportynity, please send me a message vie indicated email to discuss it. Have a great day!

    Sergiy, e-mail: [email protected]

    opened by SergB38 5
  • rabinKarp seems to miss some matches

    rabinKarp seems to miss some matches

    Hello,

    I recently tried to run some property based tests on the algorithms provided in javascript-algorithms. I discovered the following failing case with rabinKarp algorithm:

    expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(2); // output: -1
    

    In order to find it, I used fast-check framework with the property:

    // for any strings a, b and c
    // rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
    fc.assert(
      fc.property(
        fc.string(), fc.string(), fc.string(),
        (a, b, c) => rabinKarp(a + b + c, b) !== -1
      )
    );
    

    I was not able to have a smaller example for this precise case :/

    bug 
    opened by dubzzz 5
  • AVL tree does not rebalance after removal

    AVL tree does not rebalance after removal

    Hi! Thanks for your project. I can't seem to find the removal algorithm in AVL tree: if it simply borrows the binary tree removal, it's incomplete. I was particularly interested in that, cause I have been looking for a removal procedure that doesn't mutate the nodes.

    Cheers.

    bug 
    opened by w8r 5
  • Getting every possible shortest path between two nodes

    Getting every possible shortest path between two nodes

    Getting every possible shortest path between two nodes using dijkstra algorithm ( ranked by best path ). Any one getting javascript code that would be awesome.

    opened by anand-010 4
  • Adds Portuguese (pt-BR) translation

    Adds Portuguese (pt-BR) translation

    Summary

    So I translated most of the content, with exception of the algorithms for now, to Portuguese, specifically to Brazilian Portuguese.

    If anythings needs to be change, just point out :)

    opened by themgoncalves 4
  • Help =)

    Help =)

    Hello, I've been programming for about 7 years now, I stopped but now I want to go back more than 0 and learn everything again more on the SQL side, where should I start?

    opened by Dogzeca 0
  • Eu realmente não entendi

    Eu realmente não entendi

    Sou iniciante nessa área de programação e recentemente estou pesquisando/aprendendo sobre JavaScript/CSS/HTML, porém recentemente estou tendo um grande problema em um cod que era parar ser uma calculadora (bem básico, eu sei), porém o resultado simplesmente não sai e eu não encontro onde errei. CODIGO: test.txt

    opened by Hirasawa-San 1
  • Eslint parsing error

    Eslint parsing error

    I'm facing "src\data-structures\queue\README.md 1:1 error Parsing error: Unexpected character '#' " error. I'm on the windows platform and tried to ignore .md files adding { "eslintIgnore" : ["**/*.md"], } propety to eslintIgnore file. am still facing the same issue. How to resolve this?

    opened by alifhs 0
Owner
Oleksii Trekhleb
Software Engineer at @uber
Oleksii Trekhleb
Algorithms and Data Structures implemented in TypeScript for beginners, following best practices.

The Algorithms - TypeScript TypeScript Repository of TheAlgorithms, which implements various algorithms and data structures in TypeScript. These imple

The Algorithms 166 Dec 31, 2022
Ace your next Javascript coding interview by mastering data structures and algorithms.

The Coding Interview: Algorithms + Data Structures Ace your next Javascript coding interview by mastering data structures and algorithms. Problem 1: S

Wallflower 5 Sep 19, 2022
Data structures & algorithms implementations and coding problem solutions. Written in Typescript and tested with Jest. Coding problems are pulled from LeetCode and Daily Coding Problem.

technical-interview-prep Data structures & algorithms implementations and coding problem solutions. Written in Typescript and tested with Jest. Coding

Lesley Chang 7 Aug 5, 2022
Bringing an all Open-Source Platform to study Data Structures and Algorithms ⚡

NeoAlgo-Docs Bringing an all Open-Source Platform to study Data Structures and Algorithms ⚡ ?? Installation You will need to have NodeJS and Yarn inst

Tesseract Coding 24 Jun 2, 2022
A Typescript companion to the book A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

This repository aims to be a companion to the book A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow. I rewrote most of the data s

Alexandre Lim 29 Dec 3, 2022
A collection of all the data structures implemented in javascript code

Data structures A collection of all the data structures implemented in javascript code, interview questions & problems ( with solutions ) Contributors

MSK Web development 2 May 1, 2022
The basics data structures implemented with javascript.

Estrutura de Dados com Javascript Tudo que está escrito e codificado aqui dentro desse repositório foi retirado do livro Estrutura de dados e algoritm

Gabriel Valin 7 Oct 18, 2022
A long list of (advanced) JavaScript questions, and their explanations

JavaScript Questions I post multiple choice JavaScript questions on my Instagram stories, which I'll also post here! Last updated: June 12th From basi

Lydia Hallie 50.9k Jan 1, 2023
Script written in JavaScript (Node) that uploads CGM readings from LibreLink Up to Nightscout

Nightscout LibreLink Up Uploader/Sidecar Simple Script written in JavaScript (Node) that uploads CGM readings from LibreLink Up to Nightscout. The upl

Timo Schlüter 87 Jan 7, 2023
API of my readings, developed in Nest.js, MongoDB, Nginx and Dockerized

My Readings step by step for configuration with docker OBS: required docker and docker-compose cp -r .env.sample .env docker-compose up example what t

William Koller 30 Jul 1, 2022
A new way to share your readings with friends. Hope you like it!

Getting Started with Create React App This project was bootstrapped with Create React App. Available Scripts In the project directory, you can run: np

Gardenia Georgia 4 Sep 9, 2022
🍎 A simple application which enables you to sync readings from your Withings scale to a Notion page.

weight-logger weight-logger is a simple application which enables you to sync readings from your Withings scale to a Notion page. Preview Installation

Juri Adams 2 Jan 14, 2022
OpenXAI : Towards a Transparent Evaluation of Model Explanations

OpenXAI : Towards a Transparent Evaluation of Model Explanations Website | arXiv Paper OpenXAI is the first general-purpose lightweight library that p

null 121 Dec 28, 2022
Serialization library for data-oriented design structures in JavaScript

Data-oriented Serialization for SoA/AoA A zero-dependency serialization library for data-oriented design structures like SoA (Structure of Arrays) and

null 11 Sep 27, 2022
easily building data structures that are serializable, validatable, and fully typed.

@davecode/structures [beta/wip] Structures is a TypeScript library for easily building data structure classes that are Serializable: Can convert rich

Dave Caruso 2 May 22, 2022
Code accompanying my illustrated Data structures video series on YouTube

Code accompanying my illustrated Data structures video series on YouTube

Kamran Ahmed 122 Dec 10, 2022
Data Structures

Data-Structures Data structures implementaion using Javascript ??‍?? Data-Structures is a Github repository that contains the implementaion of most of

Mohanad Fteha 5 Sep 14, 2022
A high-resolution local database that uses precise algorithms to easily record data in local files within a project with persistent JSON and YAML support designed to be easy to set up and use

About A high-resolution local database that uses precise algorithms to easily record data in local files within a project with persistent JSON and YML

Shuruhatik 5 Dec 28, 2022
Simple Library implemented using HTML, CSS and JavaScript. This is a simple implementation of JavaScript Modules of ES6.

Awesome-books A single page project with the porpuse of storing books' titles and authors. Built With CSS, HTML & Javascript. How to run in your local

Saadat Ali 7 Feb 21, 2022