preface
This article combs several common data structure, for the crowd for data structure introduction and systematic review of data structure partners! Xiaobian from the definition of each data structure, characteristics, use scenarios and method implementation, and finally attached a related exercise in Leecode, to help you better grasp the corresponding knowledge. If you have this need, come quickly ~
The stack
The characteristics of
It is a LIFO data structure. According to the literal meaning is the first to go out, after the first to go in. Think about the case around there are many, such as:
-
In the coal stove, the briquettes that are put in first are at the bottom and taken out last, while the briquettes that are put in last are at the top and taken out first;
-
The clothes in the storage box are folded in first and taken out last;
.
There is no stack data structure in JS, so if you want to achieve the function of stack in JS, you need to use Array to achieve it. Let’s see how to use stacks with arrays.
const stack = []; // Stack space, simulated by arrays
/ / into the stack
stack.push(1);
stack.push(2);
/ / out of the stack
const p1 = stack.pop();
const p2 = stack.pop();
Copy the codeThe stack changes: [1, 2] => [1] => [], P1 =2, P2 =1, which also verifies lifO.
implementation
After learning how to use it, let’s implement a simple stack structure:
class Stack{
container = []; / / container
/ / into the stack
enter(value){
this.container.unshift(value);
}
/ / out of the stack
leave(){
return this.container.shift();
}
// Get the stack length
size(){
return this.container.length;
}
// Get the stack result
value(){
return this.container.slice(0); // Clone the container to prevent external operations from modifying the internal container}}Copy the codepractice
The characteristics of the stack mentioned above is last in first out, so that is the need for last in first out place need to use the stack!
- Decimal to binary;
- Determines whether the parentheses of the string are valid;
- Function call stack;
This is the most common use of a stack in a program. Let’s use string parentheses as an example to get a feel for what the stack can do.
/ * title description: given a only include a '(',') ', '{','} ', '/', ' 'string, to determine whether a string is effective. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string. Example: "[] {} ()" / / true "()" / / false "{[]}" / / true "([]" / / false * /
Copy the codeSo let’s see, for an open parenthesis that doesn’t close, the closer the open parenthesis is, the closer the close parenthesis is, satisfying the last in, first out condition. So let’s take a step-by-step look at how to do that.
The problem solving steps
- Create a new stack;
- If the string is traversed, it will be pushed onto the stack when it encounters an open parenthesis. If it encounters a close parenthesis matching the top parenthesis, it will be pushed off the stack. If the type does not match, it will be judged as illegal.
- Finally stack empty is legal, otherwise illegal;
/ * * *@param {string} s
* @return {boolean}* /
var isValid = function(s) {
if(s.length % 2= = =1) {return false}; // If the string length is odd, it is definitely illegal
const stack = []; / / container
for(let i=0; i<s.length; i++){const item = s[i];
if(item === '(' || item === '[' || item === '{'){
stack.push(item); // open parenthesis on the stack
}else{
const top = stack[stack.length-1]; // Get the top element of the stack
if(
// Check whether the top element matches the current symbol
(top === '(' && item === ') ')||
(top === '[' && item === '] ')||
(top === '{' && item === '} ')
){
stack.pop();
}else{
return false; }}}return stack.length === 0; // Stack null is valid, non-null is invalid
};
Copy the codeNow that we have solved the problem, let’s analyze its time complexity and space complexity:
Time complexity: O(n) [n is the length of the string, because there is only one for loop, push/ POP operations are O(1) complexity];
Space complexity: O(n)
The queue
The characteristics of
A fifO data structure. It is easy for us to think of queues everywhere in life: queuing for meals in the canteen, queuing for hospital registration, queuing for banking services and so on.
In our JS there is no queue this data structure, to achieve the function of the queue in JS, also need to use Array to achieve. Let’s see how to use queues with arrays.
const queue = []; // Queue, simulated by array
/ / team
queue.push(1);
queue.push(2);
/ / out of the team
const p1 = queue.shift();
const p2 = queue.shift();
Copy the codeThe whole process can be seen through breakpoint debugging, the queue changes: [1, 2] => [2] => [], P1 =1, P2 =2, which also verifies first-in, first-out.
implementation
With that in mind, let’s simply implement a queue structure:
class Queue {
container = []; / / container
/ / team
enter(element) {
this.container.push(element);
}
/ / out of the team
leave() {
return this.container.shift();
}
// Queue length
size() {
return this.container.length;
}
// Get the result in the queue
value() {
return this.container.slice(0); }}Copy the codepractice
Usage scenarios
- JS asynchronous task queue; JS is a single thread and cannot handle concurrent tasks in async.
- Count the number of recent requests; When a new request enters the queue, the one who initiates the request is the first to leave the queue. The length of the queue is the number of recent requests.
The above is the most common use of queues in the program, the following to count the number of recent requests as an example to feel the role of queues!
* Write a RecentCounter class to count the most recent requests. It has only one method: ping(int t), where t stands for some time in milliseconds. Returns the number of pings from 3000 ms ago to the present. Any pings within the [T-3000, t] time range will be counted, including current pings. Make sure that each call to ping uses a larger t value than before. Example: the input: inputs = [" RecentCounter ", "ping", "ping", "ping", "ping"], inputs = [[], [1], [100], [3001], [3002]] output: Null, 1,2,3,3 * /
Copy the codeLook at the topic so, be a bit meng, very confused person! The first inputs represent the record of the inputs that sent the request, and the second inputs represent the time that the request was sent.
- The first ping occurs in 1ms
- The second ping occurs at 100ms
- The third ping occurs at 3001ms
- The fourth ping occurs at 3002ms
What you need to calculate is the time at which the current ping occurred and how many pings occurred in the last 3000 milliseconds. It was so difficult that I got myself confused
In other words, if the current ping occurs at time t, we want to know how many times (t-3000) ms to t ms ping. Further analysis can be concluded as follows:
T = 1ms: time range (0,1), when there is only one request, [1];
T = 100ms: time range (0,100), where there are two requests, [1] and [100];
T = 3001ms: time range (1,3001), at this time there are 3 requests, 3001-3000 = 1, because it is closed, 1 is included in the calculation, so it is the 3 requests [1], [100] and [3001];
T = 3002ms: time range (2,3002), at this time there are 3 requests, 3002-3000 = 2, so T-1ms has to request to queue out, so it is [100], [3001] and [3002] three requests;
That should make it easier to understand! Now that you understand the problem, let’s see how to do it. The RecentCounter class is instantiated, and the ping method is called in the order of the input array. Each ping call takes the parameter t and puts its return value into the output array.
The problem solving steps
- Create a queue;
- Join the team if there is a new request, if the request is sent before 3000ms, it will be removed from the team;
- The length of the queue is the number of recent requests.
var RecentCounter = function() {
this.q = []; // Attach queue to this so queue q can be accessed at ping
};
/ * * *@param {number} t
* @return {number}* /
RecentCounter.prototype.ping = function(t) {
this.q.push(t); // A new request joins the queue
while(this.q[0] < t - 3000) {// Check whether it is within the time range
this.q.shift(); // Queue out of range
}
return this.q.length;
};
/** * Your RecentCounter object will be instantiated and called as such: * var obj = new RecentCounter() * var param_1 = obj.ping(t) */
Copy the codeHere we have solved this problem, is not found very simple! Similarly, let’s analyze its time and space complexity:
Time complexity: O(n) [n is the number of requests that need to be excluded from the queue];
Space complexity: O(n) [n is the length of queue];
The list
What is a linked list?
A linked list is a data structure that consists of a list of elements, but the storage of the elements is not contiguous and is connected by a next pointer.
Since it is also a list of multiple elements, why not just use an array and design such a complex linked list? Let’s look at the differences.
The difference between arrays and linked lists
Array: To add or remove non-beginning or end elements, move the elements.
Linked list: To add or remove non-beginning or end elements, you do not need to move the elements. You only need to change the pointer to next.
Similarly, there are no linked lists in JS. We use Object to simulate the linked list structure! Type the blackboard, here is not Array, Object!!
implementation
const a = { val: 'a' }
const b = { val: 'b' }
const c = { val: 'c' }
// Establish the association through next
a.next = b;
b.next = c;
// Iterate over the list
let p = a;
while (p) {
console.log(p.val); //a b c
p = p.next;
}
// Insert d into the list
const d = { val: 'd' };
b.next = d;
d.next = c;
// Delete d from the list
b.next = c;
Copy the codepractice
/* * Write a function that removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted. Example 1: Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Given the second node in your list with a value of 5, the list strain will be 4 -> 1 -> 9 after your function is called. Example 2: Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: Given a third node in your list whose value is 1, the strain of the list is 4 -> 5 -> 9 after calling your function. Tip: The linked list contains at least two nodes. All nodes in a linked list have unique values. The given node is a non-trailing node and must be a valid node in the linked list. Do not return any results from your function. * /
Copy the codeLet’s analyze the problem first. In this problem, we can’t directly get the last node of the deleted node, it just points to the next node. How do you delete it? You can move the deleted node to the next node. Take example 1, for example, if we want to delete node 1, first assign 9 to node 1, then 4=>5=>9=>9, and then delete the last node 9 to achieve the goal.
Steps to solve the problem:
- Change the value of the truncated point to the value of the next node;
- Delete the next node.
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} node
* @return {void} Do not return anything, modify node in-place instead.
*/
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
Copy the codeTime complexity: O(1) [no loop] Space complexity: O(1) [No matrix, array]
The tree
What is a tree?
It is an abstract model of layered data. Here is not to say that we usually see the tree O(∩_∩)O, in the front-end work common trees include: DOM tree, cascading selection, tree control…… JS does not have a tree, so we use Object and Array to simulate a tree. Let’s take a look at its basic structure.
{
label:'parent'.value:'p1'.children:[
{
label:'child1'.value:'c1'.children:[
label:'c-child1'.value:'cc1'] {},label:'child2'.value:'c2'}}]Copy the codeCommon operations
Depth/breadth first traversal
A in the figure can be regarded as the root node of the book directory, B and C are the section directories, and D, E, F and G are the contents of each section. So depth-first traversal is to go page by page, while breadth-first traversal is to look at the chapter list first, and then look at the specific content of the chapter after you have read all the chapters. Figure 1-7 shows the traversal sequence. Let’s simulate the tree structure shown above:
const tree = {
val:'a'.children:[
{
val:'b'.children:[
{
val:'d'.children:[]
},
{
val:'e'.children:[]}]}, {val:'c'.children:[
{
val:'f'.children:[]
},
{
val:'g'.children:[]}]}Copy the codeLet’s see how the two traversal methods are implemented for this tree structure.
Depth-first traversal (DFS) : Search as deep a branch of the tree as possible. Algorithm formula: visit the root node and perform depth-first traversal on the children of the root node one by one.
const dfs = (root) = > {
console.log(root.val);
root.children.forEach(dfs); // The children recursion of the root node performs depth-first traversal
}
dfs(tree); //a b d e c f g
Copy the codeBreadth-first traversal (BFS) : Visits the node closest to the root node first.
Algorithm formula:
- Create a queue and add the root node to the queue.
- Take the team leader out of the team and visit;
- Put the children of the leader in the team one by one;
- Repeat 2,3 steps until the queue is empty.
const bfs = (root) = > {
const q = [root];
while(q.length>0) {const header = q.shift();
console.log(header.val);
header.children.forEach(child= >{
q.push(child);
})
}
}
bfs(tree); //a b c d e f g
Copy the codeMiddle – order traversal of binary tree
What is a binary tree? Each node in the tree can have a maximum of two child nodes. In JS, we usually use Object to simulate binary tree, the following data structure:
const binaryTree = {
val:1.left: {val:2.left: {val:4.left:null.right:null
},
right: {val:5.left:null.right:null}},right: {val:3.left: {val:6.left:null.right:null
},
right: {val:7.left:null.right:null}}}Copy the codeAfter understanding the binary tree, according to the above definition of the tree structure, we have a look at its three traversal methods and concrete implementation.
The first sequence traversal
- Access the root node;
- The left subtree of the root node is traversed in advance.
- The right subtree of the root node is traversed in advance.
const prevOrder = (root) = > {
if(! root)return;
console.log(root.val); / / the root node
prevOrder(root.left); / / the left subtree
prevOrder(root.right); / / right subtree
}
prevOrder(binaryTree); //1 2 4 5 3 6 7
Copy the codeIn the sequence traversal
- The left subtree of the root node is traversed in middle order.
- Access the root node;
- Middle order traversal of the right subtree of the root node;
const inOrder = (root) = > {
if(! root)return;
inOrder(root.left); / / the left subtree
console.log(root.val); / / the root node
inOrder(root.right); / / right subtree
}
inOrder(binaryTree); //4 2 5 1 6 3 7
Copy the codeAfter the sequence traversal
- The left subtree of the root node is traversed in order.
- Post-order traversal of the right subtree of the root node;
- Access the root node;
const postOrder = (root) = > {
if(! root)return;
postOrder(root.left); / / the left subtree
postOrder(root.right); / / right subtree
console.log(root.val); / / the root node
}
postOrder(binaryTree); //4
Copy the codepractice
/* * Given a binary tree, return its middle-order traversal. Input: [1, NULL,2,3] 1\2/3 Output: [1,3,2] */
Copy the codeWith the introduction of the previous sequence, here we do not need to repeat, directly on the code:
/ / the recursive version
var inorderTraversal = function(root) {
const res = [];
const rec = (n) = > {
if(! n)return; // The node does not have a direct return
rec(n.left); / / the left subtree
res.push(n.val); // Access the root node
rec(n.right); / / right subtree
}
rec(root)
return res;
};
Copy the codeRecursive version of the implementation is relatively simple, the use of iterative algorithm to achieve it!
var inorderTraversal = function(root) {
const res = [];
const stack = []; / / stack space
let p = root; / / pointer
while(stack.length || p){
while(p){
stack.push(p);
p = p.left; // indicates the left node
}
const top = stack.pop();
res.push(top.val);
p = top.right; // Access the right node
}
return res;
};
Copy the codeLet’s continue with the time and space complexity of the iteration:
Time complexity: O(n) [Middle-order traversal to all nodes, n is the number of all nodes in the binary tree]
Space complexity: O(n)
The heap
What is a heap?
It is a special kind of complete binary tree. So what is a perfect binary tree? The nodes in each layer are completely filled, and if the last layer is not full, only some nodes on the right are missing, then a complete binary tree satisfies this characteristic. A heap differs from a normal complete binary tree in that all nodes are greater than or equal to (maximum heap) or less than or equal to (minimum heap) its children. In JS generally used to represent the heap array, before the tree is used to simulate the Object, here how to change the array, is not a bit messy. Don’t panic. Just hold on. Keep looking.
It can be found that the position of the left child node is 2 * index + 1, the position of the right child node is 2 * index + 2, and the position of the parent node is (index-1) / 2.
So what are the applications of the heap? It is useful to find the maximum and minimum values efficiently and quickly, with time complexity O(1); Again, to find its minimum, return the top element of the heap. In addition, the heap can find the KTH largest (or smallest) element, which is described in the exercises below.
implementation
class MinHeap{
constructor(){
this.heap = [];
}
swap(i1,i2){
const temp = this.heap[i1];
this.heap[i1] = this.heap[i2];
this.heap[i2] = temp;
}
getParentIndex(i){
return ( i - 1) > >1;
}
getLeftIndex(i){
return i * 2 + 1;
}
getRightIndex(i){
return i * 2 + 2;
}
shiftUp(index){
if(index == 0) return;
const parentIndex = this.getParentIndex(index);
if(this.heap[parentIndex] > this.heap[index]){
this.swap(parentIndex,index);
this.shiftUp(parentIndex); }}shiftDown(index){
const leftIndex = this.getLeftIndex(index);
const rightIndex = this.getRightIndex(index);
if(this.heap[leftIndex] < this.heap[index]){
this.swap(leftIndex,index);
this.shiftDown(leftIndex);
}
if(this.heap[rightIndex] < this.heap[index]){
this.swap(rightIndex,index);
this.shiftDown(rightIndex); }}insert(value){
this.heap.push(value);
this.shiftUp(this.heap.length-1);
}
pop(){
this.heap[0] = this.heap.pop();
this.shiftDown(0);
}
peek(){
return this.heap[0];
}
size(){
return this.heap.length; }}Copy the codepractice
/* * Find the KTH largest element in an unsorted array. Note that you need to find the KTH largest element in the sorted array, not the KTH different element. Example 1: inputs: [3,2,1,5,6,4] and k = 2 output: 5 example 2: inputs: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4 note: you can assume that k is always valid and that 1 ≤ k ≤ the length of the array. * /
Copy the codeTo analyze how this problem works, see “the KTH largest element”, as mentioned earlier consider using a minimum heap implementation.
The problem solving steps
- Build a minimum heap and insert elements into the heap one by one;
- When the size of the heap exceeds K, the heap top is removed;
- After insertion, the top of the heap is the KTH largest element;
/ * * *@param {number[]} nums
* @param {number} k
* @return {number}* /
var findKthLargest = function(nums, k) {
const h = new MinHeap(); // Build the minimum heap instance
nums.forEach(n= >{
h.insert(n); // Insert the element into the heap
if(h.size() > k){ // The heap size exceeds k
h.pop(); // Delete the heaptop element}})return h.peek(); // Return the top of the heap element
};
Copy the codeTime complexity: O(n*logK)
Space complexity: O(k)
Heaps a little bit of effort ao ~(⊙﹏⊙), but also need more thinking about thinking about!
figure
What is the graph?
It is an abstract model of network structure, a set of nodes connected by edges. Graphs can be used to represent any binary relationship, such as roads, flights…… There is no graph data structure in JS. You can build a graph structure with Object and Array. The representation of graph includes adjacency matrix, adjacency list, incidence matrix and so on.
A collection of
What is a set?
It is an unordered and unique data structure. In ES6, there is a collection called Set. Let’s see how it is used.
/ / to heavy
const arr = [1.2.3.3];
const newArr = [...new Set(arr)];
console.log(newArr); / / [1, 2, 3]
// Determine if the element is in the set
const s1 = new Set(arr);
const has1 = s1.has(1);
const has2 = s1.has(8);
console.log(has1, has2); //true false
/ / intersection
const s2 = new Set([2.4.5]);
const s3 = new Set([...s1].filter(item= > s2.has(item)));
console.log(s3); //Set { 2 }
Copy the codeThese are the basic usage scenarios for a Set. Let’s take a look at some other common operations for a Set.
The Set of ES6
add
let mySet = new Set(a); mySet.add(1);
mySet.add(5);
mySet.add(5);
mySet.add('hello');
let obj = { name: 'tt' };
mySet.add(obj);
mySet.add([1.3]);
mySet.add({ name: 'tt' });
/** note: set uniqueness, 5 is not added, while obj and {name:'tt'} are both in set, because the two objects look the same, but are actually stored in different locations in memory, and are essentially different objects. * /
console.log(mySet);
//Set { 1, 5, 'hello', { name: 'tt' }, [ 1, 3 ], { name: 'tt' } }
Copy the codehas
let mySet = new Set(a); mySet.add(1);
mySet.add(5);
const has1 = mySet.has(3);
const has2 = mySet.has(5);
console.log (has1 has2);//false true
Copy the codedelete
let mySet = new Set(a); mySet.add(1);
mySet.add(5);
console.log(mySet); / / the Set {1, 5}
mySet.delete(5);
console.log(mySet); //Set {1}
Copy the codeThe iteration
for… of
for(let item of mySet){
console.log(item);
}
Copy the codekeys() / values() / entries()
for(let item of mySet.keys()){
console.log(item);
}
for(let item of mySet.values()){
console.log(item);
}
for(let [key,value] of mySet.entries()){
console.log(key,value);
}
/* 1 1 hello hello { name: 'tt' } { name: 'tt' } [ 1, 3 ] [ 1, 3 ] { name: 'tt' } { name: 'tt' } */
Copy the codeAs you can see, keys() and values() are the same.
Conversions between collections and arrays
// Set to array
const myArr = [...mySet];
const myArr = Array.from(mySet);
// array to set
const mySet2 = new Set([1.2.3.4]);
Copy the codemasked
const intersection = new Set([...mySet1].filter(item= > mySet2.has(item)));
Copy the codeO difference set
The difference set is very similar to the intersection. The intersection is to determine whether there are elements of set 1 in set 2. Now we just need to determine that set 2 does not contain elements of set 1.
Emm, I don’t think it’s confused! If you are confused, use stickers:
const difference = new Set([...mySet1]).filter(item= >! mySet.has(item));Copy the codepractice
/* Given two arrays, write a function to calculate their intersection. Example 1: input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2] example 2: input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] output: [9,4] Each element in the output must be unique. We can ignore the order of the output. * /
Copy the codeAnalyze the topic: point out that the element is unique, regardless of the order, seek intersection, naturally associated with the set.
The problem solving steps
- Nums1 is de-weighted by set;
- Iterate through nums1 and filter out the values that nums2 also contains;
/ * * *@param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}* /
var intersection = function (nums1, nums2) {
let s1 = new Set(nums1); // Use Set to retrieve nums1
return [...s1].filter(item= > nums2.includes(item)); //filter filter out the contents of the nums2 array containing nums1 elements
};
Copy the codeSimilarly, let’s analyze its time and space complexity:
Time complexity: O(m* N) [M refers to filter cycle consumption time, N refers to includes consumption time];
Space complexity: O(m) [m is the length of nums1 after deduplication];
The dictionary
What is a dictionary?
Similar to collections, it is a data structure that stores unique values, but in the form of key-value pairs. Key-value pairs are used for mapping. ES6 has a dictionary called Map. Here’s how it works:
const m = new Map(a);/ / to add
m.set('a'.'a1');
m.set('b'.'b1');
m.set('c'.'123');
/ / delete
m.delete('b');
//m.clear(); // Delete all elements
/ / change
m.set('a'.'hello');
console.log(m); //Map { 'a' => 'hello', 'c' => '123' }
/ / check
m.get('c'); / / 123
Copy the codeThis is its basic add, delete, change, check operation.
practice
Remember the exercise in the stack section? After we finish this section, let’s make some improvements to the previous problem.
/ * * *@param {string} s
* @return {boolean}* /
var isValid = function(s) {
if(s.length % 2= = =1) return false;
const stack = [];
const map = new Map(a); map.set('('.') ');
map.set('['.'] ');
map.set('{'.'} ');
for(let i=0; i<s.length; i++){let item = s[i];
if(map.get(item)){
stack.push(item);
}else{
let top = stack[stack.length-1];
if(map.get(top) === item){
stack.pop();
}else{
return false; }}}return stack.length === 0;
};
Copy the codeTime complexity: O(n) [n is the length of the string, because there is only one for loop, push/ POP operations are O(1) complexity];
Space complexity: O(n)
The above is all the content, xiaobian in their review process to comb out the summary of this article, I hope to help you! If there is a mistake, I hope every senior to testify!