Data structures used so far
- An array of
- Arrays can be divided into queues, stacks, and so on
- Hash table
- Used to store key-value pairs
Queue Queue
A queue is a special kind of array — a FIFO array
FIFO : first in , first out
The title
- Please implement a “restaurant call” page
- Click the “Get number” button to generate a number
- Click the “station number” button, it will show “Please have dinner on date X”
Analysis of the
-
First, you should select “queue” as the data structure
- This is because “calling” is supposed to be on a “first come, first served” basis, which is consistent with the “first in, first out” principle of “queue”
-
There are two important APIS for queues: queue entry and queue exit
- In JS, queuing is equivalent to queue.push (adding a person at the end of the call number array)
- In JS, “out of line” is equivalent to queue.shift.
-
Remember to practice the use of “call”
-
The rest takes care of itself, see the full code
- In the local compiler, you can install a parcel (
yarn global add parcelRun),Parcel + (file path, such as SRC /index.html)To turn on local services and listen in real time
- In the local compiler, you can install a parcel (
code
<body>
<div id="screen"></div>
<div class="actions">
<button class="createNumber">Take a no.</button>
<button class="callNumber">Your turn</button>
</div>
<div>Current Number:<span id="newNumber"></span>
</div>
<div>Current queue:<span id="queue"></span>
</div>
<script 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")
/ / take a number
// Number n The value starts from 0 by default and increases by 1 after each tap
// You need to write down all the numbers
let n = 0
let queue = []
btnCreateNumber.onclick = () = > {
n += 1
queue.push(n) / / team
spanNewNumber.innerText = n
spanQueue.innerText = JSON.stringify(queue)
/* innerText can only display strings, * can be queue.tostring () : 1,2,3,4 * json.stringify (..) Converts the JS object to an identical looking string, [1,2,3,4] * */
}
/ / your turn
btnCallNumber.onclick = () = > {
if (queue.length === 0) { // When the queue is empty, the call operation is not performed
return spanQueue.innerText = 'No queue'
}
const m = queue.shift() / / out of the team
divScreen.innerText = ` please${m}The repast `
spanQueue.innerText = JSON.stringify(queue)
}
Copy the code 
q
What would you do if you didn’t know about queues?
-
Understand “queue”, see this implementation logic (first come first served), you can immediately know that this conforms to “queue: in queue/out of queue” (first in first out) students only need to understand: “in queue, out of queue” in JS corresponding API form
-
Without the aid of knowledge related to “data structure”, the implementation method of this logic can only be derived step by step (relatively weak)
- So “data structure” is important
Stack Stack
LIFO array
LIFO : last in , first out
For example,
It can be understood with an imprecise “take the elevator” scenario: the first floor directly to the 88th floor of the elevator, the advanced elevator, will stand at the end of the elevator. The last person to enter the elevator will get out first, standing in front of the elevator
In real life, there are very few examples of this kind of unfair operation mechanism, so the following is a ** “JS function call” example to expand. JS “call stack” is the data structure of “stack”
-
The JS function call stack is a stack
-
Suppose F1 calls F2, and F2 calls F3
-
So when F3 ends it should go back to F2, and when F2 ends it should go back 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()
// How does this code stack and bounce?
Copy the codeIf you draw the process of pushing and unloading the stack, you can see that this is a “last in, first out” stack
First, a stack is an array
- Pushing is pushing.
- Pop stack is pop (pop out the front first)
Leave it in suspense
The stack memory in the memory diagram and this call stack
- What is the relationship? — It matters a lot.
- Is it the same memory? There is a lot of overlap
This doesn’t have much to do with JS.
List Linked List
As long as it satisfies the “one chain one” data structure, it is a “linked list”.
The actual use
Example: ** “JS prototype chain” ** in the “chain”, actually refers to “linked list”
let array = [1.2.3]
array.__proto__ === Array.prototype
Array.prototype.__proto__ === Object.prototype
Copy the codeFrom this perspective, any ordinary object in JS is a linked list (because of the concept of prototypes).
A linked list is an abstraction of data structures. This abstraction is a very loose link relationship
let array = [1.2.3]
array.push // Array does not have push
array.hasOwnProperty // Array does not exist, array prototype does not exist, only object prototype can be found
Copy the codeThis is a very neat mechanism for implementing inheritance
The benefits of linked lists
You can break the chain at any time
case
-
Any array array, get rid of the array prototype in the chain
-
Implementation: Make array’s _proto_ point directly to the object prototype (then the 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 // Make array's __proto__ point directly to the object prototype array.__proto__ = Object.prototype array.push // undefined Copy the code
Simple operation of linked lists ✅
How to create a linked list, how to add, delete, change and check a linked list
What kind of model can you build in your brain
Add a node
First attempt: failed ❌
BUG analysis
- The appendList method running the following code only achieves one thing: adding a second node after the first.
- When you want to add more than one node, run the appendList method multiple times and you will always have only two nodes in the list
- The result of multiple runs is that the second node is constantly replaced, without adding user-written nodes to existing nodes at each run
/* * How to create a linked list ↓ * The simplest list is a list with only one node * one node, represented by an object. You need to include two attributes: data, and the next node (empty by default) * */
const createList = (value) = > {
return {
data: value,
next: null // The next node is empty by default}}/* Add other nodes */
const appendList = (list, value) = > {
const node = {
data: value,
next: null
}
list.next = node
return node // Add a node to the list and return this node as the function value
}
const list = createList(10) // Create a list chain (only one node)
const node = appendList(list, 20) // Add node to the list chain.
console.log(`node`, node)
console.log(`list`, list)
Copy the codeCode to simplify
{
data: value, / / parameter value
next: null // The default is a single-node list with the next node empty
}
Copy the codeThe above section has been cited many times. This can be extracted into a single function, createNode, that can be called multiple times
// Extract the common part into a separate function createNode
const createNode = (value) = > {
return {
data: value,
next: null}} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -const createList = (value) = > {
return createNode(value) // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< many times
}
const appendList = (list, value) = > {
const node = createNode(value) // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< many times
list.next = node
return node
}
Copy the codeSecond attempt: successful ✔️
When we say “add node”, we actually want to add new nodes after the last node of the current chain, not after the first node.
👆 This logic must be clearly recognized so that the code can be written correctly
const appendList = (list, value) = > {
const node = createNode(value) // Add 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.
// The last node of the list must be found
let x = list
// Reassign to the variable x, safer. Using the original list can cause problems
// If the list has only one node, declare variable x as the last node of the list.
// loop over
// If there is a node after x, it indicates that x is not the last node and needs to be reassigned to the next node
while (x.next) {
x = x.next
}
// x.next === null
// if x. ext is null, x is the last node
// Just assign the node to x.next
x.next = node
return node // return the node to be added
}
Copy the code
Remove nodes
There are three nodes in the list chain, and the data of each node is 10/20/30 respectively. Requirement: Remove 20 nodes from the chain
The sample analysis
-
The idea behind this implementation is similar to the previous example.
By “removing 20 nodes from the chain,” you essentially make the 10-node next point to 30 instead of 20
-
After removing the link between 10 and 20, next of 10 and 20 still points to 30. But there is no object pointing to 20, which is the equivalent of unused memory garbage that the browser automatically reclaims
-
So eventually 10 minus 20 minus 30 becomes 10 minus 30
(Illustration ↘)
Question: How to find the last node of the 20 nodes (we can only find the next node of the current node through next, there is no property to save the last node of the current node??)
Train of thought
- As can be seen from the figure above, ** “delete node X” ** can be transferred to another requirement 👇
- ** “Let next, the last node of X, point directly to the next node of X” **
- Skipping the X node removes the X node from the chain (the browser also recycles it automatically)
First try: find a pattern ⚠️
Conventional logic writing
/* * Delete node * Parameter 1: which chain to delete * Parameter 2: which node to delete * */
const removeFromList_Demo = (list, node) = > { // Note: the chain name === the name of the first node
// If the first node is to be removed (node.next represents the second node)
if (node === list) {
list = node.next // reassign the first node list to the second node.
} else {
// If the node to delete is the second node (then node.next represents the third node)
if (node === list.next) {
list.next = node.next // Select next from first node and point directly to third node.
} else {
// If the node to delete is the third node (node.next represents the fourth node)
if (node === list.next.next) {
list.next.next = node.next // Select next from node 2 and point directly to node 4.
} else {
Next, point straight to section 5 (skip 4)
if (node === list.next.next.next) {
(list.next.next).next = node.next
} else {
// See the pattern?
// This is a recursive loop
}
}
}
}
}
Copy the codeAccording to the requirements, write the above general code: very redundant, full of approximate code, repetitive. Is there a rule to follow?
Guess: whether “loop” can be used to solve the code of repeated calls, implementation rules
Second attempt: Bug ⭕️
Use cycle, realize rule
- Delete X node: make next of [previous node of X] point directly to [next node of X] (x.next).
- So the key is: how does the last node of X find **
- You know, the last node of X, this is very closely related to the X node
/* * Delete node * Parameter 1: delete from which chain * Parameter 2: delete from which node * (chain name === first node) * */
const removeFromList = (list, node) = > {
let x = list // x defaults to the first node
let p = null // p always represents the last node of x, which is null by default
// The node passed in represents 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 node, re-assign x to the next node to determine whether it is equal
// Iterate over the next node, and eventually X will find the node to delete
// Because [last node of x] is the key, the last node of current X is recorded in each round of the loop
while(node ! == x) { p = x// Write down the current x with p for each round
x = x.next // Then reassign x to the next node
// when x becomes the next node of x, p becomes the last node of x.
}
// while the current node to be deleted. If not, the node passed in by the user does not exist.
// To sum up, after traversal, the values of x and p each have two cases 👇
/ / the console. The log (x = = = node | | x = = = null) / / x or find the incoming to remove node; Or null
. / / the console log (p = = = x on a node | | p = = = null) / / p either x on a node. Or null (p = null)
/* * Finally, delete the node, equivalent to skip the node. * x is the node to be deleted, so if you skip x, it should be next of the previous node of x, directly pointing to the next node of x (skip x) * next of the previous node of x ===> p.ext * next of x ===> x.ext * */
p.next = x.next // ← / it can be concluded that
}
Copy the codeThrough the loop, the rule is realized, but there are bugs.
- Unable to delete the first node
- Missing a lot of boundary case handling
The following is an example:
const list = createList(10);
const node = list // node is the first node in the list now
removeFromList(list, node) // You will notice that the list has not changed at all
const newList = removeFromList(list, node) // The new list is not returned at all
Copy the codeThird attempt: success ✅
RemoveFromList_Demo1: the original code used to discover the pattern * removeFromList_Demo2: RemoveFromList: very abstract and not optimal * Next points directly to the next node of X, skipping the X node * */
const removeFromList = (list, node) = > {
let x = list
let p = node // p still represents the previous node of x. Demo2 initializes p to null
while(x ! == node && x ! = =null) { // Demo2 forgot to handle null. If node is not in list, x may be null
p = x
x = x.next
// if x is the next node of x, p is the last node of x.
}
if (x === null) { // If x is null, you do not need to delete the node. If x is false, you cannot delete the node that is not in the list
return false
} else if (x === p) {
// the initial value of x is list and the initial value of p is node.
// If node receives a list, then x===p is the first node to be removed
p = x.next // p is list, list is reassigned to list.next, then list does not exist, equivalent to deleting the first node of the original list
return p
// If the first node is deleted, the new list's head node p is returned outside
// newList = removeFromList(list, list)
} else {
p.next = x.next // Assignment skips the x node
return list // If not the first node, return the original list}}const list = createList(10)
const node = list // node is the first node in the list now
const newList = removeFromList(list, node) // newList must be used to get the return value to get the newList with the first node removed
Copy the codeThere are other, more elegant implementations of P.S., such as changing the header pointer to a header node, but that’s a little overdone…
Only 10% of the students who listened to the linked list class for the first time in Huazhong University of Science and Technology could write the code to delete the node.
The logic is convoluted and difficult. So relax and don’t get too upset if you don’t understand
Traverse the nodes
For each node in the list, do something
/* * get node * parameter: to get the number of nodes * return this node 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 the codeconclusion
list = create(value) / / create
node = get(index)
append(node, value) / / add
remove(node) / / delete
travel(list,fn) / / traverse
Copy the codeDeformation of linked lists
This is more than the outline, just put forward a concept, interested in their own understanding
Two-way linked list
Each node has a previous that points to the previous node
Circular linked list
Next of the last node points to the head node
Key-value pairs for hash table
Linked lists are more complex, hash tables are not as complex as linked lists
Some people say: hash table looks like a simplified version of JS object, is there any difficulty?
-
The difficulty in hashing tables is not the word table
-
The difficulty lies in the word “hash” **
-
Here’s an article (parking lot case) to help you understand what hash is
Hash table
Key – the combination of the value
- Store key-value data
- There is no upper limit on storage capacity. But the more you save, the harder it is to read
- The challenge is how do you read the hash table faster
Hash table difficulty
scenario
- Suppose there are 10000 key-value pairs in the hashTable (N=10000)
- How to make reading any hashTable[‘yyy’] fast?
- Here’s an article (same with the parking lot case)
hashTable = {
aaa: value1
aab: value2
aba: value3
abb: value4
...
zzz: value10000 // Suppose there are 10,000 key-value pairs
}
// The fastest way to find hashTable[' yyy ']
Copy the codeThe solution
Four ways to read hashTable[‘yyy’] are as follows
-
Without any optimization, hash[‘ XXX ‘] traverses all keys with O(N) complexity (N indicates the total number of keys is 10000)
- Ten thousand takes one second, one hundred thousand takes ten seconds…
-
Order (log(2)N) => order (log(2)N)
-
Index with ASCII numbers corresponding to strings, complexity O(1)
aaa => 979797 (a: 97) yyy => 121121121 (y: 121) // Although yyY can be found directly at one time, as in the parking lot case, it takes up too much space (each refers to a space). Copy the code -
Divide index, take remainder, O(1)
Assume that the ASCII of the key to be retrieved is979797, prepare a length of1000Use the container979797 / 1000The remainder must be0~999The array between just needs0~999Item {0: aaa, aab, aba, abb,...1: bbb,bba,bab,baa,... 2: ccc,... .998: yyy,... 999: zzz,... } Copy the code(the same number has two) conflict how to do, conflict will be postponed
- When 998 is full, 999,999 is full, 0 is full, 0 is full, 1 is full…
- There are only 1,000 places
Through the hash table to achieve faster reading of the data
- Hash tables solve this problem (easy to store and fast to read)
Tree Tree
Multiple chains
It’s an upgrade to linked lists
- Children is an array
- The data1 node has two children (array elements), data2 / data3, which together form a “tree” structure (which can be infinitely long)
- Two children data2 / data3 can then be linked down to other children datA4/5/6… And there are no other child nodes
- If the child has no more children, the child is called a leaf
- It’s the end of the chain, the last node
- So data1 has two leaves
It doesn’t look like a tree. It looks like a pyramid. It looks like a tree upside down
The actual use
In real life, trees are everywhere
- China’s provinces and cities can be seen as a tree
- The corporate hierarchy can be viewed as a tree
- HTML > head, body, body > div, span, a, P… , head > link, title, meta
Add, delete, change and check “tree”
let tree = createTree(value) / / create a tree
let node = createNode(value) // Create a node
addChild(tree,node) // Add a node
removeChild(node1,node2) // Delete a node
travel(tree) / / traversal tree
Copy the codeCreating a tree (root node)
const createTree = (value) = > {
return {
data: value,
children: null./ / child nodes
parent: null / / the parent node}}Copy the codeAdding child Nodes
/* * Add child node * Parameter 1: Which node to add child node * Parameter 2: What is the data of the child node to add * */
const addChild = (node, value) = > {
const newNode = {
data: value,
children: null.parent: node
}
node.children = node.children || [] // Node. children must be an array to use the push method
node.children.push(newNode)
return newNode
}
Copy the codeTraverse the nodes
/* * traversal nodes * fn operates on the root node, and then traverses all the children on the root node, respectively, using FN to operate the children (continuous loop) * This traversal method, called "first root traversal" method, is 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 the codeRemove nodes
/* * Delete nodes * arrays can only be deleted by subscript (splice) * so you must first find nodes' siblings and iterate over them to see which node ranks (get subscript) * */
const removeNode = (tree, node/* The 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 the codeFind nodes
/* * find the node * */
const findNode = (tree, node) = > {
if (tree === node) { // We need to find the root node
return tree
} else if(tree ! == node && tree.children) {// A non-root node with child nodes
for (let i = 0; i < tree.children.length; i++) { // Traverses all child nodes to find the destination node
const result = findNode(tree.children[i], node) / / recursion
if (result) {
return result
}
}
return undefined
}
return undefined
}
Copy the code
Is the data structure that simple?
Yeah, the data structure is this code
- The difficulty is that the code looks simple, but it is very difficult to write.
- I can’t even think clearly in my head. I have to write it out, log it, and then work it out
In fact, the data structure must be simple
- All data structures can be summarized in a single sentence
- What is a queue: first in, first out
- What is the stack: in and out
- What is a hash table: a key-value combination
- What is a linked list: one object linked to another
- What is a tree: one object linked to multiple objects
- It can’t be complicated, and even if it is, the programmer will break it down into simple problems
Because 👇 programmers adore simplicity and elegance
- Programmers worship simplicity and elegance
- If you find a programming concept really hard
- So please believe that there must be something wrong with your understanding
- Please try to understand it again
- Put the detailsDo it yourself, to find the error point.
- You may suddenly realize, “Oh, here it is, my mind was wrong.”
Tips “binary trees” are probably the most difficult of the front ends