Are you looking to improve your fundamental knowledge of computer science, especially data structure and algorithms? Then you’re in the right place. Let’s go through some common data structures and implement them in JavaScript.

1. Stack
2. Queue
4. Set
5. Hash Table
6. Tree
7. Trie
8. Graph

## 1. Stack

Stack follows the principle of LIFO (last In, first out). If you stack books, the top book will be taken before the bottom one. When you browse on the internet, the back button leads you to the most recently browsed page.

## Common Methods of Stack in JavaScript

• push: Input a new element.
• pop : Remove the top element, return the removed element.
• peek : Return the top element.
• length : Return the number of element(s) in the stack.

Array in JavaScript has the attributes of a stack, but we construct a stack from scratch by using `function Stack()`.

``````function Stack() {
this.count = 0;
this.storage = {};

this.push = function (value) {
this.storage[this.count] = value;
this.count++;
}

this.pop = function () {
if (this.count === 0) {
return undefined;
}
this.count--;
var result = this.storage[this.count];
delete this.storage[this.count];
return result;
}

this.peek = function () {
return this.storage[this.count - 1];
}

this.size = function () {
return this.count;
}
}``````

More From Built In Software ExpertsCreate React App and TypeScript — A Quick How-To

## 2. Queue

Queue is similar to stack. The only difference is that queue uses the FIFO principle (first in, first out). In other words, when you queue for the bus, the first in the queue will always board first.

## Queue Methods in JavaScript

• enqueue: Enter queue, add an element at the end.
• dequeue: Leave queue, remove the front element and return it.
• front: Get the first element.
• isEmpty: Determine whether the queue is empty.
• size: Get the number of element(s) in queue.

Array in JavaScript has some attributes of queue, so we can use array to construct an example for queue:

``````function Queue() {
var collection = [];
this.print = function () {
console.log(collection);
}
this.enqueue = function (element) {
collection.push(element);
}
this.dequeue = function () {
return collection.shift();
}
this.front = function () {
return collection;
}

this.isEmpty = function () {
return collection.length === 0;
}
this.size = function () {
return collection.length;
}
}``````

### Priority Queue

Queue has another advanced version. Allocate each element by priority and it will be sorted according to the priority level:

``````function PriorityQueue() {

...

this.enqueue = function (element) {
if (this.isEmpty()) {
collection.push(element);
} else {
for (var i = 0; i < collection.length; i++) {
if (element < collection[i]) {
collection.splice(i, 0, element);
break;
}
}
collection.push(element);
}
}
}
}``````

Testing it out:

``````var pQ = new PriorityQueue();
pQ.enqueue([ gannicus , 3]);
pQ.enqueue([ spartacus , 1]);
pQ.enqueue([ crixus , 2]);
pQ.enqueue([ oenomaus , 4]);
pQ.print();``````

Result:

``````[
[  spartacus , 1 ],
[  crixus , 2 ],
[  gannicus , 3 ],
[  oenomaus , 4 ]
]``````

A linked list is a chained data structure. Each node consists of two pieces of information: the data of the node and the pointer to the next node. Linked list and conventional array are both linear data structures with serialized storage. Of course, they also have differences:

A unilateral linked list normally has following methods:

• size: Return the number of node(s).
• remove: Remove a certain node.
• indexOf: Return the index of a node.
• elementAt: Return the node of an index.
• addAt: Insert a node at a specific index.
• removeAt: Delete a node at a specific index.
``````/** Node in the linked list **/
function Node(element) {
// Data in the node
this.element = element;
// Pointer to the next node
this.next = null;
}
var length = 0;
this.size = function () {
return length;
}
}
var node = new Node(element);
} else {
while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
length++;
}
this.remove = function (element) {
var previousNode;
if (currentNode.element === element) {
} else {
while (currentNode.element !== element) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
length--;
}
this.isEmpty = function () {
return length === 0;
}
this.indexOf = function (element) {
var index = -1;
while (currentNode) {
index++;
if (currentNode.element === element) {
return index;
}
currentNode = currentNode.next;
}
return -1;
}
this.elementAt = function (index) {
var count = 0;
while (count < index) {
count++;
currentNode = currentNode.next;
}
return currentNode.element;
}
this.addAt = function (index, element) {
var node = new Node(element);
var previousNode;
var currentIndex = 0;
if (index > length) {
return false;
}
if (index === 0) {
node.next = currentNode;
} else {
while (currentIndex < index) {
currentIndex++;
previousNode = currentNode;
currentNode = currentNode.next;
}
node.next = currentNode;
previousNode.next = node;
}
length++;
}
this.removeAt = function (index) {
var previousNode;
var currentIndex = 0;
if (index < 0 || index >= length) {
return null;
}
if (index === 0) {
} else {
while (currentIndex < index) {
currentIndex++;
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
length--;
return currentNode.element;
}
}``````

## 4. Set

A set is a basic concept in mathematics: a collection of well defined and distinct objects. ES6 introduced the concept of set, which has some similarities to  an array. However, a set does not allow repeating elements and is not indexed.

## Typical Set Methods in JavaScript

• values: Return all elements in a set.
• size: Return the number of elements.
• has: Determine whether an element exists.
• add: Insert elements into a set.
• remove: Delete elements from a set.
• union: Return the intersection of two sets.
• difference: Return the difference of two sets.
• subset: Determine whether a certain set is a subset of another set.

To differentiate set in ES6, we declare as `MySet` in the following example:

``````function MySet() {
var collection = [];
this.has = function (element) {
return (collection.indexOf(element) !== -1);
}
this.values = function () {
return collection;
}
this.size = function () {
return collection.length;
}
if (!this.has(element)) {
collection.push(element);
return true;
}
return false;
}
this.remove = function (element) {
if (this.has(element)) {
index = collection.indexOf(element);
collection.splice(index, 1);
return true;
}
return false;
}
this.union = function (otherSet) {
var unionSet = new MySet();
var firstSet = this.values();
var secondSet = otherSet.values();
firstSet.forEach(function (e) {
});
secondSet.forEach(function (e) {
});
return unionSet;  }
this.intersection = function (otherSet) {
var intersectionSet = new MySet();
var firstSet = this.values();
firstSet.forEach(function (e) {
if (otherSet.has(e)) {
}
});
return intersectionSet;
}
this.difference = function (otherSet) {
var differenceSet = new MySet();
var firstSet = this.values();
firstSet.forEach(function (e) {
if (!otherSet.has(e)) {
}
});
return differenceSet;
}
this.subset = function (otherSet) {
var firstSet = this.values();
return firstSet.every(function (value) {
return otherSet.has(value);
});
}
}``````

More From Built In JavaScript Experts5 Ways to Check If an Object Is Empty in JavaScript

## 5. Hash Table

A hash table is a key-value data structure. Due to the lightning speed of querying a value through a key, hash tables are commonly used in map, dictionary or object data structures. As shown in the graph above, the hash table uses a hash function to convert keys into a list of numbers, and these numbers serve as the values of corresponding keys. To get value using a key is fast; time complexity can achieve `O(1)`. The same keys must return the same values, which is the basis of the hash function.

## Hash Table Methods in JavaScript

• remove: Delete a key-value pair.
• lookup: Find a corresponding value using a key.

An example of a simplified hash table in JavaScript:

``````function hash(string, max) {
var hash = 0;
for (var i = 0; i < string.length; i++) {
hash += string.charCodeAt(i);
}
return hash % max;
}

function HashTable() {
let storage = [];
const storageLimit = 4;

this.add = function (key, value) {
var index = hash(key, storageLimit);
if (storage[index] === undefined) {
storage[index] = [
[key, value]
];
} else {
var inserted = false;
for (var i = 0; i < storage[index].length; i++) {
if (storage[index][i] === key) {
storage[index][i] = value;
inserted = true;
}
}
if (inserted === false) {
storage[index].push([key, value]);
}
}
}

this.remove = function (key) {
var index = hash(key, storageLimit);
if (storage[index].length === 1 && storage[index] === key) {
delete storage[index];
} else {
for (var i = 0; i < storage[index]; i++) {
if (storage[index][i] === key) {
delete storage[index][i];
}
}
}
}

this.lookup = function (key) {
var index = hash(key, storageLimit);
if (storage[index] === undefined) {
return undefined;
} else {
for (var i = 0; i < storage[index].length; i++) {
if (storage[index][i] === key) {
return storage[index][i];
}
}
}
}
}``````

Dive Deeper and Up Your SkillsSoftware Engineering Learning Lab on Built In

## 6. Tree

Tree data structure is a non-linear multi-layer data structure in contrast to array, stack and queue. This structure is highly efficient during insert and search operations. Let’s take a look at some concepts of tree data structure:

## Tree Data Structure Concepts

• root: Root node of a tree; no parent node for root.
• parent node: Direct node of the upper layer; only has one
• child node: Direct node(s) of the lower layer; can have multiple
• siblings: Share the same parent node
• leaf: Node with no child
• Edge: Branch or link between nodes
• Path: The edges from a starting node to the target node
• Height of Node: Number of edges of the longest path of a specific node to leaf node
• Height of Tree: Number of edges of the longest path of the root node to the leaf node
• Depth of Node: Number of edges from root node to specific node
• Degree of Node: Number of child nodes

Here’s an example of a binary search tree here. Each node has a maximum of two nodes with the left node being smaller than the current node and the right node being bigger than the current node.

## Common Methods of Binary Search Tree in JavaScript

• add: Insert a node into the tree.
• findMin: Get the minimum node.
• findMax: Get the maximum node.
• find: Search a specific node.
• isPresent: Determine the existence of a certain node.
• remove: Delete a node from the tree.

Example in JavaScript:

``````class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}

class BST {
constructor() {
this.root = null;
}

const node = this.root;
if (node === null) {
this.root = new Node(data);
return;
} else {
const searchTree = function (node) {
if (data < node.data) {
if (node.left === null) {
node.left = new Node(data);
return;
} else if (node.left !== null) {
return searchTree(node.left);
}
} else if (data > node.data) {
if (node.right === null) {
node.right = new Node(data);
return;
} else if (node.right !== null) {
return searchTree(node.right);
}
} else {
return null;
}
};
return searchTree(node);
}
}

findMin() {
let current = this.root;
while (current.left !== null) {
current = current.left;
}
return current.data;
}

findMax() {
let current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.data;
}

find(data) {
let current = this.root;
while (current.data !== data) {
if (data < current.data) {
current = current.left
} else {
current = current.right;
}
if (current === null) {
return null;
}
}
return current;
}

isPresent(data) {
let current = this.root;
while (current) {
if (data === current.data) {
return true;
}
if (data < current.data) {
current = current.left;
} else {
current = current.right;
}
}
return false;
}

remove(data) {
const removeNode = function (node, data) {
if (node == null) {
return null;
}
if (data == node.data) {
// no child node
if (node.left == null && node.right == null) {
return null;
}
// no left node
if (node.left == null) {
return node.right;
}
// no right node
if (node.right == null) {
return node.left;
}
// has 2 child nodes
var tempNode = node.right;
while (tempNode.left !== null) {
tempNode = tempNode.left;
}
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.data);
return node;
} else if (data < node.data) {
node.left = removeNode(node.left, data);
return node;
} else {
node.right = removeNode(node.right, data);
return node;
}
}
this.root = removeNode(this.root, data);
}
}``````

Testing it out:

``````const bst = new BST();
bst.remove(4);
console.log(bst.findMin());
console.log(bst.findMax());
bst.remove(7);
console.log(bst.findMax());
console.log(bst.isPresent(4));``````

Result:

``````1
7
6
false``````

Related ReadingHow to Get Started With Social Network Analysis

## 7. Trie

Trie (pronounced “try”) or “prefix tree” is also a type of search tree. Trie stores the data step-by-step; each node in the tree represents a step. We use trie to store vocabulary so it can be quickly searched, especially for an auto-complete function.

Each node in trie has an alphabet and following the branch can form a complete word. It also comprises a boolean indicator to show whether or not it’s the end of a string.

## Methods of Trie in JavaScript

• add: Insert a word into the dictionary tree.
• isWord: Determine whether the tree consists of a certain word.
• print: Return all words in the tree.
``````/** Node in Trie **/
function Node() {
this.keys = new Map();
this.end = false;
this.setEnd = function () {
this.end = true;
};
this.isEnd = function () {
return this.end;
}
}

function Trie() {
this.root = new Node();
this.add = function (input, node = this.root) {
if (input.length === 0) {
node.setEnd();
return;
} else if (!node.keys.has(input)) {
node.keys.set(input, new Node());
} else {
}
}
this.isWord = function (word) {
let node = this.root;
while (word.length > 1) {
if (!node.keys.has(word)) {
return false;
} else {
node = node.keys.get(word);
word = word.substr(1);
}
}
return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
}
this.print = function () {
let words = new Array();
let search = function (node = this.root, string) {
if (node.keys.size != 0) {
for (let letter of node.keys.keys()) {
search(node.keys.get(letter), string.concat(letter));
}
if (node.isEnd()) {
words.push(string);
}
} else {
string.length > 0 ? words.push(string) : undefined;
return;
}
};
search(this.root, new String());
return words.length > 0 ? words : null;
}
}``````

More Software Engineering Tutorials on Built InWhat Is the @ Symbol in Python and How Do I Use It?

## 8. Graph

Graphs, sometimes known as networks, refer to sets of nodes with linkages (or edges). We can further divide graphs into two groups (i.e. directed graphs and undirected graphs), according to whether the linkages have direction. We use graphs in our daily lives without even realizing it. Graphs help calculate the best route in navigation apps or recommend friends with whom we might like to connect. Adjacency matrix shows nodes in rows and columns. Intersections of the row and column interpret the relationship between nodes: `0` means not linked, `1` means linked and `>1` means different weightage.

To query for nodes in a graph, one must search through the entire tree network with either the breadth-first-search (BFS) method or the depth-first-search (DFS) method.

Let’s see an example of BFS in Javascript:

``````function bfs(graph, root) {
var nodesLen = {};
for (var i = 0; i < graph.length; i++) {
nodesLen[i] = Infinity;
}
nodesLen[root] = 0;
var queue = [root];
var current;
while (queue.length != 0) {
current = queue.shift();

var curConnected = graph[current];
var neighborIdx = [];
var idx = curConnected.indexOf(1);
while (idx != -1) {
neighborIdx.push(idx);
idx = curConnected.indexOf(1, idx + 1);
}
for (var j = 0; j < neighborIdx.length; j++) {
if (nodesLen[neighborIdx[j]] == Infinity) {
nodesLen[neighborIdx[j]] = nodesLen[current] + 1;
queue.push(neighborIdx[j]);
}
}
}
return nodesLen;
}``````

Testing it out:

``````var graph = [
[0, 1, 1, 1, 0],
[0, 0, 1, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0]
];
console.log(bfs(graph, 1));``````

Result:

``````{
0: 2,
1: 0,
2: 1,
3: 3,
4: Infinity
}``````

That’s it — we’ve covered all the common data structures and seen examples in JavaScript. This should give you a better picture of how data structures work. Happy coding!

Expert Contributors

Built In’s expert contributor network publishes thoughtful, solutions-oriented stories written by innovative tech professionals. It is the tech industry’s definitive destination for sharing compelling, first-person accounts of problem-solving on the road to innovation.