• Stars
    star
    7,590
  • Rank 5,032 (Top 0.1 %)
  • Language
    JavaScript
  • License
    MIT License
  • Created almost 8 years ago
  • Updated 9 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

πŸ₯žData Structures and Algorithms explained and implemented in JavaScript + eBook

image

Data Structures and Algorithms in JavaScript

CircleCI NPM version chat

This is the coding implementations of the DSA.js book and the repo for the NPM package.

In this repository, you can find the implementation of algorithms and data structures in JavaScript. This material can be used as a reference manual for developers, or you can refresh specific topics before an interview. Also, you can find ideas to solve problems more efficiently.

Interactive Data Structures

Table of Contents

Installation

You can clone the repo or install the code from NPM:

npm install dsa.js

and then you can import it into your programs or CLI

const { LinkedList, Queue, Stack } = require('dsa.js');

For a list of all available data structures and algorithms, see index.js.

Features

Algorithms are an essential toolbox for every programmer.

You will need to mind algorithms runtime when you have to sort data, search for a value in a big dataset, transform data, scale your code to many users, to name a few. Algorithms are just the step you follow to solve a problem, while data structures are where you store the data for later manipulation. Both combined create programs.

Algorithms + Data Structures = Programs.

Most programming languages and libraries indeed provide implementations for basic data structures and algorithms. However, to make use of data structures properly, you have to know the tradeoffs to choose the best tool for the job.

This material is going to teach you to:

  • πŸ›  Apply strategies to tackle algorithm questions. Never to get stuck again. Ace those interviews!
  • βœ‚οΈ Construct efficient algorithms. Learn how to break down problems into manageable pieces.
  • 🧠 Improve your problem-solving skills and become a well-rounded developer by understanding fundamental computer science concepts.
  • πŸ€“ Cover essential topics, such as big O time, data structures, and must-know algorithms. Implement 10+ data structures from scratch.

What's Inside

All the code and explanations are available on this repo. You can dig through the links and code examples from the (src folder). However, the inline code examples are not expanded (because of Github's asciidoc limitations), but you can follow the path and see the implementation.

Note: If you prefer to consume the information more linearly, then the book format would be more appropriate for you.

The topics are divided into four main categories, as you can see below:

Computer Science nuggets without all the mumbo-jumbo. (Click to expand)

Learn to calculate run time from code examples

Translating lines of code to an approximate number of operations


Learn how to compare algorithms using Big O notation. (Click to expand)

Comparing algorithms using Big O notation

Let's say you want to find the duplicates on an array. Using Big O notation, we can compare different solutions that solve the same problem but has a massive difference in how long it takes to do it.


8 examples to explain with code how to calculate time complexity. (Click to expand)

8 examples to explain with code how to calculate time complexity

Most common time complexities

image

Time complexity graph

Most common time complexities


Understand the ins and outs of the most common data structures. (Click to expand)

When to use an Array or Linked List. Know the tradeoffs. (Click to expand)

Use Arrays when…

  • You need to access data in random order fast (using an index).
  • Your data is multi-dimensional (e.g., matrix, tensor).

Use Linked Lists when:

  • You will access your data sequentially.
  • You want to save memory and only allocate memory as you need it.
  • You want constant time to remove/add from extremes of the list.
  • when size requirement is unknown - dynamic size advantage

Build a List, Stack, and a Queue. (Click to expand)

Build any of these data structures from scratch:


Understand one of the most versatile data structure of all: Hash Maps. (Click to expand)

Learn how to implement different types of Maps such as:

Also, learn the difference between the different Maps implementations:

  • HashMap is more time-efficient. A TreeMap is more space-efficient.
  • TreeMap search complexity is O(log n), while an optimized HashMap is O(1) on average.
  • HashMap’s keys are in insertion order (or random depending on the implementation). TreeMap’s keys are always sorted.
  • TreeMap offers some statistical data for free such as: get minimum, get maximum, median, find ranges of keys. HashMap doesn’t.
  • TreeMap has a guarantee always an O(log n), while HashMaps has an amortized time of O(1) but in the rare case of a rehash, it would take an O(n).

Know the properties of Graphs and Trees. (Click to expand)

Know all the graphs properties with many images and illustrations.

graph example with USA airports

Graphs: data nodes that can have a connection or edge to zero or more adjacent nodes. Unlike trees, nodes can have multiple parents, loops. Code | Graph Time Complexity

Learn all the different kinds of trees and their properties.

tree data structure properties

  • Trees: data nodes has zero or more adjacent nodes a.k.a. children. Each node can only have one parent node otherwise is a graph, not a tree. Code | Docs


Implement a binary search tree for fast lookups.

From unbalanced BST to balanced BST

1                           2
  \                       /   \
   2        =>           1     3
    \
     3

Never get stuck solving a problem with 7 simple steps. (Click to expand)
  1. Understand the problem
  2. Build a simple example (no edge cases yet)
  3. Brainstorm solutions (greedy algorithm, Divide and Conquer, Backtracking, brute force)
  4. Test your answer on the simple example (mentally)
  5. Optimize the solution
  6. Write code. Yes, now you can code.
  7. Test your written code
  8. Analyse the complexity, both space and time, and make sure to optimize further.

Full details here


Master the most popular sorting algorithms (merge sort, quicksort, etc.) (Click to expand)

We are going to explore three essential sorting algorithms O(n^2), which have low overhead:

and then discuss efficient sorting algorithms O(n log n) such as:


Learn different approaches to solve problems such as divide and conquer, dynamic programming, greedy algorithms, and backtracking. (Click to expand)

We are going to discuss the following techniques for solving algorithms problems:

  • Greedy Algorithms: makes greedy choices using heuristics to find the best solution without looking back.
  • Dynamic Programming: a technique for speeding up recursive algorithms when there are many overlapping subproblems. It uses memoization to avoid duplicating work.
  • Divide and Conquer: divide problems into smaller pieces, conquer each subproblem, and then join the results.
  • Backtracking: search all (or some) possible paths. However, it stops, and go back as soon as notice the current solution is not working.
  • Brute Force: generate all possible solutions and tries all of them. (Use it as a last resort or as the starting point).

FAQ

How would I apply these to my day-to-day work? (Click to expand)

As a programmer, we have to solve problems every day. If you want to solve problems well, it's good to know about a broad range of solutions. Often, it's more efficient to learn existing resources than stumble upon the answer yourself. The more tools and practice you have, the better. This book helps you understand the tradeoffs among data structures and reason about algorithms performance.

Why you created this repo/book?

There are not many books about Algorithms in JavaScript. This material fills the gap. Also, it's good practice :)

Is there anyone I can contact if I have questions about something in particular?

Yes, open an issue or ask questions on the [slack channel](https://dsajs-slackin.herokuapp.com).

Book

This project is also available in a book. You will get a nicely formatted PDF with 180+ pages + ePub and Mobi version.

dsa.js book

Support

Reach out to me at one of the following places!

License

License

More Repositories

1

todoAPIjs

βœ… NodeJS, ExpressJS and MongoDB RESTful API Tutorial
JavaScript
201
star
2

meanshop

πŸ›’ Building an e-commerce application with the MEAN stack
JavaScript
149
star
3

Backbone-tutorial

Fat-free Backbone.js tutorial (walkthrough for absolute beginners)
HTML
80
star
4

amejiarosario.github.io

Personal Blog
HTML
23
star
5

angular-todo-app

Angular 2 Todo App (with routing, production env and deployment)
TypeScript
20
star
6

sink

πŸ“š Modern Full Stack Javascript Development with MEAN
9
star
7

algorithms-problems

topcoder, google code jam and other algorithms exercises...
Java
4
star
8

faceted-search

faceted search
Ruby
4
star
9

algorithms_part1

Java
4
star
10

cryptobot

πŸ’° πŸ€– Cryptocurrency trading bot for multiple platforms and coins (gdax/coinbase & dollar/bitcoin/ethereum/litecoin)
JavaScript
3
star
11

Book-Summarizer

Book/Text Summarizer - Extract most frequent words and phrases
JavaScript
3
star
12

node-proxy-latency-tester

Node proxy for simulating webservers latencies on localhost or testing environments (CI)
JavaScript
3
star
13

blog-on-rails

Yet Another Blog On Rails (YABOR)
JavaScript
3
star
14

ninjalearning

Ninja Learning | Semantic eLearning resources manager
Ruby
2
star
15

vue-todo-app

Learn Vue.js doing a Todo app with routing
JavaScript
2
star
16

polyglot-programmer

Learn new languages by comparing it with the one(s) you already know
TypeScript
2
star
17

BrainTrainer

App to boost your speed performing calculations through training
Ruby
2
star
18

ticketee

Tracks tickets and groups them into projects
Ruby
1
star
19

jerkyll-drupal7-migration

Migrate drupal7 blog to jerkyll/octopress blog.
JavaScript
1
star
20

Struts2-Tiles-Ajax

Struts2,Tiles,Interceptors,Ajax
Java
1
star
21

TcpServer

tcp server using Qt
Lua
1
star
22

tumimo

Explore your social network data by yourself
JavaScript
1
star
23

rit48

Ruby
1
star
24

Trackstart

project's issues management
JavaScript
1
star
25

deprecated-meanshop

Building an e-commerce application with the MEAN stack
JavaScript
1
star
26

codebreaker

Code Breaker - BDD
Ruby
1
star
27

mobile-inventory-app

Mobile Inventory App
JavaScript
1
star
28

---ja-learning

eLearning
JavaScript
1
star
29

ninjalearning_old1

Ninja Learning | Semantic eLearning resources manager
Ruby
1
star
30

pocket-timezone-converter

Web app for mobiles to convert time zone easily
JavaScript
1
star
31

ama

ask me anything!
1
star
32

shirika

organize and prioritize resource list
JavaScript
1
star
33

sample-app

sample app with login, basic styles, ...
Ruby
1
star
34

ruby-scripts

miscellaneous ruby script to perform SQL, Log and general purpose text processing
Java
1
star
35

semantic_test

test with ruby and semantic web
Ruby
1
star
36

Java-Practice

Java 707 @ rit
1
star
37

ninjalearning-old

Semantic eLearning System
Ruby
1
star