The front end also needs to know something-data structure (on)

The front end also needs to know something-data structure (on)

Data structure used so far

  • Array
    • The array can be divided into queues, stacks, etc.
  • Hash table
    • Used to store key-value pairs

Queue

Queue is a special array-** "First-in, first-out 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
      ),run
      parcel + (file path, such as src/index.html)
      To open local services and monitor in real time

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 real-life 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 single-node 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 //Re-assign 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 re-assigned 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
  1. 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

  2. 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

  3. So in the end 10-20-30, it becomes 10-30

(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 re-assign 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 above-mentioned 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 re-assign 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 re-assign 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 re-assigned 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 super-class, 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 key-value 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

key-value combination

  • Is to store data in the form of key-value
  • 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 key-value 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 key-value } //The fastest way to find hashTable [ `yyy`] is copy the code

Solution

4.ways to read hashTable['yyy'] are as follows

  1. 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...
  2. Sort the keys and use the binary search method. The complexity is O(log(2)N) => can be abbreviated as (ln N) [faster]

  3. 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
  4. 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) { //non-root 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: key-value 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