Data structures are a cornerstone of software engineering. I have come to really appreciate these. I mean, that is what we actually deal with - data, structured data, information. To visualise any of the structures below I would go to Visualgo.net or Object playground.
Queue
People don't queue in London so this may be a tough concept to grasp. People queue in the rest of the UK so they will understand this. Remember, if you "push in", you'll get "what for". A Queue is first in first out, so don't try and be clever, punk.
var Queue = function () {
this.size = 0;
this.data = {};
};
Queue.prototype.enqueue = function (value) {
this.data[this.size] = value;
this.size = this.size + 1;
};
Queue.prototype.dequeue = function () {
var i;
var count = 0;
var value;
if (this.size > 0) {
value = this.data[0];
delete this.data[0];
this.size--;
for (i in this.data) {
this.data[count] = this.data[i];
delete this.data[i];
count++;
}
}
return value;
};
Or, if you want to make use of Arrays:
class Queue {
constructor () {
this.queue = [];
}
enqueue (value) {
this.queue.push(value);
}
dequeue() {
return this.queue.shift();
}
}
Stack
A stack is a pile of things, like a stack of plates. The last one on that came on the stack will be the first one off the stack - FIFO - first on first off. An array is a kind of stack (I say "kind of" as an array is more flexible than a box standard stack.)
var Stack = function () {
this.size = 0;
this.data = {};
};
Stack.prototype.push = function (value) {
this.data[this.size] = value;
this.size = this.size + 1;
};
Stack.prototype.pop = function () {
var value = null;
if (this.size > 0) {
value = this.data[this.size - 1];
delete this.data[this.size];
this.size = this.size - 1;
}
return value;
};
Binary Tree
Lets say you had an analogue telephone book (haha I know!) and you wanted to find a number, not just any number, but someones land line (haha I know!). You could find that number in only a few steps. A binary tree is a similar thing. To find a number you open the book in half. If the name you are looking for is a letter greater than the one in the middle, then divide the right half of the book in two, and repeat until you find the name. This type of algorithm is a logarithm. It sounds musical, but it is purely mathematical. The "contains" function (below) complexity is O(Log(n)). The other functions are linear, which are O(n).
var BinaryTree = function (value) {
this.value = value;
this.left = null;
this.right = null;
};
BinaryTree.prototype.insert = function (value) {
if (value < this.value) {
this.left ? this.left.insert(value) : this.left = new BinaryTree(value);
} else{
this.right ? this.right.insert(value) : this.right = new BinaryTree(value);
}
};
BinaryTree.prototype.contains = function (value) {
var left = this.left ? this.left.contains(value) : false;
var right = this.right ? this.right.contains(value) : false;
return this.value === value || left || right;
};
BinaryTree.prototype.breadthFirst = function () {
var results = [];
var nodeList = [this];
while (nodeList.length > 0) {
results.push(nodeList[0].value);
if (nodeList[0].left) {
nodeList.push(nodeList[0].left);
}
if (nodeList[0].right) {
nodeList.push(nodeList[0].right);
}
nodeList.shift();
}
return results;
};
BinaryTree.prototype.depthFirst = function () {
var results = [];
if (this.left) {
results = results.concat(this.left.depthFirst());
}
results.push(this.value);
if (this.right) {
results = results.concat(this.right.depthFirst());
}
return results;
};
Brilliant implementation of a binary tree at Khan academy.
Linked List and Double Linked List
A linked list are good for, lists. A bit like arrays. They are made up of cells that have values, and a link to the next cell in line. A linked list has a top (or head), and a bottom (or tail). A double linked list has a link back to the previous cell. They can grow or shrink over time. With arrays, doing an operation like Array.splice is quite expensive, time wise. A linked list is a good alternative.
A list will look something like this:
{
value: bob, next : {
value: mark, next : {
value: jim, next : null
}
}
}
The linked list in JavaScript:
var LinkedList = function () {
this.head = null;
this.tail = null;
};
LinkedList.prototype.addToHead = function (value) {
var cell;
if (!this.head) {
this.head = new Cell(value);
this.tail = this.head;
} else {
cell = new Cell(value);
this.head.previous = cell;
cell.next = this.head;
this.head = cell;
}
};
LinkedList.prototype.addToTail = function (value) {
var cell;
if (!this.tail) {
this.tail = new Cell(value);
this.head = this.tail;
} else {
cell = new Cell(value);
this.tail.next = cell;
cell.previous = this.tail;
this.tail = cell;
}
};
LinkedList.prototype.insertAfter = function (key, value) {
var next = this.head;
var cell;
while (next) {
if (next.value === key) {
cell = new Cell(value);
cell.next = next.next;
cell.previous = next;
next.next = cell;
}
next = next.next;
}
};
LinkedList.prototype.removeHead = function () {
var result = null;
if (this.head) {
result = this.head.value;
this.head = this.head.next;
}
return result;
};
LinkedList.prototype.toArray = function () {
var results = [];
var next = this.head;
while (next) {
results.push(next.value);
next = next.next;
}
return results;
};
var Cell = function (value) {
this.value = value;
this.next = null;
this.previous = null;
};
Graph
No, not the type of thing you see in boring presentations stating that "yes we are really expanding" (yawn). However, it kind of is like that cos the definition is:
A collection of points who's coordinates satisfy a given relation
— The dictionary on my Mac :-)
So it is a number of "points", things that exist and that can be related to each other. Yeah, thats like pretty much all the other things covered here. Exactly. It just another form of data structure. It still is structured data. The totally amazing Object playground implements a graph as you can see on GitHub, amazing stuff.
var Graph = function () {
this._nodes = {};
}
Graph.prototype.addNode = function (node) {
this._nodes[node] = this._nodes[node] || { edges : {} };
}
Graph.prototype.removeNode = function (node) {
var targetNode;
node = this._nodes[node];
if (this.contains(node)) {
for (targetNode in node.edges) {
this.removeEdge(node, node.edges[targetNode]);
}
delete this._nodes[node];
}
}
Graph.prototype.contains = function (node) {
return this._nodes.hasOwnProperty(node);
}
Graph.prototype.addEdge = function (node1, node2) {
this._nodes[node1].edges[node2] = this._nodes[node2];
this._nodes[node2].edges[node1] = this._nodes[node1];
}
Graph.prototype.removeEdge = function (node1, node2) {
delete this._nodes[node1].edges[node2];
delete this._nodes[node2].edges[node1];
}
Graph.prototype.hasEdge = function (node1, node2) {
return this._nodes[node1].edges.hasOwnProperty(node2);
}
This is a great introduction to graphs.
Tree
A tree is exactly what it sounds like. A root with multiple branches, and possibly more branches on branches. The tree is similar to the binary tree, however a tree can have multiple children whereas binary trees just have two.
var Tree = function (value) {
this.value = value;
this.children = [];
};
Tree.prototype.addChild = function (value) {
this.children.push(new Tree(value));
};
Tree.prototype.contains = function (target) {
var found = this.value === target;
var i;
if (found) {
return found;
}
for (i = 0; i < this.children.length; i++) {
found = this.children[i].contains(target) || found;
}
return found;
};
Tree.prototype.traverse = function (callback) {
var i;
this.value = callback(this.value);
for (i = 0; i < this.children.length; i++) {
this.children[i].traverse(callback);
}
};
Set
A set is a collection of distinct things regarded as a unit. So with RIRO you may break the definition of set, but let's KISS.
function Set () {
this._storage = {};
}
Set.prototype.add = function (value) {
this._storage[value] = value;
}
Set.prototype.contains = function (value) {
return this._storage.hasOwnProperty(value);
}
Set.prototype.remove = function (value) {
delete this._storage[value];
}
Hash table
A hash is an extremely fast method of storing and retrieving data. It has the asymptotic behaviour of O(1). There are trade offs with disk space though.
var makeHashTable = function() {
var max = 4;
var _storage = {};
return {
retrieve: function(key) {
var i;
var genKey = hashFn(key, max);
var tuples = _storage[genKey] || [];
for (i = 0; i < tuples.length; i++) {
if (tuples[i][0] === key) {
return tuples[i][1];
}
}
return null;
},
insert: function(key, value) {
var i;
var genKey = hashFn(key, max);
var tuples = _storage[genKey] || [];
if (tuples.length === 0) {
tuples.push([key, value]);
_storage[genKey] = tuples;
} else {
for (i = 0; i < tuples.length; i++) {
if (tuples[i][0] === key) {
tuples[i][1] = value;
}
}
}
}
};
};
NB this assumes there is a "hashFn" function which would create hash keys
Other data structures
There are tonnes and tonnes of data structures, the ones above are great for beginners.
- Intermediate: Heap, Priority Queue, Huffman Tree, Union Find, Tries, Hash Table, Tree Map
- Proficient: Segment Tree, Binary Indexed Tree, Suffix Array, Sparse Table, Lowest Common Ancestor, Range Tree.
- Expert: Suffix Automaton, Suffix Tree, Heavy-Light Decomposition, Treap, Aho-Corasick, K-d tree, Link-Cut Tree, Splay Tree, Palindromic Tree, Rope, Dancing Links, Radix Tree, Dynamic Suffix Array.