= Data Structures and Algorithms in JavaScript
:toc: macro
:toclevels: 2
Adrian Mejia <https://github.com/amejiarosario[@amejiarosario]>

image::https://travis-ci.com/amejiarosario/dsa.js.svg?branch=master["Build Status", link="https://travis-ci.com/amejiarosario/dsa.js"]
image::https://badge.fury.io/js/dsa.js.svg["npm version", link="https://badge.fury.io/js/dsa.js"]

This repository covers the implementation of the classical algorithms and data structures in JavaScript.

toc::[]

## Book

.You can check out the book that goes deeper into each topic and provide addtional illustrations and explanations.
- Algorithmic toolbox to avoid getting stuck while coding.
- Explains data structures similarities and differences.
- Algorithm analysis fundamentals (Big O notation, Time/Space complexity) and examples.
- Time/space complexity cheatsheet.

image::book/cover.png[link=https://books.adrianmejia.com/dsajs-data-structures-algorithms-javascript/, height=400]

== Data Structures
We are covering the following data structures.

image::https://user-images.githubusercontent.com/418605/46118890-ba721180-c1d6-11e8-82bc-6a671428b422.png[link=https://embed.kumu.io/85f1a4de5fb8430a10a1bf9c5118e015]

### Linear Data Structures
1. **Arrays**: Built-in in most languages so not implemented here. https://adrianmejia.com/blog/2018/04/28/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#Array[Post].
2. **Linked Lists**: each data node has a link to the next (and previous). https://github.com/amejiarosario/dsa.js/blob/master/src/data-structures/linked-lists/linked-list.js[Code] | https://adrianmejia.com/blog/2018/04/28/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#Linked-Lists[Post].
3. **Queue**: data flows in a "first-in, first-out" (FIFO) manner. https://github.com/amejiarosario/dsa.js/blob/master/src/data-structures/queues/queue.js[Code] | https://adrianmejia.com/blog/2018/04/28/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#Queues[Post]
4. **Stacks**:  data flows in a "last-in, first-out" (LIFO) manner. https://github.com/amejiarosario/dsa.js/blob/master/src/data-structures/stacks/stack.js[Code] | https://adrianmejia.com/blog/2018/04/28/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#Stacks[Post].

### Non-Linear Data Structures
1. **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. https://github.com/amejiarosario/algorithms.js/tree/master/src/data-structures/trees[Code] | https://adrianmejia.com/blog/2018/06/11/data-structures-for-beginners-trees-binary-search-tree-tutorial/[Post]
	.. **Binary Trees**: same as tree but only can have two children at most. https://github.com/amejiarosario/algorithms.js/tree/master/src/data-structures/trees[Code] | https://adrianmejia.com/blog/2018/06/11/data-structures-for-beginners-trees-binary-search-tree-tutorial/#Binary-Trees[Post]
	.. **Binary Search Trees** (BST): same as binary tree, but the nodes value keep this order `left < parent < rigth`. https://github.com/amejiarosario/algorithms.js/blob/master/src/data-structures/trees/binary-search-tree.js[Code]] | https://adrianmejia.com/blog/2018/06/11/data-structures-for-beginners-trees-binary-search-tree-tutorial/#Binary-Search-Tree-BST[Post]
	.. **AVL Trees**: Self-balanced BST to maximize look up time. https://github.com/amejiarosario/algorithms.js/blob/master/src/data-structures/trees/avl-tree.js[Code] | https://adrianmejia.com/blog/2018/07/16/self-balanced-binary-search-trees-with-avl-tree-data-structure-for-beginners/[Post]
	.. **Red-Black Trees**:  Self-balanced BST more loose than AVL to maximize insertion speed. https://github.com/amejiarosario/algorithms.js/blob/master/src/data-structures/trees/red-black-tree.js[Code]
2. **Maps**: key-value store.
	.. **Hash Maps**: implements map using a hash function. https://github.com/amejiarosario/algorithms.js/blob/master/src/data-structures/hash-maps/hashmap.js[Code] | https://adrianmejia.com/blog/2018/04/28/data-structures-time-complexity-for-beginners-arrays-hashmaps-linked-lists-stacks-queues-tutorial/#HashMaps[Post]
	.. **Tree Maps**: implement map using a self-balanced BST. https://github.com/amejiarosario/dsa.js/blob/master/src/data-structures/maps/tree-maps/tree-map.js[Code]
3. **Graphs**: data *nodes* that can have a connection or *edge* to zero or more adjacent nodes. Unlike trees, nodes can have multiple parents, loops. https://github.com/amejiarosario/algorithms.js/blob/master/src/data-structures/graphs/graph.js[Code] | https://adrianmejia.com/blog/2018/05/14/data-structures-for-beginners-graphs-time-complexity-tutorial/[Post]

## Algorithms

.We cover the following algorithms and techniques.
* Sorting algorithms
  ** Bubble Sort. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/sorting/bubble-sort.js[Code]
  ** Insertion Sort. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/sorting/insertion-sort.js[Code]
  ** Selection Sort. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/sorting/selection-sort.js[Code]
  ** Merge Sort. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/sorting/merge-sort.js[Code]
  ** Quicksort. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/sorting/quick-sort.js[Code]
* Greedy Algorithms
	** Fractional Knapsack Problem. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/knapsack-fractional.js[Code]
* Divide and Conquer
  ** Fibonacci Numbers. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/fibonacci-recursive.js[Code]
* Dynamic Programming
	** Fibonacci with memoization. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/fibonacci-dynamic-programming.js[Code]
* Backtracking algorithms
	** Word permutations. https://github.com/amejiarosario/dsa.js/blob/master/src/algorithms/permutations-backtracking.js[Code]


