Many of the students who do the front-end are self-taught or half-baked. The basic knowledge of computer is relatively weak, especially the data structure and algorithm. So today, I sorted out the common data structure and the corresponding implementation of Javascript, hoping to help you improve the knowledge system in this area.

1. Stack (stack)

Stack is characterized by last in first out. Common examples of Stack in life are a stack of books, the last one you put on will be taken away first, and the browser's access history, when you click the return button, the last website you visit pops up first from the history.

Stack generally has the following methods:

1. push: push an element onto the top of the stack
2. pop: Remove the top element of the stack and return the removed element
3. peek: Returns the top element of the stack
4. length: Returns the number of elements in the stack

Javascript Array naturally has Stack features, but we can also implement a Stack class from scratch:

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;
  }
}

2. Queue (queue)

Queue and Stack have some similarities, but Stack is first-in-first-out, while Queue is first-in-first-out. Queue examples in life, such as queuing for buses, are always the first to get on the bus; or printer queues, for example, are the first to print.

Queue generally has the following common methods:

1. enqueue: Entry, add an element to the end of the queue
2. dequeue: Out of the queue, removes an element from the head of the queue and returns the removed element
3. front: Gets the first element of the queue
4. isEmpty: Determine whether the queue is empty
5. size: Gets the number of elements in the queue

Array in Javascript already has some features of Queue, so we can implement a Queue type with Array:

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[0];
  }

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

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

Priority Queue

Queue also has an upgraded version that prioritizes each element, and high-priority elements are listed before low-priority elements. The main difference is the implementation of the enqueue method:

function PriorityQueue() {

  ...

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

Test it:

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 ]
]

3. Linked List

As the name implies, a linked list is a linked data structure. Each node in the chain contains two kinds of information: the data of the node itself and the pointer to the next node. Link lists and traditional arrays are linear data structures, which store data in a sequence, but there are many differences, as follows:

Comparative dimension	array	linked list
memory allocation	Static memory allocation, compile-time allocation and continuity	Dynamic memory allocation, runtime allocation and discontinuity
Element acquisition	Obtained through Index, faster	Through traversal sequential access, the speed is slower
Add and delete elements	Because the memory location is continuous and fixed, the speed is slow.	Because memory allocation is flexible, there is only one overhead step, which is faster.
space structure	It can be one-dimensional or multi-dimensional arrays.	It can be a one-way, two-way or circular list.

A one-way list usually has the following methods:

1. size: Number of nodes returned to the list
2. head: Returns the header element in the list
3. add: add a node to the end of the list
4. remove: Delete a node
5. indexOf: Returns the index of a node
6. elementAt: Returns a node at an index
7. addAt: Insert a node at an index
8. removeAt: Delete a node at an index

Javascript implementation of one-way linked list:

/**
 * Nodes in the linked list 
 */
function Node(element) {
  // Data in nodes
  this.element = element;
  // Pointer to the next node
  this.next = null;
}

function LinkedList() {
  var length = 0;
  var head = null;

  this.size = function () {
    return length;
  }

  this.head = function () {
    return head;
  }

  this.add = function (element) {
    var node = new Node(element);
    if (head == null) {
      head = node;
    } else {
      var currentNode = head;

      while (currentNode.next) {
        currentNode = currentNode.next;
      }

      currentNode.next = node;
    }
    length++;
  }

  this.remove = function (element) {
    var currentNode = head;
    var previousNode;
    if (currentNode.element === element) {
      head = currentNode.next;
    } 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 currentNode = head;
    var index = -1;
    while (currentNode) {
      index++;
      if (currentNode.element === element) {
        return index;
      }
      currentNode = currentNode.next;
    }

    return -1;
  }

  this.elementAt = function (index) {
    var currentNode = head;
    var count = 0;
    while (count < index) {
      count++;
      currentNode = currentNode.next;
    }
    return currentNode.element;
  }

  this.addAt = function (index, element) {
    var node = new Node(element);
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;

    if (index > length) {
      return false;
    }

    if (index === 0) {
      node.next = currentNode;
      head = node;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      node.next = currentNode;
      previousNode.next = node;
    }
    length++;
  }

  this.removeAt = function (index) {
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;
    if (index < 0 || index >= length) {
      return null;
    }
    if (index === 0) {
      head = currentIndex.next;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
    return currentNode.element;
  }
}

4. Set (collection)

Set is a basic concept in mathematics, which represents the collective of objects with certain characteristics. Set is also introduced in ES6. Set and Array are similar to each other to some extent. The difference is that there are no duplicate elements in Set and they are disorderly.

A typical Set should have the following methods:

1. values: Returns all elements in the collection
2. size: Returns the number of elements in a collection
3. has: Determines whether an element exists in a collection
4. add: Adding elements to a collection
5. remove: remove an element from a collection
6. Union: Returns the union of two sets
7. Intersection: Returns the intersection of two sets
8. Difference: Returns the difference set of two sets
9. Subset: Determines whether a set is a subset of another set

Set can be implemented using Javascript as follows, in order to distinguish it from Set in ES6, which is named MySet:

function MySet() {
  var collection = [];
  this.has = function (element) {
    return (collection.indexOf(element) !== -1);
  }

  this.values = function () {
    return collection;
  }

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

  this.add = function (element) {
    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) {
      unionSet.add(e);
    });
    secondSet.forEach(function (e) {
      unionSet.add(e);
    });
    return unionSet;
  }

  this.intersection = function (otherSet) {
    var intersectionSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {
      if (otherSet.has(e)) {
        intersectionSet.add(e);
      }
    });
    return intersectionSet;
  }

  this.difference = function (otherSet) {
    var differenceSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {
      if (!otherSet.has(e)) {
        differenceSet.add(e);
      }
    });
    return differenceSet;
  }

  this.subset = function (otherSet) {
    var firstSet = this.values();
    return firstSet.every(function (value) {
      return otherSet.has(value);
    });
  }
}

5. Hash Table (hash table/hash table)

Hash Table is a data structure used to store key value pair s. Because Hash Table queries value quickly according to key, it is often used to implement Map, Dictinary, Object and other data structures. As shown in the figure above, Hash Table uses a hash function to convert the incoming key into a series of numbers, which will be used as the key value to the actual key. By querying the corresponding value through this key, the time complexity will reach O(1). The Hash function requires that the output corresponding to the same input must be equal, while the output corresponding to the different input must be different, which is equivalent to a unique fingerprint on each pair of data.

A Hash Table usually has the following methods:

1. add: Increase a set of key-value pairs
2. remove: Delete a set of key-value pairs
3. lookup: Find a key value

A simple version of Hastable's Javascript implementation:

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][0] === key) {
          storage[index][i][1] = 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][0][0] === key) {
      delete storage[index];
    } else {
      for (var i = 0; i < storage[index]; i++) {
        if (storage[index][i][0] === 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][0] === key) {
          return storage[index][i][1];
        }
      }
    }
  }
}

6. Tree (Tree)

As the name implies, Tree's data structure is very similar to that of trees in nature, with roots, branches and leaves, as shown in the figure above. Tree is a multi-layer data structure. Compared with Array, Stack and Queue, Tree is a non-linear data structure. It is very efficient in insertion and search operations. The following concepts are often used in describing a Tree:

1. Root: Represents the root node of the tree. The root node has no parent node.
2. Parent Node: A direct parent of a node, with only one parent.
3. Child Node: A direct subordinate node of a node that may have more than one
4. Siblings: Nodes with the same parent
5. Leaf (leaf node): Node without child node
6. Edge (Edge): Connection between two nodes
7. Path: Continuous edges from the source node to the target node
8. Height of Node: Represents the number of upper edges of the longest path between nodes and leaf nodes
9. Height of Tree: The height of the root node
10. Depth of Node: Represents the number of edges from the root node to the node
11. Degree of Node: Represents the number of subnodes

We take the binary search tree as an example to show the implementation of the tree in Javascript. In binary lookup tree, each node has at most two sub-nodes, while the left sub-node is smaller than the current node, while the right sub-node is larger than the current node, as shown in the figure:

A binary search tree should have the following common methods:

1. add: Insert a node into the tree
2. findMin: Find the smallest node in the tree
3. findMax: Find the largest node in the tree
4. find: find a node in the tree
5. isPresent: Determines whether a node exists in the tree
6. remove: remove a node from the tree

The following is the Javascript implementation of the binary lookup tree:

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

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

  add(data) {
    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) {
        // node has no child nodes
        if (node.left == null && node.right == null) {
          return null;
        }
        // node has no left child nodes
        if (node.left == null) {
          return node.right;
        }
        // node has no right subnode
        if (node.right == null) {
          return node.left;
        }
        // node has two subnodes
        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);
  }
}

Test it:

const bst = new BST();

bst.add(4);
bst.add(2);
bst.add(6);
bst.add(1);
bst.add(3);
bst.add(5);
bst.add(7);
bst.remove(4);
console.log(bst.findMin());
console.log(bst.findMax());
bst.remove(7);
console.log(bst.findMax());
console.log(bst.isPresent(4));

Print results:

1
7
6
false

7. Trie

Trie can also be called Prefix Tree, which is also a search tree. Trie stores data step by step. Each node in the tree represents a step. Trie is often used to store words for quick search, such as the automatic completion of words. Each node in Trie contains a letter of a word. Following the branch of the tree, a complete word can be spelled out. Each node also contains a Boolean value indicating whether the node is the last letter of the word.

Trie generally has the following methods:

1. add: add a word to the dictionary tree
2. isWord: Determine whether a word is included in the dictionary tree
3. print: Returns all words in the dictionary tree

/**
 * Trie Nodes
 */
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[0])) {
      node.keys.set(input[0], new Node());
      return this.add(input.substr(1), node.keys.get(input[0]));
    } else {
      return this.add(input.substr(1), node.keys.get(input[0]));
    }
  }

  this.isWord = function (word) {
    let node = this.root;
    while (word.length > 1) {
      if (!node.keys.has(word[0])) {
        return false;
      } else {
        node = node.keys.get(word[0]);
        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;
  }
}

8. Graph (figure)

Graph is a collection of nodes (or vertices) and connections (or edges) between them. Graph can also be called the Network. Directed Graph (directed graph) and Undrected Graph (undirected graph) can be classified according to the direction of the connection between nodes. Graph has many uses in real life, such as: navigation software calculating the best path, social software recommending friends and so on.

Graph is usually expressed in two ways:

Adjaceny List (Adjaceny List):

The adjacency list can be represented as a list of nodes on the left and all other nodes connected to it on the right.

And Adjacency Matrix (Adjacency Matrix):

Adjacency matrix uses matrix to represent the connection relationship between nodes. Each row or column represents a node. The number at the intersection of rows and columns represents the relationship between nodes: 0 indicates no connection, 1 indicates connection, and greater than 1 indicates different weights.

The traversal algorithm is used to access the nodes in Graph. The traversal algorithm is divided into breadth-first and depth-first. It is mainly used to determine the distance between the target node and the root node.

In Javascript, Graph can be represented by a matrix (two-dimensional array). The breadth-first search algorithm can be implemented as follows:

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;
}

Test it:

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));

Print:

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

The purpose of this paper is to popularize common data structures to front-end students. I only have a glimpse of this field, and welcome to point out where there is a gap. I also hope that you can lay a solid foundation and go higher and farther on this road!