Abstract Data Types & Data Structures

Days 1–2.5 in Fullstack Academy’s Remote Immersive Program

Beth Qiang
Nov 3, 2016 · 11 min read

In the first two and a half days of Fullstack’s Junior phase, we created a command line “create your own adventure” game, where the user could select one of a couple of options and the game would change based on the option selected. Then, we dove straight into abstract data types and data structures.

An abstract data type is a description of information, how that information is connected, and performable operations on that information. If you think that’s a little vague, that’s because it is. A few (slightly more) concrete examples of abstract data types are lists, which are ordered collections of elements, and dictionaries, which are sets of key-value pairs.

A data structure is a specific programmatic solution for storing, referencing, and accessing data in computer memory. Their purpose is to implement some kind of abstract data type — so, for example, you can implement a binary search tree (abstract data type) with a linked list (a data structure). (I’ll talk about both of these in more detail in a bit.)

In class, we concentrated on two data structures, a queue and a linked list. Then, we implemented two abstract data types: a binary search tree, and a hash table.

Queues

A queue, as it’s aptly named, can be thought of a queue of people (or, for us Americans, a line). They have a front and a back. You can only add (enqueue) to the back, and you can only remove (dequeue) from the front. Queues don’t have indexes, so you can’t access elements that way, but elements are sorted by insertion order. Queues operate under the First In, First Out principle — that is, the first thing that is added on will also be the first thing that is removed.

We implemented a queue using a simple array with the ability to add an element to a queue, remove an element from a queue, and find the size of the queue. We were expressly forbidden from using any Array.prototype methods (including, but not limited to, .push, .shift, .length, etc.) Instead, we were instructed to use head and tail indices.

Our solution was relatively simple. We created a constructor, Queue, and placed an array, head, and tail properties on it. We placed the methods enqueue, dequeue, and size on Queue’s prototype. We used the tail index of our created array to add an element to our queue, and then incremented the tail index by one so that whatever element we added after would be placed after. We did something similar in our dequeue method — we returned the head index of the array, and incremented the head index by one.

Then, to find the size, we subtracted the tail index from the head index. We faced a small challenge in attempting to manage underflow — that is, preventing the head index to be larger than the tail index, in which case the size becomes negative. A simple if statement that returned undefined in the dequeue method fixed that, and that was that!

Linked Lists

Next, we created a linked list. A linked list looks like this:

Each node has two parts: where data is actually stored, and a reference to where the next node is stored (node.next). Linked lists can also be bi-directional and have a third part: a reference to where the previous node is stored.

Linked lists are preferable over other storage methods, such as arrays, when:

  • You need to insert/delete elements in the middle or at the beginning — arrays need to shift the entirety of the “rest” of the elements when you insert or delete.
  • You need a flexible data storage method. Arrays are of a fixed length and expanding it may mean copying it to another place in memory. (Note: arrays in JavaScript aren’t “true” arrays, so this is less of a concern, but this statement holds true for a lot of other languages.)

In order to create a linked list, we created two constructor functions: LinkedList, which was empty, but necessary so that we could place methods on the prototype, and Node, which represented each “element” in the linked list. Ours was bi-directional, so the Node constructor had a value property, a previous property, and a next property.

To add a node to the tail, we created a new instance of a Node. If a tail already existed in our list, we’d assign this new node to the .next property of the current tail. If a tail didn’t already exist, we’d assign both the head and the tail properties to the new Node. (Because if a tail doesn’t already exist, then a head doesn’t either.)

LinkedList.prototype.addToTail = function(value) {
var newNode = new Node(value, this.tail);
if (this.tail) {
this.tail.next = newNode;
} else {
this.head = newNode;
}
this.tail = newNode;
};

To add a node to the head, we did the exact same thing except added a “this.head” to the parameters, exchanged “tail” with “head,” and vice versa, and “next” with “previous.”

To remove a node from the head, we first checked if the head property existed — if it didn’t, return undefined. If it did, then we stored the value of the head in a variable and set the head equal to the next head. If the next head property (which is now the current head property) existed, we set the previous head to null. (If we actually had removed the head, then there would be nothing in its place once it was removed.) If the next head property didn’t exist, that indicated that we just removed the last element in our list, and there was nothing left in our linked list, so we set the tail property to null. Then, we returned the variable of our original head.

LinkedList.prototype.removeHead = function() {
if (!this.head) return;
var oldHead = this.head.value;
this.head = this.head.next;
if (this.head) {
this.head.previous = null;
} else {
this.tail = null;
}
return oldHead;
};

Binary Search Trees

Binary search trees look like this:

You start with the root node on top, which is some value. Then, when you add a node, if the node is smaller than the parent node, then it goes to the left. If it’s larger, it goes to the right. So, in our example above, if we’re using 3 as the parent node and want to add the number 6, it would go to the right of 3 because it’s larger.

Binary trees are useful if you want your lookup to be fast, because instead of having to go through an entire array or linked list, you effectively “cut out” half of your set every time you move from node to node.

In order to find any node in the tree above, you only have to look a maximum of 6 times!

We implemented a binary search tree with a linked list. We started with a BinarySearchTree constructor that had the properties for the value, the left node (this.left), the right node (this.right), and this.length, which we initially set to 1 as the number of nodes in the tree.

To insert a value, we first needed to decide if it was going to go to the left or right. If the value we wanted to add is less than the root value, it’d be placed to the left. If it’s greater, it’d be placed to the right. Regardless of where it went, the new node should be a new instance of BinarySearchTree — effectively, each node was its own tree. We’d also need to check if there was already a node to the left or right. If there was, then we’d call the function recursively on the next node until it found an empty spot. Lastly, we’d need to increment the size by one.

BinarySearchTree.prototype.insert = function(value) {
if (value < this.value) {
if (this.left === null) {
this.left = new BinarySearchTree(value);
this.length++;
} else {
this.left.insert(value);
}
} else {
if (this.right === null) {
this.right = new BinarySearchTree(value);
this.length++;
} else {
this.right.insert(value);
}
}
};

Then, we added a method on the prototype that would check if the tree already contained a given value. We did this recursively as well. First, we started with the root node, and checked if that was equal to the given value. If it wasn’t, we’d check if the given value was less than or greater than the root value. Just like inserting a value, if it was less than, we’d traverse down to the left linkage, and do the opposite if it was greater than. If the value wasn’t found in the child node, we’d run the function again on the child node to see if that child node matched.

This illustrates one of the primary advantages of using a binary search tree: your search is cut significantly. Instead of searching in the entire set, your search is effectively cut in half at every node.

Our code originally looked like this:

BinarySearchTree.prototype.contains = function(value) {
if (value === this.value){
return true;
} else {
if (value < this.value) {
if (this.left === null) {
return false;
}
this.left.contains(value);
} else {
if (this.right === null) {
return false;
}
this.right.contains(value);
}
}
return false;
};

Do you see a problem in this code? When we ran it with numbers that we knew were in the set, we’d always get false. When we changed “return false” to “return ‘foo’”, we’d get foo. So, we needed to figure out why our function seemed to completely disregard, well, everything that was in it.

We started by console logging each number as it was compared, and found that our program was finding matches — but still seemed to be skipping straight down to the bottom. After much struggling and finally asking for help, our instructor gave us a simple example to demonstrate what was happening.

If we have a simple tree that looks like:

 1 <=a2 3 <= b, c

Where 1, 2, and 3 are the values of each node and a, b, and c are the names of each node. If we’re trying to find the number “3,” and we called a.contains(3), the program would first check a to see if it was 3. It’s not, and 3 is greater than 1, so it’ll check c. c.contains(3) IS 3, so it would return true — except we never returned that value, so the program skips directly to the bottom and returns a.contains(3) instead (which is false!).

After a small adjustment in the form of adding return statements and a small lesson in recursion principles, we had a program that did exactly what we wanted it to!

BinarySearchTree.prototype.contains = function(value) {
if (value === this.value){
return true;
} else {
if (value < this.value) {
if (this.left === null) {
return false;
}
return this.left.contains(value);
} else {
if (this.right === null) {
return false;
}
return this.right.contains(value);
}
}
return false;
};

Here’s our tree again. We’ll use this in a second.

A binary tree can be searched in one of two main ways. The first is breadth-first, where you start at the first level, then go through all the nodes on the level beneath that, then all the nodes on the level beneath that, etc. This is useful when the tree level has some meaning (for example, a hierarchical org chart), but less useful for binary search trees. In our tree above, we’d get the values in the following order: 8, 3, 10, 1, 6, 14, 4, 7, 13.

We could do a breadth-first search in one of two ways, either iteratively or recursively. Whether it was because we were tired of recursion at this point or we just didn’t think to do it recursively (hint — it’s the latter), we did it iteratively with a queue.

Our iterator function was one that takes a value that is returned by the breadthFirstForEach function, and pushes it into an array.

BinarySearchTree.prototype.breadthFirstForEach = function(iterator, queue) {
queue = queue || [this];
var tree;
tree = queue.shift();
if (!tree) {
return undefined;
}
iterator(tree.value);
if (tree.left) {
queue.push(tree.left);
}
if (tree.right) {
queue.push(tree.right);
}
return tree.breadthFirstForEach(iterator, queue);
};

As long as our queue has length, we shift off the head of the queue, and run the iterator function (our array-pushing function) on that tree’s value. If the tree has a sub-tree to its left, we push it into the queue. Same thing for the right.

The other primary way to search a binary tree is depth-first, where you go down to certain stopping points before moving on to the next branch. The three types of depth-first search are:

  • Pre-order: process the current node value, then go down the left branch, then the right branch. Most useful in copying a tree. In our tree above, we’d get the values in the following order: 8, 3, 1, 6, 4, 7, 10, 14, 13.
  • In-order: process all left children, then this node’s value, then the right children. This is the most useful for a binary search tree, as values are processed from smallest to greatest. In our tree above, we’d get the values in the following order: 1, 3, 4, 6, 7, 8, 10, 13, 14.
  • Post-order: process all left children, then right children, then this node’s value. This is most useful to delete nodes in a safe way, because you’ve deleted the children before deleting the nodes above them. In our tree above, we’d get the values in the following order: 1, 4, 7, 6, 3, 13, 14, 10, 8.

Our group faced a lot of trouble implementing this at first: we weren’t able to wrap our minds around exactly how to get into each branch and recurse through them, and ended up with an enormous amount of if statements at one point. However, once we diagrammed each process out and realized that the recursion would be a simple matter of running the left and right branches through the function again, we were able to implement the following.

Our function takes an iterator function and an order, where the order is either pre-order, in-order, or post-order. Our iterator function is the same array-pushing function we had before.

BinarySearchTree.prototype.depthFirstForEach = function(iterator, order) {
if (order === 'pre-order') {
iterator(this.value);
}
if (this.left) {
this.left.depthFirstForEach(iterator, order);
}
if (!order || order === 'in-order') {
iterator(this.value);
}
if (this.right) {
this.right.depthFirstForEach(iterator, order);
}
if (order === 'post-order') {
iterator(this.value);
}
};

Essentially, most of the structure between these three are similar, which is why we’re able to combine them into one function. The only difference is the order in which the central “parent” node is processed — in pre-order, it’s first, in in-order, it’s between the left and the right, and in post-order, it’s last. We recurse through each left and right branch to ensure we get each node.

Hash Tables & Others

We also talked about hash tables, and our last problem in this set was implementing one. My partner and I didn’t quite get that far in the time that we had. There are also an incredibly large number of other abstract data types and data structures — things like graphs, red-black trees, circular buffers, heaps, the list goes on. I’m definitely interested in pursuing these on my own time (the little of it that exists nowadays), and I’ll report back!

Beth Qiang

Written by

Coder, runner, climber, adventurer, traveller, environmentalist, & animal lover. http://bethqiang.com/

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade