Summary of common front end data structure

liangyue 2021-05-03 14:44:13
summary common end data structure


One 、 Stack

brief introduction

Is a kind of the stack Last in, first out ( namely LIFO:Last in, First out) Data structure of , stay JavaScript There is no stack structure in , But you can use arrays to do all the functions of the stack : push( Push ) and pop( Out of the stack )

Code implementation

function Stack() {
this.stack = []
this.push = function(item) {
stack.push(item)
}
this.pop = function() {
stack.pop()
}
}
 Copy code 

Application scenarios

Function call stack

To make it easier to understand the scene , Let's start with a piece of code :

function first() {
console.log('first start')
second()
console.log('first end')
}
function second() {
console.log('second start')
}
console.log('start')
first()
console.log('end')
// start
// first start
// second start
// first end
// end
 Copy code 

The result of this code execution shows that : Function in execution , The first function is executed at the end , encounter first Function time , Enter function execution , When you meet second Function time , execute second, stay second After the function is executed, continue to execute first, Finally, execute end end .
In this way, it is easy to understand why the logic of function call is actually realized by using the data structure of this stack .

Two 、 queue

brief introduction

A queue is a kind of fifo ( namely FIFO:First in, First out) Data structure of , stay JavaScript There is no data structure in the queue , But we can still use arrays to implement the queue function :enqueue( The team ) and dequeue( Out of the team )

Code implementation

function Queue() {
this.queue = []
this.enqueue = function(item) {
this.queue.push(item)
}
this.dequeue = function() {
return this.queue.shift()
}
}
 Copy code 

Application scenarios

JS Task queue

because js It's single threaded , So when multiple asynchronous functions are executed at the same time , When asynchronous tasks have results , Will enter a task queue first , stay js After the synchronization task of the main thread is completed , To read the task queue , Start a callback function that supports asynchronous functions in the order that asynchronous functions enter the task queue , That is, the function that enters the task queue first will be executed first

3、 ... and 、 Linked list

brief introduction

Links are also lists of multiple elements , But unlike queues and stacks , The storage of linked list is discontinuous , But use next Point to the next element . In the list , We need to add and delete elements , It just needs to be modified next Just a pointer . stay js We can use object To simulate a linked list .

Code implementation

/**
* Linked list
* @param {*} val
*/
function LinkList(val) {
/**
* Create a node node
* @param {*} val
* @param node
*/
function _creatNode(val) {
return {
val: val,
next: null,
}
}
this.head = _creatNode(val)
this.tail = this.head
/**
* lookup
* @param {*} val lookup val
* @returns node
*/
this.find = function (val) {
let node = this.head
while (node) {
if (val === node.val) {
return node
}
node = node.next
}
return null
}
/**
* stay node The node is inserted after the node
*/
this.insert = function (insertVal, val) {
const insertNode = _creatNode(insertVal)
if (val) {
const node = this.find(val)
insertNode.next = node.next
node.next = insertNode
} else {
this.tail.next = insertNode
this.tail = insertNode
}
}
/**
* Traverse
* @param {Function} fn Callback function
*/
this.map = function (fn) {
let p = this.head
while (p) {
fn(p)
p = p.next
}
}
}
 Copy code 

Application scenarios

1. Prototype chain

stay js The structure of the central chain is very similar to that of the list . In the linked list we use next Attribute to link to the next element , The prototype chain uses __proto__ Property to link prototype objects

Four 、 aggregate

brief introduction

A collection is a kind of Disorder and uniqueness Data structure of , stay JavaScript in , We can use es6 Of Set Method to create a collection directly

Code implementation

// because es6 There is a special data structure in , You can create a collection directly 
const set = new Set()
set.add(1)
set.add(2)
...
 Copy code 

Application scenarios

1. Array weight removal

Usually we use it in actual development Set This kind of data structure is mostly used for de duplication , But when the array is de duplicated , Note that for data of reference type , If the references are different, they will exist in the collection by different values , meanwhile Set It can also be stored NaN undefined This kind of special data

2. Array judgment 、 Delete and other operations

For example, in determining whether there is a value in the array , Or delete a value in the array , You can also use Set.prototype.has and Set.prototype.delete And other methods to facilitate the operation of the array

5、 ... and 、 Dictionaries

brief introduction

Dictionaries are also data structures that store unique values , But in order to Key value pair The way to store . stay JavaScript in , We can use es6 Of Map Method to create a dictionary directly

Code implementation

const map = new Map()
 Copy code 

Application scenarios

Used to store data

Map It can be used to store data with mapping relationship , Like a id Corresponding to a content , This realization and js The function of ordinary objects in is similar to , however Map Is more powerful ,Objet Only strings can be used 、 Simple types such as numbers are used as key values , however Map You can use any type as a key , meanwhile Map You can also get the length directly ; And it's the same operation ,Map Execution is better than Object[key] This is faster .

Different from other similar data structures

Map And the general Object or Set, There are some similarities or differences , It is also summarized here , In the later use, it is better to select the appropriate data structure according to the needs and scenarios

And ordinary objects Object The difference between

  1. Orderliness :Map Will be stored in the original order of addition ,Object Will be based on key Automatic sorting
  2. Can the iteration :Map Implemented iterators , have access to for...of Way to traverse
  3. Map You can get the length directly
  4. Map Of key It can be any basic type ,Object It can only be a string 、 Numbers 、Symbol

And assemble Set The difference between

  1. Storage :Set Can only store key Can't save value, because key Can't repeat , therefore Set No repeat key
  2. an :Map After expansion, the format of each item is [key, value]

6、 ... and 、 Trees

brief introduction

Trees are a kind of layered An abstract model of data , stay JavaScript There is no tree in this data structure , So usually we use Object To simulate the structure of a tree

Code implementation

In order to facilitate the operation of the test tree , Let's first simulate the data structure of a tree :

const treeData = {
value: '1',
children: [
{
value: '1-1',
children: [
{
value: '1-1-1',
children: []
},
{
value: '1-1-2',
children: [
{
value: '1-1-2-1',
children: []
}
]
},
],
},
{
value: '1-2',
children: [
{
value: '1-2-1',
children: [],
},
],
},
],
}
 Copy code 

Depth-first traversal

The depth first traversal of a tree is children Just continue to traverse children, Until there is no children Then traverse the next node : Depth first traverses the process :

  1. Access root
  2. For the root node children Continue the depth first traversal
function des(root) {
console.log('value', root.value)
root.children.forEach(item => {
des(item)
})
}
des(treeData)
// value 1
// value 1-1
// value 1-1-1
// value 1-1-2
// value 1-1-2-1
// value 1-2
// value 1-2-1
 Copy code 

We can see that the order is priority traversal children, know children The end of traversal starts the depth traversal of the next node

Breadth first traversal

Breadth first traversal is to traverse the child nodes first , If the child node traversal is complete , Then traverse the children: Breadth first traverses the process :

  1. Create an array , Take the root node as the first item
  2. Pop up the first item in the array and access
  3. Will pop up the children Traverse and add to the array in turn
  4. repeat 2、3 Step until the queue is empty
function bfs(root) {
let arr = [root]
while(tree = arr.shift()) {
console.log('value', tree.value)
tree.children.forEach(item => {
arr.push(item)
})
}
}
bfs(treeData)
// value 1
// value 1-1
// value 1-2
// value 1-1-1
// value 1-1-2
// value 1-2-1
// value 1-1-2-1
 Copy code 

From the output results, we can see that the traversal of the tree is in accordance with the priority of traversing the child nodes , After traversing the child node, continue to traverse the child node of the child node ... until arr If the array is empty, the traversal is complete

Binary tree

Binary tree : Each node in the tree can only have two nodes at most , Usually we use Object To simulate a binary tree , The traversal of binary tree has its own advantages 、 in 、 There are three kinds of traversal
Full binary tree : Except that the last layer has no child nodes , Every node in each layer has a binary tree with two children , If the level of a binary tree is n, So the total number of nodes in a full binary tree is 2^k - 1 individual
Perfect binary tree : Binary tree ( Except for the last layer ) Every node of must be fully filled , At the last level, all the nodes are continuously concentrated on the left side

First simulate the data structure of a binary tree :

const binaryTreeData = {
value: 'root',
left: {
value: 'left',
left: {
value: 'left-left',
left: null,
right: null,
},
right: {
value: 'left-right',
left: {
value: 'left-right-left',
left: null,
right: null,
},
right: null,
},
},
right: {
value: 'right',
left: {
value: 'right-left',
left: null,
right: null,
},
right: {
value: 'right-right',
left: null,
right: null,
},
},
}
 Copy code 

Binary tree graph :

root
left
right
left-left
left-right
left-right-left
null
right-left
right-right

The first sequence traversal

root node -> Left Traversing the subtree in advance -> Right Traversing the subtree in advance , namely :

function preOrder(binaryTree) {
if (!binaryTree) return
console.log(binaryTree.value)
preOrder(binaryTree.left)
preOrder(binaryTree.right)
}
preOrder(binaryTreeData)
// root
// left
// left-left
// left-right
// left-right-left
// right
// right-left
// right-right
 Copy code 

In the sequence traversal

Left Order traversal in subtree -> root node -> Right Order traversal in subtree , namely :

function inOrder(binaryTree) {
if (!binaryTree) return
inOrder(binaryTree.left)
console.log(binaryTree.value)
inOrder(binaryTree.right)
}
inOrder(binaryTreeData)
// left-left
// left
// left-right-left
// left-right
// root
// right-left
// right
// right-right
 Copy code 

After the sequence traversal

Left Traversal of subtree postorder -> Right Traversal of subtree postorder -> root node , namely :

function postOrder(binaryTree) {
if (!binaryTree) return
postOrder(binaryTree.left)
postOrder(binaryTree.right)
console.log(binaryTree.value)
}
postOrder(binaryTreeData)
// left-left
// left-right-left
// left-right
// left
// right-left
// right-right
// right
// root
 Copy code 

Application scenarios

domTree、vDom

In the browser dom The structure and react、vue Virtual in this kind of framework dom They are applied to the tree data structure to represent the relationship between page elements

7、 ... and 、 chart

brief introduction

The picture is Network structure Abstract model , It's a group made up of edge The node of the link . A graph can represent any binary relationship ( Such as : Roads, etc ), stay javaScript Can be used in Object To simulate the data structure of a graph

The representation of a graph

For a more intuitive understanding chart The data structure and its representation of , Let's start with an example , Other operations on the graph are tested based on this example :

A
B
D
C
E

In this picture, we can see clearly that A、B、C、D、E The relationship between these nodes , So in javaScript How do we express this kind of relationship in English :

Adjacency matrix

A B C D E
A 0 1 0 0 0
B 0 0 1 1 0
C 0 0 0 0 1
D 0 1 0 0 0
E 1 0 0 0 0

Adjacency matrix Is to use a two-dimensional array to table the relationship between the vertices , for example A --> B, So in this two-dimensional array arr[0][1] by 1, If you can't link , Then for 0, This two-dimensional array represents the relationship between each vertex in the graph Adjacency matrix

Adjacent street table

{
A: [B],
B: [C, D],
C: [E],
D: [B],
E: [A]
}
 Copy code 

Adjacent street table Use an object to represent the relationship in the graph ,key For each vertex ,value Is an array , Represents the vertex that the vertex can link to , The way to represent vertices in a graph in this way is called Adjacent street table

Graph traversal

Depth-first traversal

Depth first traversal starts at a vertex , For this vertex Not traversing Adjacent vertices in turn Depth-first traversal , namely :

// Record traversed vertices 
const visited = new Set()
function dfs(node) {
console.log(node)
visited.add(node)
graph[node].forEach(childNode => {
if (!visited.has(childNode)) {
dfs(childNode)
}
})
}
dfs('A')
// A B C E D
 Copy code 

Let's assume that from A The vertex starts Depth-first traversal , So the input result is A B C E D, Comparing with the previous diagram, we can see the order of depth first traversal when traversing to C when , Will continue to traverse E And then we went through D, According to the rules of depth first traversal .

Breadth first traversal

Breadth first traversal of graphs and Trees Breadth first traversal is similar to :

  1. Need to put root Element entry
  2. Get out of the team and visit
  3. take Not traversing The adjacent nodes of are joined in turn
  4. repeat 2、3 Step , Until the queue is empty , namely :
const visited = new Set()
function bfs(node) {
const queue = [node]
// The root element is manually added to the accessed queue during traversal , Only the adjacent nodes of the root element are added 
visited.add(node)
while(visitNode = queue.shift()) {
console.log(visitNode)
graph[visitNode].forEach(childNode => {
if (!visited.has(childNode)) {
visited.add(childNode)
queue.push(childNode)
}
})
}
}
bfs('A')
// A B C D E
 Copy code 

We from A The vertex carries on Breadth first traversal , When traversal to C Node time , No more traversal C Next to each other , It's traversing D, According to the rules of breadth first traversal .

8、 ... and 、 Pile up

brief introduction

A heap is a kind of Special complete binary trees , All nodes in the heap are Greater than or equal to or less than His children , if Greater than or equal to the child node Then for The biggest pile , Otherwise The smallest pile . stay javaScript Arrays are usually used to represent heaps in
For the first i Nodes :
The index of its parent node is :Math.floor((i - 1) / 2)
The index of its left child node is :(2 * i) + 1
The index of its right child node is :(2 * i) + 2

Code implementation

Achieve minimal heap

function MinHeap() {
this.heap = []
this.getParentIndex = function (childIndex) {
return Math.floor((childIndex - 1) / 2)
}
/**
* Swap places
* @param {number} index1
* @param {number} index2
*/
this.swap = function (index1, index2) {
const temp = this.heap[index1]
this.heap[index1] = this.heap[index2]
this.heap[index2] = temp
}
/**
* Move up to the right place , Compared with the parent node , If it's smaller than the parent node, it exchanges
* @param {number} index Indexes
*/
this.moveUp = function (index) {
if (index === 0) return
const parentIndex = this.getParentIndex(index)
if (this.heap[index] < this.heap[parentIndex]) {
this.swap(index, parentIndex)
this.moveUp(parentIndex)
}
}
/**
* Additive elements
* @param {number} value
*/
this.append = function (value) {
this.heap.push(value)
this.moveUp(this.heap.length - 1)
}
}
const minHeap = new MinHeap()
minHeap.append(3)
minHeap.append(4)
minHeap.append(1)
minHeap.append(0)
minHeap.append(2)
minHeap.append(7)
minHeap.append(9)
// [0, 1, 3, 4, 2, 7, 9]
 Copy code 

adopt heap Can simulate a heap representation , namely :

0
1
2
3
4
7
9

You can see that this structure satisfies The smallest pile The definition of

Application scenarios

1. Find the maximum and minimum quickly and efficiently

You can build The biggest pile or The smallest pile Find the maximum and minimum quickly

2. Implement heap sort

Above we implemented a simple build The smallest pile Methods , So the principle of heap sorting is to build a The smallest pile And then the top of the pile ( The minimum value pops up ), And then build the other elements into a heap , Pop up every time Top of pile Elements until the remaining elements are 1 End of time , This is the implementation of a heap sort .

Nine 、 Last

This paper mainly introduces several common data structures and the use scenarios of different data structures , Also wrote some simplified version of the code , Although the function will be less , But simple code is easier to understand and remember , Interested partners can also implement more and more complex functions by themselves . On the one hand is to make a summary of their own learning , At the same time, I hope it can help you .
Thank you for reading

版权声明
本文为[liangyue]所创,转载请带上原文链接,感谢
https://qdmana.com/2021/05/20210503144051050d.html

  1. Why did gitlab choose vue.js?
  2. HTTP-RPC: 轻量跨平台REST服务
  3. 继全面采用Node.js以后,PayPal分享大幅度踩坑GraphQL心得 - Mark Stuart
  4. vue组件化开发实战之滚动/轮播的实现
  5. Http-rpc: lightweight cross platform rest Service
  6. Following the full adoption of node.js, PayPal shares a great deal of graphql experience mark Stuart
  7. Implementation of rolling / carousel in Vue component development
  8. CSS是什么?这一篇全解,绝对有你想要的
  9. What is CSS? This is a complete solution, there is absolutely what you want
  10. 04-HTML5常用标签-HTML5极速入门
  11. 04-html5 common tags
  12. WEB前端全套零基础视频教程+软件2021最新编程视频
  13. Web front end full set of zero basic video tutorial + software 2021 latest programming video
  14. 使用Node, Mongo, React, Redux实现Token认证
  15. Using node, Mongo, react and Redux to realize token authentication
  16. 体面编码之CSS和HTML
  17. CSS and HTML for decent coding
  18. 使用Playwright基于多浏览器进行javascript自动化测试的简单教程- Applitools
  19. A simple tutorial for JavaScript automatic testing based on multi browser using playwright - applitools
  20. Minimum distance to target element
  21. 浅谈 React 中的 XSS 攻击
  22. XSS attack in react
  23. 自学前端教程整理,附不容错过的前端100篇文章合集
  24. Self taught front-end tutorial collation, with a collection of 100 front-end articles that can not be missed
  25. 使用OpenTracing跟踪Go中的HTTP请求延迟
  26. Using opentracing to track HTTP request latency in go
  27. Encapsulating databinding allows you to write less than 10000 lines of code
  28. 03-HTML5标签-HTML5极速入门
  29. 03-html5 tag-html5 quick start
  30. LayUI - 极易上手拿来即用的前端 UI 框架
  31. Layui - easy to use front end UI framework
  32. Interpretation of lodash source code (1)
  33. Why is the first parameter of node family callback error?
  34. 报告:JavaScript 开发者达1380 万,C#超越 PHP,Rust 增长最快
  35. Report: Javascript developers reach 13.8 million, C surpasses PHP, and rust grows fastest
  36. 小白前端入门笔记(10),怎么设置网站内部的超链接?
  37. How to set up hyperlinks inside the website?
  38. Using node and socket to realize online chat room
  39. The core competitiveness of Vue: data bidirectional binding
  40. React configuration agent
  41. CSS layout
  42. Application scenario explanation of Vue dynamic component
  43. Redux learning notes 04 -- using multiple reducers to manage data
  44. After three months of typescript writing, what have I learned?
  45. Node family - what is a callback?
  46. React -- a simple implementation of render & create element
  47. JS learning simple usage of jquery
  48. Seamless love
  49. 小白前端入门笔记(12),设置哑链接
  50. Small white front-end entry notes (12), set dumb links
  51. Vue2. X opens composition API and TSX
  52. Interview record and thinking of social recruitment for one and a half years (Alibaba, Tencent, baidu offer)
  53. Flex learning notes
  54. The most essential closure article in the eastern hemisphere
  55. 2021-05-03 hot news
  56. Sword finger offer -- reverse order pair in array (JS Implementation)
  57. Working process of scaffold
  58. Use decorator mode to strengthen your fetch
  59. [JS] scope (Introduction)
  60. Employment information statistics network (interface document)