JavaScript® (often shortened to JS) is a lightweight, interpreted, object-oriented language with first-class functions, most known as the scripting language for Web pages, but used in many non-browser environments as well such as node.js or Apache CouchDB. It is a prototype-based, multi-paradigm scripting language that is dynamic, and supports object-oriented, imperative, and functional programming styles.

javascript

This course teaches you how to implement your first data structures and algorithms. In the process, you’ll learn some fundamental computer science concepts as well. We’ll build these from scratch using JavaScript, but what we learn can be taken and used in any other language, too.

You will learn how to build: queues, stacks, linked lists, graphs, and trees. You’ll learn to implement several different sorting algorithms: bubble, insert, merge, and quick. Each of these lessons will not only teach you their implementation, but the tradeoffs made in choosing one over another. By proxy, you’ll learn about concepts like Big O notation and recursion.

Whether you've studied computer science before and need a refresher, or you're like me and never had the chance to study it in school, my hope is that this course is a great introduction to the concepts of data structures and algorithms.

We'll cover queues, stacks, linked lists, graphs and trees, breadth first and depth first search, tree traversal, and a variety of sorting algorithms.

The goal of this course isn't for you to be able to implement these from scratch, though that's precisely what we'll do. Instead, the goal is to teach you to think differently, to learn how to use the right tool for the job, to break problems down into their atomic, algorithmic steps, and even to think divergently, to conceive of several solutions to the same problem understand their tradeoffs. These skills will make you a better engineer for sure.

Course Introduction: Data Structures and Algorithms in JavaScript

In this lesson, you will learn how to create a queue in JavaScript. A queue is a first-in, first-out data structure (FIFO). We can only remove items from the queue one at a time, and must remove items in the same sequence as they were placed in the queue.

Queue Data Structure in JavaScript

In this lesson, you'll learn how we can combine several queues to create a new data structure: a priority queue. A priority queue allows the user to add items to the queue that are deemed to be high priority, and get moved ahead in the line. This added complexity is simple to achieve and is a good example of how we can build up complexity through the use of data structures.

Priority Queue JavaScript Data Structure 

In this lesson, you'll learn how to create a stack data structure. A stack is a collection of items that obeys the principle of "last in, first out". Like a stack of plates, we can only access the topmost plate at any time. We must remove that plate before we get down to other plates. This is useful for function calls, hence why it's called a "call stack" in JavaScript.

Stack Data Structure in JavaScript

A linked list is a collection of items where each item points to the next one in the list. Because of this structure, linked lists are very slow when searching for an item at a particular index. An array, by comparison, has quick `get`s when searching for an index, but a linked list must start at the beginning, often called the "head", and loop through each item's `next` property until we arrive at the item. This makes `get`s in a linked list an operation that takes `O(n)` time.

While `get`s might be slow in a linked list, it's other operations, like `push` and `delete` come with some great benefits we will see in the lesson.

Linked List Data Structure in JavaScript

A graph is a data structure comprised of a set of nodes, also known as vertices, and a set of edges. Each node in a graph may point to any other node in the graph. This is very useful for things like describing networks, creating related nonhierarchical data, and as we will see in the lesson, describing the relationships within one's family.

JavaScript Graph Data Structure

Breadth first search is a graph search algorithm that starts at one node and visits neighboring nodes as widely as possible before going further down any other path. This algorithm requires the use of a queue to keep track of which nodes to visit, so it might be worth your time to brush up on that data structure before watching this lesson.

Breadth First JavaScript Search Algorithm for Graphs

Depth first search is a graph search algorithm that starts at one node and uses recursion to travel as deeply down a path of neighboring nodes as possible, before coming back up and trying other paths.

Write a Depth First Search Algorithm for Graphs in JavaScript

A tree data structure is a graph without any cycles. I can hear you saying, "Kyle, that's a super helpful explanation," with a healthy dose of sarcasm already. "No cycles" means that no three nodes create a circuitous path. In a tree, nodes have a single parent node and may have many children nodes. They never have more than one parent nor point to any siblings.

The most common tree structure you see is a web page. The underlying structure is often called the "DOM tree". The `html` element forms the root of our tree, with children of `head` and `body`, so on and so forth. In this lesson, we'll create a quick example of a DOM tree with our tree data structure.

Tree Data Structure in JavaScript

A binary tree is a tree where each node may only have up to two children. These children are stored on the `left` and `right` properties of each node.

When traversing a binary tree, we have three common traversal algorithms: in order, pre-order, and post-order. In this lesson, we write each of these algorithms and explore their differences.

Build a Binary Tree  in JavaScript and Several Traversal Algorithms

Bubble sort is often one of the first sorting algorithms people learn because it closely resembles how we might physically sort a collection of items. We loop through our list of items, comparing our current item with the next one. If our current item is less than the next one, we swap them. We continue looping through the list until we make a loop without any swaps.

This is a very inefficient algorithm with a time complexity of `O(n^2)`. Given a list of length `n`, we must compare each item against every other item in the list, which gives us `n * n`, or rather `n^2`. That means for a list of length 10, our worst case scenario will require 100 loops to sort our list. A list just twice as long will take 4x as many loops to solve.

Sort an Array with a JavaScript do while Loop using Bubble Sort

Insertion sort is another sorting algorithm that closely resembles how we might sort items in the physical world. We start at the second item in our collection and make the assumption that this item is a sorted list of length 1. We then compare all the items before it and determine if it needs to be "inserted" to the left or right of our item. We then move onto the second item, again comparing it to every item before it in the list, inserting those items correctly.

Because this algorithm requires two loops, one inside the other, the worst case scenario of our algorithm still requires a time complexity of `O(n^2)`. This is also an inefficient sorting algorithm, but if our list is mostly sorted already, it will perform a slight bit better than bubble sort.

Sort an Array with a Nested for Loop using Insertion Sort in JavaScript

Merge sort is a "divide and conquer" algorithm. That is, we break the array down into smaller arrays that are easier and faster to sort; then we stitch the results of calling merge sort on these smaller arrays back together to get our final sorted list.

This is a recursive algorithm, which dramatically improves the efficiency of our sort compared to bubble or insertion sort. The worst case scenario for our list is `O(n log(n))`, that is, we must go through every item at least once, hence the first `n`, but with each recursive call we operate on half the data set. This means that when we double `n`, we only get one more operation, instead of `n` number of operations like in bubble or insertion sort.

Divide and Recurse Over an Array with Merge Sort in JavaScript

Quick sort is another "divide and conquer" algorithm, calling itself recursively to sort our list. With quick sort, we pick an index of our array to be the "pivot". Every item is compared to the pivot, and pushed into a left or right array depending on that comparison. Quick sort is then called on these left and right arrays.

This is an efficient algorithm and uses less memory than merge sort. The time complexity of quick sort is `O(n log(n))`. Sorting any list requires at least one pass through the entire list, hence `n`, but increasing the size of our list doesn't lead to a linear or quadratic increase in operations. Each doubling in size only results in one more level of operations.

Data Structures and Algorithms in JavaScript

Kyle Shevlin

Course Content