Data structure used so far
 Array
 The array can be divided into queues, stacks, etc.
 Hash table
 Used to store keyvalue pairs
Queue
Queue is a special array** "Firstin, firstout FIFO" array**
FIFO: first in, first out
topic
 Please implement a "restaurant call number" webpage
 Click the "Get Number" button to generate a number
 Click the "Call Number" button, and it will display "Please X number for dinner]
analysis

First of all, you should choose "queue" as the data structure
 Because "calling" should follow the principle of "first come, first served", which is consistent with the "first in, first out" of "queue"

The two important APIs of the queue: enqueue and dequeue
 In JS, "Enqueue" is equivalent to queue.push (add a person at the end of the number array)
 In JS, "dequeue" is equivalent to queue.shift (kick the first person in the call number array, end the queue, and go to dinner)

Remember to practice the usage of call

Other things just go with the flow, see the complete code
 In the local compiler, you can install parcel (yarn global add parcel),runparcel + (file path, such as src/index.html)To open local services and monitor in real time
 In the local compiler, you can install parcel (
Code
< body >
< div id = "screen" > </div >
< div class = "actions" >
< button class = "createNumber" > Take number </button >
< button class = "callNumber" > Call number </button >
</div >
< div >
Current number: < span id = "newNumber" > </span >
</div >
< div >
Current queue: < span ID = "Queue" > </span >
</div >
< Script the src = "./main.js" > </Script >
</body >
copy the code
//Get all page elements
const divScreen = document .querySelector( "#screen" )
const btnCreateNumber = document .querySelector( ".createNumber" )
const btnCallNumber = document .querySelector( ".callNumber" )
const spanNewNumber = document .querySelector( "#newNumber" )
const spanQueue = document .querySelector( "#queue" )
//Number
picking
//Number picking number n starts from 0 by default, and increments by 1 after each click. //You need to write down all the numbers you have taken before you can call number
let n = 0
let queue = []
btnCreateNumber.onclick = () => {
n += 1
queue.push(n) //join the queue
spanNewNumber.innerText = n
spanQueue.innerText = JSON .stringify(queue)
/* innerText can only display strings,
* You can use queue.toString() to display the effect: 1, 2, 3, 4
* Using JSON.stringify(..) will convert the JS object into a string with exactly the same appearance, [1,2,3,4]
* */
}
//Call the number
btnCallNumber.onclick = () => {
if (queue.length === 0 ) { //When the queue is empty, no more call operations are performed
return spanQueue.innerText = `No need to queue`
}
const m = queue.shift() //
Dequeue divScreen.innerText = `Please eat with ${m) `
spanQueue.innerText = JSON .stringify(queue)
}
Copy code
ask
If you didn't know the knowledge point of "queue", what would you do?

Understand the "queue" and see this realization logic (first come, first served), and immediately know that this is in line with "queue: enqueue/dequeue" (first in first out). Students only need to understand: "queue, leave the team" The corresponding API form in JS can be

Without the aid of "data structure" related knowledge, we can only deduce the realization of this logic step by step (relatively weak)
 So "data structure" is very important
Stack
Array of "Last In, First Out LIFO"
LIFO: last in, first out
For example
It can be understood in a not rigorous "elevator" scenario: the elevator from the first floor to the 88th floor, the advanced elevator will stand at the end of the elevator. And those who enter the elevator later stand at the front of the elevator and will exit the elevator first
In reallife operating mechanisms, there are few examples of such unfairness , so the following is an example of **"JS function call"**. The ``call stack'' of JS is the data structure of the ``stack''

The call stack of JS function call stack is a stack

Suppose f1 calls f2 and f2 calls f3

Then after f3 ends, it should return to f2, and after f2 ends, it should return to f1.
Code
function f1 () { let a = 1 ; returb a+f2()}
function f2 () { let b = 2 ; return b+f3()}
function f3 () { let c = 3 ; return c}
f1()
//Question: How does the above code push and pop the stack?
Copy code
Draw the process of pushing and popping the stack, and you will know that this is a "last in, first out" stack
First of all, the stack is an array
 Pushing the stack is push (added to the end)
 Pop the stack is pop (pop the front first)
Leave a suspense
The stack memory in the memory graph and this call stack
 What is their relationship? It's a big deal
 Is it the same piece of memory? (It can be said that it is the same piece of memory, because) there is a big overlap
This piece has little to do with JS.
Linked List
As long as it satisfies the data structure of "one for a chain", it is a "linked list"
actual use
Example: The "chain" in **"JS prototype chain"** actually refers to the "linked list"
let array = [ 1 , 2 , 3 ]
=== .__ proto__ Array Array .prototype
Array .prototype .__ proto__ === Object .prototype
copy the code
From this perspective, any ordinary object in JS is a linked list (because of the concept of prototype)
Linked list is an abstraction of data structure. This kind of abstraction is a very loose link relationship
let array = [ 1 , 2 , 3 ]
array.push //There is no push in the array itself, just go to the array prototype to find
array.hasOwnProperty //The array itself does not, there is no array prototype, you can only find the
copy code from the object prototype
This is a very concise mechanism to implement inheritance
Benefits of linked lists
You can break the chain in the middle at any time
example

Any array, remove the array prototype in the chain

Implementation: Let the _ proto _ of the array directly point to the object prototype (then this array no longer has push methods)
let array = [ 1 , 2 , 3 ] array.__proto__ //Get the array prototype array.__proto__.__proto__ //Get the object prototype array.__proto__.__proto__.__proto__ //null //Let the __proto__ of the array directly point to the object prototype array.__proto__ = Object .prototype Array.push //undefined copy the code
Simple operation of linked list
How to create a linked list, how to add, delete, modify and check on the linked list
What kind of model can be constructed in the brain
Add node
First attempt: failed
BUG analysis
 Running the [appendList method] of the following code can only achieve one situation: that is, after the first node, add the second node.
 When you want to add multiple nodes, run [appendList method] multiple times and you will find that there are always only two nodes in the linked list
 The result of multiple runs is that the second node is constantly being replaced, and the node written by the user during each run is not added to the back of the existing node
/*
* How to create a linked list
* The simplest linked list is a linked list with only one node
* A node, represented by an object. Need to include two attributes: data, next node (empty by default)
* */
const createList = ( value ) => {
return {
data : value, next : null //By default , the
next node is empty
}
}
/* Add other nodes*/
const appendList = ( list, value ) => {
const node = {
data : value,
next : null
}
list.next = node
return node //Add a node node to the list, and use this node node as the function return value
}
const list = createList( 10 ) //Create a list chain (only one node)
const node = appendList(list, 20 ) //Add a node node to the list chain.
Console .log ( `node` , Node)
Console .log ( ` list` , List)
copy the code
Code simplification
{
data : value, //formal parameter value
next : null //The default is a singlenode linked list, and the next node is empty
}
Copy code
The above part has been cited many times. It can be extracted and used as a single function createNode to call multiple times
//Extract the common part and separate it into a function createNode
const createNode = ( value ) => {
return {
data : value,
next : null
}
}
 
const createList = ( value ) => {
return createNode(value) //<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< <<<< multiple calls
}
const appendList = ( list, value ) => {
const node = createNode(value) //<<<<<<<<<<<<<<<<<<<<<<<<<<<<< << multiple calls
list.next = node
return node
}
Copy code
2.attempt: success
When we say "add node" is actually to add a new node after the last node of the current chain. Instead of adding a new node after the first node
The above logic must be clearly understood so that the code can be written correctly
const appendList = ( list, value ) => {
const node = createNode(value) //First generate the content of the node we want to add
//Add node: We need to add a new node after the last node of the current chain.
//So you must find the last node of the
list let x = list
//Reassign the variable x, which is more
secure . Directly using the original value of the list may cause problems. //Opening assumption: The linked list has only one node, and the variable x is declared as this node (and the last node) of the linked list
//Loop traversal
//If there are nodes after x, it means that x is not the last node, and x needs to be reassigned to the next node
while (x.next) {
x = x.next
}
//x.next === null
//When the traversal is over, if x.next is null, it means that x is the last node.//
At this point, only need, assign the node that needs to be added to x.next.
x.next = node
return node //Use the node node that needs to be added as the function return value
}
Copy code
Delete node
Now there are 3 nodes on the list chain, and the data of each node is 10/20/30 respectively. Requirement: Remove 20 nodes from the chain
Example analysis

The idea of this realization is similar to the previous example.
"Remove 20 nodes from the chain" actually means that the next of 10 nodes no longer points to 20, but directly points to 30

After deleting the connection between 10 and 20, the next of 10 and 20 still point to 30 respectively. But there is no object pointing to 20, 20 is equivalent to the memory garbage that no one uses, the browser will automatically recycle it

So in the end 102030, it becomes 1030
(Illustration )
Question: How to find the previous node of 20 nodes (we can only find the next node of the current node through next, and there is no attribute to save the previous node of the current node?)
Ideas
 From the above figure, we can see that ** Delete X node ** can be transferred to another requirement
 ** "Let the next node of X's previous node directly point to the next node of X" **
 Skipping the X node is equivalent to deleting the X node from the chain (the browser will also automatically reclaim it)
The first attempt: find a pattern
Conventional logic writing
/*
* Delete node
* Parameter 1: Which chain to delete from
* Parameter 2: Which node to delete
* */
const removeFromList_Demo = ( list, node ) => { //Note: the name of the chain === the name of the first node
//If
the name to be deleted (passed by node) is the first node (the node .next means the second node) if (node === list) {
list = node.next // Just reassign the first node list to the second node (equivalent to the first node does not exist)
} else {
//If the item to be deleted (passed by node) is the second Nodes (then node.next means the third node)
if (node === list.next) {
list.next = node.next // Just point the next of the first node directly to the third node (skipping the second node, which is equivalent to deleting)
} else {
//If you want to delete (node passed in) Is the third node (then node.next means the fourth node)
if (node === list.next.next) {
list.next.next = node.next // Just point the next of the second node to the fourth node directly (skip the third node, which is equivalent to deleting)
} else {
//If the
fourth node is to be deleted Node => Let the third node.next point to the fifth node directly (skip 4) if (node === list.next.next.next) {
(list.next.next).next = node.next
} else {
//Have you found the pattern?
//This is a loop (recursion)
}
}
}
}
}
Copy code
According to the requirements, write the abovementioned conventional code: very redundant, all approximate codes, repeated continuously. [Does it mean that this is actually a rule to follow?]
Conjecture: Is it possible to use "loops" to solve the repeated calls of the code and realize the law
2.attempt: there is a bug
Use loops to realize the law
 Delete X node: Let the next of [X's previous node] directly point to [X's next node] (X.next)
 So **the key is: how to find the last node of X**
 To know the last node of X, this is closely related to node X
/*
* Delete node
* Parameter 1: Which chain to delete from
* Parameter 2: Which node to delete
* (Chain name === the first node)
* */
const removeFromList = ( list, node ) => {
let x = list //x defaults to the first node
let p = null //p always represents the previous node of x, default is empty
//The incoming node indicates the node to be deleted.
//To traverse each node in the chain, use x to represent the node currently traversed.
//Compare x with node. If the current node x is not equal to the node node, then reassign x to the next node and judge whether it is equal again
//Keep looping to find the next one, and eventually x will find the node to be deleted
//Because [the previous node of x] is the key, so every round of the loop, [the previous node of the current x] should be recorded
while (node !== x) {
p = x //Use p to write down the current x in each round.
x = x.next //and then reassign x to the next node
//(At this time x becomes the next node of x, p becomes x Previous node)
}
//While traversal is over, the node to be deleted is obtained. If it is not found, it means that the node passed in by the user does not exist ( )
//In summary, after the traversal, there are two cases for the values of x and p
//console.log(x === node  x === null)//x either finds the incoming node to be deleted; or it is null
//console.log(p === the previous node of x p === null)//p Either it is the previous node of x; or it is null (indicating that the first node to be deleted is the first node, so p is null)
/*
* Finally, deleting the node is equivalent to skipping this node.
* x is the node to be deleted, then skip the node x, it should be the next node of the previous node of x, and directly point to the next node of x (skip x)
* next of the previous node of x ===> p.next
* The next node of x ===> x.next
* */
p.next = x.next // in summary
}
Copy code
Through the loop, the law is realized, but there are bugs.
 Unable to delete the first node
 Lack of handling of many boundary conditions
Examples are as follows:
const list = createList( 10 );
const node = list //node is the first node of the list now
removeFromList(list, node) //you will find that the list has not changed
const newList = removeFromList(list, node) //even get the return value is useless, because there is no return to the new list
copy the code
Third attempt: success
/*
* Delete node
* Parameter 1: Which chain to delete from
* Parameter 2: Which node to delete
* removeFromList_Demo1: Original code, used to discover the law
* removeFromList_Demo2: The final code, used to implement the law (cycle), without handling the boundary conditions
* removeFromList: very abstract and not the best solution
* The key idea: to make the next of [the previous node of X] point directly to the [next node of X], skip the x node
* */
const removeFromList = ( list, node ) => {
let x = list
let p = node //p still represents the previous node of x. In Demo2, p is initialized to null, here is changed to node
while (x != = node && x !== null ) { //I forgot to deal with null in Demo2. If node is not in the list, x may be null
p = x
x = x.next
//(At this time x is reassigned to [the next node of x], then p becomes [the previous node of x], a little abstract, pay attention to understanding)
}
if (x === null ) { //If x is null, you don t need to delete it, just return directly, false means you can t delete the node that is not in the list
return false
} else if (x === p) {
//the beginning of x The value is list, and the initial value of p is node.
//If the node receives the parameter list, x===p after the loop, that is, both parameters are lists, indicating that the node to be deleted is the first node
p = x.next //p is the list, and the list is renewed Assigned to list.next, the original value of the list does not exist, which is equivalent to deleting the first node of the original list
return p
//If the first node is deleted, then the head node p of the new list must be returned to the outside
//That is newList = removeFromList(list, list)
} else {
p.next = x.next //Assignment skips the x node
return list //If the deleted node is not the first node, just return to the original list
}
}
const list = createList( 10 )
const node = list //node is the first node of the list now
const newList = removeFromList(list, node) //You must use newList to get the return value to get the first node deleted New list
copy code
PS Of course, there are other more elegant implementation methods, such as changing the head pointer to the head node. . .
Only 10% of the students in Huazhong University of Science and Technology who have listened to the linked list course can write this code for deleting nodes.
The logic is very convoluted and difficult. So relax, don t be too anxious if you don t understand
Traverse nodes
Perform some operations on each node in the list
/*
* Get node
* Parameters: which node to get
* Return this node node
* Idea: traverse once to record 1, traverse twice to record 2, traverse to the index time to return this node
* */
const getNode = ( list, index ) => {
let x = list
let count = 1
while (x !== null ) {
if (count !== index) {
count += 1
x = x.next
} else {
return x
}
}
}
Copy code
summary
list = create(value) //create
node = get(index)
append(node, value) //add
remove(node) //delete
travel(list, fn) //traverse
copy code
Deformation of the linked list
This one is more superclass, so I only propose a concept, if you are interested, you can understand it yourself
Doubly linked list
Each node has a previous, which points to the previous node
Circular linked list
Next of the last node, pointing to the head node
Hash table keyvalue pairs
The linked list is more complicated, and the hash table is not as complicated as the linked list
Some people say: Hash table seems to be a simplified version of JS object, is there any difficulty?

The difficulty of hash tables is not the word "table"

The difficulty lies in the word **"hash"**

Here is an article (car park case) to help you understand what a hash is
Hash table
keyvalue combination
 Is to store data in the form of keyvalue
 There is no upper limit to the storage capacity. But the more you save, the harder it is to read
 The difficulty is how to read the hash table faster
Difficulties of hash tables
Scenes
 Assume that there are 10000 keyvalue pairs in the hashTable (N=10000)
 How to make reading any hashTable['yyy'] fast?
 You can read an article (same as the parking lot case)
hashTable = {
aaa : value1
aab : value2
aba : value3
abb : value4
...
zzz : value10000 //Assuming there are 10000 pairs of keyvalue
}
//The fastest way to find hashTable [ `yyy`] is
copy the code
Solution
4.ways to read hashTable['yyy'] are as follows

Without any optimization, hash['xxx'] needs to traverse all keys, and the complexity is O(N) (N represents the total number of keys 10000) [Slow speed]
 10.thousand takes 1 second, one hundred thousand takes 10 seconds...

Sort the keys and use the binary search method. The complexity is O(log(2)N) => can be abbreviated as (ln N) [faster]

Use the ASCII number corresponding to the string as index, the complexity is O(1) [fastest speed, huge space]
aaa => 979797 (a: 97 ) yyy => 121121121 (y: 121 ) //Although yyy can be found directly once, it is like the case of a parking lot, which leads to too much space (each finger corresponds to a space) copy code 
Divide the index, take the remainder, O(1) [The fastest speed, save most of the space]
Assuming that the ASCII of the key to be obtained is 979797 , prepare a length of container with 1000 Then use 979 797/1000 remainder certainly 0 ~ 999 between This array only needs 0 ~ 999 items { 0 : aaa,aab,aba,abb,... 1 : bbb,bba,bab,baa,... 2 : ccc,... ... 998 : yyy,... 999 : zzz,... } Copy code(There are two for the same number) What should I do if there is a conflict?
 998 When it is full, it will be stored as 999, when it is full, it will be stored as 0, and when it is 0, it will be stored as 1
 There are only 1000 locations anyway
Faster reading of data through hash table
 The hash table solves this problem (easy to save and fast to read)
Tree
Multiple in one chain
Is an upgrade to the linked list
 children is an array
 The data1 node has two child nodes (array elements) data2/data3, which together form a "tree" structure (can have infinite length)
 The two child nodes data2/data3 can link down to other child nodes data4/5/6 , or there are no other child nodes
 If the child node no longer (branches) has children, call this child node "leaf"
 The end of the chain, the last node
 So data1 has two leaves
It doesn t look like a tree, like a pyramid, but it looks like a tree upside down.
actual use
In real life, there are "tree" structures everywhere
 China s provinces and municipalities can be seen as a tree
 The hierarchical structure of the company can be seen as a tree
 The nodes in the webpage can be seen as a tree html> head, body, body> div, span, a, p , head> link, title, meta
Add, delete, modify and check the "tree"
let tree = createTree(value) //create tree
let node = createNode(value) //create node
addChild(tree,node) //add node
removeChild(node1,node2) //delete node
travel(tree) //traverse the tree
Copy code
Create tree (root node)
const createTree = ( value ) => {
return {
data : value,
children : null , //child node
parent : null //parent node
}
}
Copy code
Add child node
/*
* Add child nodes
* Parameter 1: Under which node to add child nodes
* Parameter 2: What is the child node data to be added
* */
const addChild = ( node, value ) => {
const newNode = {
data : value,
children : null ,
parent : node
}
node.children = node.children  [] //You must ensure that node.children is an array before you can use the push method
node.children.push(newNode)
return newNode
}
Copy code
Traverse nodes
/*
* Traverse nodes
* First fn to operate the root node, and then traverse all the child nodes on the root node, and use fn to operate the child nodes (continuously looping)
* This traversal method of printing the root node first and then processing the child nodes is called the "root traversal first" method, which is a relatively simple traversal method
* Of course there are other traversal methods
* */
const travel = ( tree, fn ) => {
fn(tree)
if (tree.children) {
for ( let i = 0 ; i <tree.children.length; i++) {
travel(tree.children[i], fn)
}
}
}
Copy code
Delete node
/*
* Delete node
* Array can only delete elements by subscript (splice)
* So you must first find the siblings of node, traverse the siblings, and see which node is ranked (get the subscript)
* */
const removeNode = ( tree, node /* node to be deleted*/ ) => {
const siblings = node.parent.children
let index = 0
for ( let i = 0 ; i <siblings.length; i++) {
if (siblings[i] === node) {
index = i
}
}
siblings.splice(index, 1 )
}
Copy code
Find node
/*
* Find node
* */
const findNode = ( tree, node ) => {
if (tree === node) { //What you want to find is the root node
return tree
} else if (tree !== node && tree.children) { //nonroot node and child nodes
for ( let i = 0 ; i <tree.children.length; i++) { //traverse all children Node, find the target node
const result = findNode(tree.children[i], node) //recursive
if (result) {
return result
}
}
return undefined
}
return undefined
}
Copy code
The data structure is that simple?
Yes, the data structure is these codes
 The difficulty is, looking at the code is simple, but it is very difficult to write (logic winding)
 Even if I don t think about it clearly in my brain, I have to write it out, log it, and derive it slowly.
In fact, the data structure must be simple
 All data structures can be summarized in one sentence
 What is the queue: first in, first out
 What is the stack: first in, last out
 What is a hash table: keyvalue combination
 What is a linked list: one object is linked to another object
 What is a tree: One object links multiple objects
 It cannot be complicated. Even if it is complicated, it will be divided into several simple problems by the programmer.
Because programmers advocate simplicity and elegance
 Programmers advocate simplicity and elegance
 If you think a certain programming concept is really difficult
 Then please believe it must be something you have misunderstood
 Please try to understand again
 Knock on the details yourself to find the wrong point.
 During this process, you may suddenly realize "Oh!! That is the case, what my brain thought was wrong"
tips "Binary Tree" may be the most difficult in the front end