Sports (stack)
A stack is a come-in, come-out data structure, such as a browser history
Array in JS already implements all functions of stack
Example: Check whether a palindrome string exists
let letters = [] / / stack
let word = 'racecar'
let rword = ' '
for(let i = 0; i < word.length; i++) {
letters.push(word[i])
}
for(let i = 0; i < word.length; i++) {
rword += letters.pop()
}
if (word === rword) {
console.log(`${word}Is a palindrome string ')}Copy the codeSimple simulation stack implementation
class Stack {
count = 0
storage = {}
// Push the data in
push(value) {
this.storage[this.count] = value;
this.count++;
}
// Push out the last pushed data
pop() {
if (this.count === 0) {
return undefined;
}
this.count--;
const result = this.storage[this.count];
delete this.storage[this.count]
return result;
}
// The number of elements in the stack
size() {
return this.count;
}
// Look at the last element in the stack
peek() {
return this.storage[this.count - 1]; }}Copy the codeTesting:
let myStack = new Stack();
myStack.push(1);
myStack.push(2);
console.log(myStack.peek())
console.log(myStack.pop())
console.log(myStack.peek())
myStack.push('abcd')
console.log(myStack.size())
console.log(myStack.peek())
console.log(myStack.pop())
console.log(myStack.peek())
Copy the codeSet
Elements in a Set are never repeated and are not ordered
ES6 already supports Set natively
Simple simulation of the implementation of Set
class MySet { // Different from native Set
collection = []
has(element) {
return this.collection.indexOf(element) ! = = -1
}
values() {
return this.collection
}
add(element) {
if (!this.has(element)) {
this.collection.push(element);
return true;
}
return false;
}
remove(element) {
if (this.has(element)) {
const index = this.collection.indexOf(element);
this.collection.splice(index, 1);
return true;
}
return false;
}
size() {
return this.collection.length
}
// Return the union of 2 sets
union(otherSet) {
let unionSet = new MySet();
let firstSet = this.values()
let secondSet = otherSet.values()
firstSet.forEach((e) = > unionSet.add(e))
secondSet.forEach((e) = > unionSet.add(e))
return unionSet
}
// Returns the intersection of two sets
intersection(otherSet) {
let intersectionSet = new MySet();
let firstSet = this.values()
firstSet.forEach((e) = > {
if (otherSet.has(e)) {
intersectionSet.add(e)
}
})
return intersectionSet
}
// Return a new Set whose elements are in the current Set but not in the otherSet
difference(otherSet) {
let differenceSet = new MySet();
let firstSet = this.values()
firstSet.forEach((e) = > {
if(! otherSet.has(e)) { differenceSet.add(e) } })return differenceSet
}
// Check whether the current Set is a subset of otherSet
subset(otherSet) {
let firstSet = this.values()
return firstSet.every(value= > {
return otherSet.has(value)
})
}
}
Copy the codetest
let setA = new MySet();
let setB = new MySet();
setA.add('a')
setB.add('b')
setB.add('c')
setB.add('a')
setB.add('d')
console.log(setA.subset(setB))
console.log(setA.intersection(setB).values())
Copy the codeThe Queue (Queue)
First in, first out, like waiting in line
JS can also implement queues with arrays, but if you want to be more precise, you have to implement it yourself
class Queue {
collection = []
print() {
console.log(this.collection)
}
// Push the element to the end of the queue
enqueue(element) {
this.collection.push(element)
}
// Push the first element out of the queue and return the pushed element
dequeue() {
return this.collection.shift()
}
front() {
return this.collection[0]}size() {
return this.collection.length
}
isEmpty() {
return this.collection === 0}}Copy the codetest
let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.print()
queue.dequeue()
queue.front()
queue.print()
Copy the codePriorityQueue
In addition to passing in elements, we also need to pass in the corresponding priority:
If all elements have the same priority, it is the same as a normal queue; But if not, the higher-priority element is inserted at the beginning of the queue
class PriorityQueue extends Queue {
enqueue(element) {
const { collection } = this;
if (this.isEmpty()) {
collection.push(element)
} else {
let added = false;
for(let i = 0; i < collection.length; i++) {
if (element[i] < collection[i][1]) {
collection.splice(i, 0, element)
added = true;
break; }}if(! added) { collection.push(element) } } }dequeue() {
const value = this.collection.shift()
return value[0]}}Copy the codetest
const pq = new PriorityQueue();
pq.enqueue(['bbb'.2])
pq.enqueue(['ccc'.3])
pq.enqueue(['aaa'.1])
pq.print()
pq.dequeue()
pq.front()
pq.print()
Copy the codeBinary Search Tree
The data stored in A tree looks like A tree in nature. The following is A graphical representation of the tree, in which the circle storing data is called the node, the topmost node A is called the root node, and the leaf node refers to the end of the tree, and there must be no child nodes.
There are many types of trees, and we’ll introduce one of them: binary search trees.
In theory, a tree can have any number of branches. For example, C node in the figure above has F, G and H child nodes, while a binary tree has only two branches. The following figure is a binary tree, where each node has only two branches:
Binary tree is an ordered data structure, each left child node must be smaller than the parent node, and each right child node must be larger than the parent node (generally not equal to). Because of this feature, the search times can always be halved, so the time complexity of this algorithm’s insert/delete (essentially search) is: O(logn), which is much better than linear complexity (traversal), but slower than hash.
Let’s look at the implementation of JS:
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 = (node) = > {
if (data < node.data) {
if (node.left === null) {
node.left = new Node(data)
return
} else {
return searchTree(node.left)
}
} else if (data > node.data) {
if (node.right === null) {
node.right = new Node(data)
return
} else {
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
}
// Whether to include the data
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 = (node, data) = > {
if (node === null) {
return null;
}
if (data === node.data) {
// There are no child nodes
if (node.left === null && node.right === null) {
return null
}
// There is no left child
if (node.left === null) {
return node.right
}
// No right child node
if (node.right === null) {
return node.left
}
// Both left and right child nodes exist
// If you want to remove 3 nodes, replace it with the left-most node (4) of the right node of 3
let 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)
returnnode; }}// The root node and the data to delete are passed in
this.root = removeNode(this.root, data)
}
}
Copy the code
test
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))
Copy the codeTraversal and height of binary search trees
The height of BST is the distance between the root node and a leaf node. For example, in the figure below, the height with respect to 9, 9 is 0, while the height of 4 and 17 nodes is 1, 5, 7, and 20 is 3.
There must be a minimum height and a maximum height for any BST, if the maximum height – minimum height is not greater than 1, then THE BST is balanced.
As shown in the figure above, the minimum height of this BST is the height 1 from the root node to the first (without two child nodes) leaf node 17, and the maximum height is the height from the root node to any bottommost (without child nodes) leaf node. Obviously the maximum height of this BST is 3, so the tree is unbalanced. The reason this tree is unbalanced is that 17 is missing a left node.
If we add a 10 node (the left node of 17), then the minimum height is 2 and the maximum height is 3, the tree is balanced.
Why tree balance? Because the query efficiency of the balanced tree is higher, the expansion is not done here
We can implement a BST that automatically balances itself when adding or deleting nodes, which will improve the efficiency of BST queries
JS implement binary search tree traversal and height:
class THBST extends BST {
// Whether it is balanced
isBalanced() {
return this.findMinHeight() >= this.findMaxHeight() - 1
}
// Minimum height
findMinHeight(node = this.root) {
if (node === null) {
return -1
}
// Left and right must return -1 at the end
let left = this.findMinHeight(node.left)
let right = this.findMinHeight(node.right)
If the minimum height of the left tree is small, then the minimum height of the whole tree is the minimum height of the left tree +1
if (left < right) {
return left + 1
} else { Otherwise, the minimum height of the whole tree is the minimum height of the right tree +1
return right + 1}}// Maximum height
findMaxHeight(node = this.root) {
if (node === null) {
return -1
}
let left = this.findMaxHeight(node.left)
let right = this.findMaxHeight(node.right)
if (left > right) {
return left + 1
} else {
return right + 1}}// Sequential traversal: start from the left-most node (in order of size) to the right-most node
inOrder() {
if (this.root === null) {
return null;
} else {
let result = [];
function traverseInOrder(node) {
node.left && traverseInOrder(node.left)
result.push(node.data)
node.right && traverseInOrder(node.right)
}
traverseInOrder(this.root)
returnresult; }}// Start from the root node, depth first traversal (first traversal the root node, then extend to the leaf node)
preOrder() {
if (this.root === null) {
return null;
} else {
let result = [];
function traversePreOrder(node) {
result.push(node.data)
node.left && traversePreOrder(node.left)
node.right && traversePreOrder(node.right)
}
traversePreOrder(this.root)
returnresult; }}// The root node is traversed from the left to the left (first to the left, then to the right)
postOrder() {
if (this.root === null) {
return null;
} else {
let result = [];
function traversePostOrder(node) {
node.left && traversePostOrder(node.left)
node.right && traversePostOrder(node.right)
result.push(node.data)
}
traversePostOrder(this.root)
returnresult; }}// Level traversal: breadth-first search, traversal the elements of this level before looking for the next level
levelOrder() {
let result = []
let queue = []
if (this.root ! = =null) {
queue.push(this.root)
while(queue.length > 0) {
let node = queue.shift()
result.push(node.data)
if(node.left ! = =null) {
queue.push(node.left)
}
if(node.right ! = =null) {
queue.push(node.right)
}
}
return result;
} else {
return null; }}}Copy the codeConstruct the data and test it as shown below:
const thbst = new THBST()
thbst.add(9)
thbst.add(4)
thbst.add(17)
thbst.add(3)
thbst.add(6)
thbst.add(21)
thbst.add(5)
thbst.add(7)
thbst.add(20)
console.log(thbst.findMinHeight())
console.log(thbst.findMaxHeight())
console.log(thbst.isBalanced())
thbst.add(10)
console.log(thbst.findMinHeight())
console.log(thbst.findMaxHeight())
console.log(thbst.isBalanced())
console.log(thbst.inOrder()) // [3, 4, 5, 6, 7, 9, 10, 17, 20, 21]
console.log(thbst.preOrder()) // [9, 4, 3, 6, 5, 7, 17, 10, 21, 20]
console.log(thbst.postOrder()) // [3, 5, 7, 6, 4, 10, 20, 21, 17, 9]
console.log(thbst.levelOrder()) // [9, 4, 17, 3, 6, 10, 21, 5, 7, 20]
Copy the codeHash Tables
Hash table is a data structure used to implement associative array or key-value pair mapping. Because of its high efficiency, it is often used to implement data structures such as Map and Object.
The average complexity of each (find, insert, delete) operation is independent of the number of elements in the hash table, and the time complexity is O (1), so it is very fast.
Most development languages have this functionality natively. For example, JavaScript object is an implementation of the hash table. Here are the details:
// Generate an index
function hash(str, max) {
let hash = 0
for(let i = 0; i < str.length; i++) {
hash += str.charCodeAt(i)
}
return hash % max;
}
class HashTable {
constructor(limit) {
this.storage = []
this.limit = limit
}
print() {
console.log(this.storage)
}
add(key, value) {
const { storage } = this
// Call the hash function to get the index in the hash table that stores the value
let index = hash(key, this.limit)
if (storage[index] === undefined) {
storage[index] = [ [key, value] ]
} else {
let inserted = false;
for(let i = 0; i < storage[index][length]; i++) {
if (storage[index][i][0] === key) { / / update
storage[index][i][1] = value
inserted = true}}if (inserted === false) { / / add
storage[index].push([ key, value ])
}
}
}
remove(key) {
const { storage } = this
let index = hash(key, this.limit)
// There may be more than one
if (storage[index].length === 1 && storage[index][0] [0] === key) {
delete storage[index]
} else {
for (let i = 0; i < storage[index].length; i++) {
if (storage[index][i][0] === key) {
delete storage[index][i]
}
}
}
}
// Find data
lookup(key) {
const { storage } = this
let index = hash(key, this.limit)
if (storage[index] === undefined) {
return undefined
} else {
for (let i = 0; i < storage[index].length; i++) {
if (storage[index][i][0] === key) {
return storage[index][i][1]}}}}}Copy the codetest
let ht = new HashTable(10)
ht.add('aaa'.'111')
ht.add('bbb'.'222')
ht.add('ccc'.'333')
ht.add('ddd'.'444')
console.log(ht.lookup('ccc')) / / 333
ht.print()
Copy the codeLinked List
reference
You can think of each node of a linked list as storing a piece of data. Each node of a linked list has two parts: the data part and the address part.
Linked lists have different forms, mainly divided into three types: one-way linked list, two-way linked list, circular linked list. Here is a one-way linked list:
Unidirectional linked lists versus arrays
To find the performance
A lookup operation for a one-way linked list usually looks like this:
- Enter the primary node, start to compare the value of the node, if different through the pointer to the next node
- Repeat until the same value is found, or the node’s pointer points to NULL
Linked lists have the same search performance as arrays with O(n) time complexity.
Insert and delete performance
The biggest difference between a linked list and an array lies in the performance advantage of deletion and insertion. Because a linked list is a discontinuous memory, there is no need to carry out a large area of member displacement during insertion and deletion like an array. For example, a new node C is inserted between nodes A and B.
- A breaks the pointer to B and points it to C
- Node C points to node B. End
This insert operation only needs to move the pointer, and the time complexity of insert and delete is only O(1).
Read performance
Linked lists also have the disadvantage of being far less efficient than arrays, which are read efficiently because they are contiguous memory and can be quickly located by addressing formulas, whereas linked lists, which are discontiguous memory, must be traversed node by node by pointer.
For example, if we want to read the third member of an array, we only need ARR [2] to get the member quickly, whereas linked lists need to be accessed from the head node and read from the next node through the pointer.
JS implementation of single linked list
class Node {
constructor(element) {
this.element = element
this.next = null; }}class LinkedList {
length = 0;
head = null;
size() {
return this.length;
}
// Return the first element of the list
head() {
return this.head;
}
// Add an element to the end of the list
add(element) {
const node = new Node(element)
if (this.head === null) {
this.head = node
} else {
let currentNode = this.head;
while(currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
this.length++
}
remove(element) {
let currentNode = this.head
let prevNode;
if (currentNode.element === element) {
this.head = currentNode.next
} else {
while(currentNode.element ! == element) { prevNode = currentNode currentNode = currentNode.next } prevNode.next = currentNode.next }this.length--; // This is not very rigorous
}
isEmpty() {
return this.length === 0
}
indexOf(element) {
let currentNode = this.head;
let index = -1;
while (currentNode) {
index++;
if (currentNode.element === element) {
return index;
}
currentNode = currentNode.next;
}
return -1;
}
// Get the element corresponding to the index
elementAt(index) {
let currentNode = this.head;
let count = 0;
while (count < index) {
count++;
currentNode = currentNode.next;
}
return currentNode.element
}
// Add an element at a specific location in the list
addAt(index, element) {
let node = new Node(element)
let currentNode = this.head;
let prevNode;
let currentIndex = 0;
if (index > this.length) {
return false;
}
if (index === 0) {
node.next = currentNode;
this.head = node;
} else {
while (currentIndex < index) {
currentIndex++;
prevNode = currentNode
currentNode = currentNode.next
}
node.next = currentNode
prevNode.next = node;
}
this.length++;
}
// This is similar to the addAt method
removeAt(index) {
let currentNode = this.head;
let prevNode;
let currentIndex = 0;
if (index < 0 || index >= this.length) {
return null;
}
if (index === 0) {
this.head = currentIndex.next;
} else {
while (currentIndex < index) {
currentIndex++;
prevNode = currentNode
currentNode = currentNode.next
}
prevNode.next = currentNode.next;
}
this.length--;
return currentNode.element
}
}
Copy the codetest
const list = new LinkedList();
list.add('aaa')
list.add('bbb')
list.add('ccc')
list.add('ddd')
list.add('eee')
console.log(list.size()) / / 5
console.log(list.removeAt(3)) // ddd
console.log(list.size()) / / 4
Copy the codeTrie(Dictionary tree)
Application scenarios
Also called a prefix tree, it is a branch of the tree and a data structure used to store associated data.
Trie also has branches, and one branch can store a single word, so the trie structure is often used to store words/strings, for example, to check if a word/string exists in a data set.
In trie, each node represents a letter/character, as shown below:
The star indicates that this position is the end node of a word, that is, to the position of the star mark, there is a complete word
JS code implementation:
class Node {
constructor() {
/ / as shown above, the keys to the root Node, it is a new Map ([' b ', the new Node ()], [' d ', the new Node ()], [' s', the new Node ()])
this.keys = new Map(a);this.end = false;
}
setEnd() {
this.end = true;
}
isEnd() {
return this.end; }}class Trie {
constructor() {
this.root = new Node()
}
add(str, node = this.root) {
if (str.length === 0) {
node.setEnd()
return;
} else if(! node.keys.has(str[0])) {
node.keys.set(str[0].new Node())
return this.add(str.substr(1), node.keys.get(str[0))}else {
return this.add(str.substr(1), node.keys.get(str[0))}}// Whether word is in Trie
isWord(word) {
let node = this.root;
while (word.length > 1) { / / is greater than 1
if(! node.keys.has(word[0]) {return false;
} else {
node = node.keys.get(word[0])
word = word.substr(1)}}// While is greater than 1
return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
}
// Print out all the words (branch)
print() {
let words = []
let search = (node, str) = > {
if(node.keys.size ! = =0) {
for (let letter of node.keys.keys()) {
search(node.keys.get(letter), str.concat(letter))
}
if (node.isEnd()) {
words.push(str)
}
} else {
str.length > 0 ? words.push(str): undefined;
return;
}
}
search(this.root, ' ')
return words.length > 0 ? words : null}}Copy the codetest
const myTrie = new Trie();
myTrie.add('ball')
myTrie.add('bat')
myTrie.add('doll')
myTrie.add('dork')
myTrie.add('do')
myTrie.add('dorm')
myTrie.add('send')
myTrie.add('sense')
console.log(myTrie.isWord('doll')) // true
console.log(myTrie.isWord('dor')) // false
console.log(myTrie.isWord('dora')) // false
console.log(myTrie.print()) // ['ball', 'bat', 'doll', 'dork', 'dorm', 'do', 'send', 'sense']
Copy the codeGraphs (FIG.)
Application scenarios
There are many ways to store graphs: adjacency matrix, adjacency list, cross linked list, multiple adjacency list and so on.
The two most commonly used: adjacency matrix and adjacency list, here to explain the adjacency list.
Adjacency list structure:
-
Store vertices in the graph —-> array/object
-
Edge pointing relation —-> linked list/array
The diagram below:
The code implementation of the collar table:
class Graph {
constructor(points) {
/ / points
this.points = points
// Number of edges
this.sideNum = 0;
// Each point corresponds to a list/array
this.adjArray = Array.from({ length: points.length }, () = >[])}addPoint(id, point) {
let index1 = this.points.findIndex(v= > v === id)
this.adjArray[index1].push(point)
/* For undirected graphs, suppose A and B are joined: if you want to add only one connection between A and B(a-b or b-a), you need the following statement, but if you add two connections (a-b and b-a), you do not need the following statement */
// let index2 = this.points.findIndex(v => v === point)
// this.adjArray[index2].push(id)
this.sideNum++
}
addPoints(id, points) {
points.forEach(item= > {
this.addPoint(id, item)
})
}
getPoints(id) {
let index = this.points.findIndex(v= > v === id)
return this.adjArray[index]
}
// Prints formatted data
print() {
let str = ' '
this.points.forEach((item, index) = > {
str += item + '- > [' + this.adjArray[index].join(', ') + '] \n'
})
return str
}
getMap(points) {
let arr = points.reduce((arr, item) = > {
return arr.concat(this.getPoints(item))
}, [])
return arr.reduce((map, item) = > {
if(! map[item]) { map[item] =1
} else {
map[item]++
}
return map
}, {})
}
/ / intersection
getUnions(points) {
let map = this.getMap(points)
let len = points.length
return Object.keys(map).filter(key= > map[key] >= len)
}
/ / and set
getCollect(points) {
let map = this.getMap(points)
return Object.keys(map).filter(key= > map[key])
}
}
Copy the codeTest, to achieve the following structure:
const demo = new Graph(['v0'.'v1'.'v2'.'v3'.'v4'])
/ / register
demo.addPoints('v0'['v2'.'v3']);
demo.addPoints('v1'['v3'.'v4']);
demo.addPoints('v2'['v0'.'v3'.'v4']);
demo.addPoints('v3'['v0'.'v1'.'v2']);
demo.addPoints('v4'['v1'.'v2']);
// -----------------------------------
// console.log(demo.getPoints('v0'))
// console.log(demo.getPoints('v1'))
// console.log(demo.getPoints('v2'))
// console.log(demo.getPoints('v3'))
// console.log(demo.getPoints('v4'))
console.log(demo.print())
Copy the code
If you get something, give it a thumbs up