Data structures that Web development should know about

Data structure concept

Data structure refers to the set of data elements which have one or more relations with each other and the composition of the relationship between the data elements in the set.

Commonly used data structures are: array, stack, linked list, queue, tree, graph, heap, hash table, etc., as shown in the figure:

Each kind of data structure has its own unique data storage mode. Different kinds of data structure are suitable for different kinds of applications. Some data structures are even designed to solve specific problems. Correct data structure selection can improve the efficiency of the algorithm.

Here are their structures and advantages and disadvantages.

Array 🌈

define

An array is a data structure consisting of a collection of elements of the same type, allocated a contiguous chunk of memory for storage. The index of an element can be used to calculate the corresponding storage address of the element.

• advantages

1. Querying elements by index is fast
2. It is convenient to traverse a number group by index

• disadvantages

1. Once the array is fixed in size, it cannot be expanded
2. An array can store only one type of data

• extension

1. The default store value in JavaScript arrays is undefined, and the default store value in other programming language arrays is 0 or junk data
2. Unlike other programming languages, JavaScript can access a nonexistent index in an array and return undefined, whereas other programming languages report an error or return junk data
3. JavaScript can store different types of data, whereas other programming languages can store only one type of data
4. JavaScript automatically expands arrays when they run out of space, whereas in other languages arrays are fixed in size and cannot be changed once defined
5. The storage allocated to arrays in JavaScript is discontinuous, whereas the storage allocated to arrays in other programming languages is continuous

• Applicable scenario

Frequent query that requires little storage space and is rarely added or deleted.

Stack 🎯

define

A stack, also known as a stack, is a special linear table. Operations can only be performed at one end of the linear table. Operations are allowed at the top of the stack, but not at the bottom of the stack. The characteristics of the stack are: First In, Last In, First Out (LIFO, Last In First Out), the operation of putting an element from the top of the stack is called on the stack, and the operation of removing an element is called on the stack.

• Applicable scenario

The stack is structured like a container, and what is put in first comes out later, so it is often used to implement recursive functions such as Fibonacci sequences, reversing list order, and undoing one or a series of operations

implementation

Here use stack to achieve an undo function

Example:

module.exports =  class Stack {
  data = []
  maxSize

  constructor(initialData, maxSize = -1) {
      this.data = Array.isArray(initialData) ? initialData : (typeof initialData == "undefined" ? [] : [initialData])
      this.maxSize = maxSize
  }
  
  isFull() {
      return this.maxSize ! = -1 ? (this.data.length == this.maxSize) : false
  }
  
  isEmpty() {
      return this.data.length == 0
  }
  
  add(item) {
      if(this.isFull()) {
          return false
      }
      this.data.push(item)
  }
  
  *generator() {
      while(!this.isEmpty()) {
          yield this.data.pop()
      }
  }
  
  pop() {
     const { value, done } = this.generator().next() 
     if(done) return false
     return value
  }
}
Copy the code

Use:

const Stack = require("./stack.js")
class Operation {
   constructor(val) {
       this.value = val
   }
}
class Add extends Operation {
   apply(value) {
       return value + thisValue}.undo(value) {
       return value - this.value 
   }
}
class Times extends Operation {
   apply(value) {
       return value * this.value
   }
   undo(value) {
       return value / this.value
   }
}
/** stack **/
class OpsStack {
   constructor() {
       this.value = 0
       this.operations = new Stack()
   }
   add(op) {
       this.value = op.apply(this.value)
       this.operations.add(op) 
   }
   
   undo() {
       if(this.operations.isEmpty()) {
           return false
       }
       this.value = (this.operations.pop()).undo(this.value)
   }
}
let s = new OpsStack()
s.add(new Add(1))
s.add(new Add(1))
s.add(new Times(2))
console.log("Current value: ", s.value)
s.undo()
s.undo()
console.log("Final value: ", s.value
// Current value: 4
// Final value: 1
Copy the code

The action classes (Add, Times) have two methods: apply to make the action work (Add and multiply), and undo to do the opposite (subtract).

Queue ✍

define

A queue, like a stack, is a linear table, except that it can add elements at one end and pull them out at the other, i.e., first-in, first-out. Putting an element from one end is called queuing, and taking an element out is queuing

• Application Scenario Because of the first-in, first-out (FIFO) feature of the queue, it is very suitable for multi-threaded blocking queue management.

implementation

Example:

class Queue {
  data = [];
  maxSize;

  constructor(initialData, maxSize = -1) {
    this.data = Array.isArray(initialData) ? initialData : typeof initialData == 'undefined' ? [] : [initialData];
    this.maxSize = maxSize;
  }

  isFull() {
    return this.maxSize ! = -1 ? this.data.length == this.maxSize : false;
  }

  isEmpty() {
    return this.data.length == 0;
  }

  enqueue(item) {
    if (this.isFull()) {
      return false;
    }
    this.data.push(item);
  }

  *generator() {
    while (!this.isEmpty()) {
      yield this.data.shift(); }}dequeue() {
    const { value, done } = this.generator().next();
    if (done) return false;
    returnvalue; }}Copy the code

This is mainly implemented by the enqueue and dequeue methods. Enqueue allows you to add elements to the queue, while the latter allows you to delete them. Arrays are used here for basic data structures because it greatly simplifies both approaches. Enqueuing is the same as pushing elements into an array; the queuing problem is resolved by a simple call to Shift, which removes the first element and returns it.

Use:

const  Queue  = require('./queues')

let q = new Queue(3.2)

q.enqueue(1)
q.enqueue(2) 

let x = 0
while(x = q.dequeue()) {
 console.log(x)
}
/*
Prints:
3
1
*/
Copy the code

In addition to the simple queue I show here:

• Priority queue: Its elements are internally sorted by priority value.
• Circular queue: the last element points to the first.
• Double-endian queue: A data structure that has the properties of a queue and stack. Elements in a two-ended queue can pop up from both ends (this sounds like cheating!). .

Heap 🚀

define

A heap is a special kind of data structure. A heap can be regarded as a tree, also known as a priority queue. Despite its name, the heap is not a queue. Because the operations allowed in the queue are first-in, first-out (FIFO), inserting elements at the end of the queue and fetching elements at the head. The heap inserts elements at the bottom of the heap and takes them out at the top of the heap, but the heap is not arranged in order of arrival, but in a certain order of priority. The node at the top of the heap is called the root node, and the root node itself has no parent node.

A classic implementation of a heap is a complete binary tree. A heap implemented in this way is called a binary heap.

This is to illustrate the concept of a full binary tree versus a complete binary tree.

Full binary tree: Except the leaf node, the left and right children of all nodes are not empty, it is a full binary tree, as shown in the following figure.It can be seen that all nodes in a full binary tree have left and right children. Complete binary tree: It is not necessarily a full binary tree, but the part of it that is dissatisfied must be on the lower right side, as shown belowThe heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap. Common heap have binary heap, Fibonacci heap and so on.

• The characteristics of

1. The value of any node is the maximum or minimum value of all nodes in the subtree
2. It has to be a complete binary tree

• Applicable scenario

Because of the characteristics of heap order, generally used to do the array sort, called heap sort.

implementation

Minimum heap insert (ADD)

Suppose that the existing element 5 needs to be inserted. In order to maintain full binary tree properties, the newly inserted element must be placed in the right subtree of node 6. At the same time in order to meet the value of any node is less than the value of the left and right subtrees of the properties, comparing to the newly inserted element and its parent nodes, if is smaller than the parent node, is about to pull the parent node down to replace the position of the current node, is constantly looking for upwards, in turn found than their parent, until no eligible value.

1. So I’m going to insert element 5 at the end, right of node 6.
2. Then compared to the parent class, 6 > 5, the parent class number is greater than the child class number, and the child class swaps with the parent class.
3. Repeat until no replacement occurs.

DELETE minimum heap (DELETE)

Core point: Fill the last element to the top of the heap, then sink the element continuously.

Let’s say we want to take node 1, or we could say we want to take node 1, and in order to maintain a full binary tree, we replace this one with the last element, 6; If it is larger than the left and right subtrees (if it exists), replace it with a smaller value from the left and right subtrees, and it will go to the corresponding subtree on its own, repeating the operation until no subtree is smaller than it.

By doing this, the heap is still the heap, so to summarize:

• Find the location of the node to be removed (removed node) in the array
• Replace the element at that position with the last element in the array
• The current position is compared to its left and right subtrees to ensure compliance with the inter-node rule of the minimum heap
• Delete the last element

List 🏉

define

A linked list is a discontinuous, non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by the pointer address of the linked list. Each element contains two nodes, one is the data domain (memory space) where the element is stored, and the other is the pointer domain pointing to the address of the next node.

• advantages

1. Linked list is a very common data structure, no need to initialize the capacity, can arbitrarily add and subtract elements;
2. When adding or deleting elements, you only need to change the pointer field of the node before and after the two elements to point to the address, so adding and deleting quickly;

• disadvantages

1. Because it contains a large number of pointer fields, it occupies a large space.
2. Finding elements requires traversing the linked list to find them, which is time-consuming.

• Applicable scenario

A scenario in which a small amount of data needs to be added frequently and deleted

According to the point of the pointer, linked lists can form different structures, such as single linked lists, bidirectional linked lists, circular linked lists, etc.

• Characteristics of circular linked lists

Compared with single linked list, circular linked list has the advantage of being convenient from chain end to chain head. When the data to be processed has the characteristics of ring structure, circular linked list is suitable for use.

• Characteristics of bidirectional linked lists

1. Compared to single-linked lists, double-linked lists require one more pointer to the precursor node, so if the same amount of data is stored, bi-linked lists take up more memory space than single-linked lists
2. Insertion and deletion of double-linked lists require maintaining both next and prev Pointers.
3. Element access in a doubly linked list requires sequential access and supports bidirectional traversal, which is the fundamental flexibility of bidirectional linked list operations

implementation

Basic operation of bidirectional linked lists

1. Add elements

Two-way lists, as opposed to one-way lists, can be done in O(1) time, whereas one-way lists require O(n) time.

Add-ons to bidirectional lists include head and tail interpolation. Head:The left side of the list is called the head and the right side is called the tail. The header method fixes the right side, and each new element is added to the left side of the header.

Tail interpolation: The left side of the list is called the head and the right side is called the tail. In the tail insertion method, the left side is fixed, and each addition is at the end of the list on the right.

2. Query element

That’s the flexibility of a bidirectional listKnowing the structure of an element in the list, you can start walking left or right to find the structure you want.Therefore, for an ordered list, the efficiency of the query by value of a bidirectional list is higher than that of a single list. Because we can record the position P searched last time, each time we search, we decide whether to search forward or backward according to the relationship between the value to be searched and the size of P, so we only need to search half of the data on average.

3. Remove elements

In real software development, removing a piece of data from a linked list is one of two things:

• Delete a node whose value is equal to a given value
• Deletes the node to which the given pointer points

For bidirectionally linked lists, nodes in a bidirectionally linked list already hold Pointers to their predecessors, so deletion does not need to be traversed like a single-linked list. So, for the second case, single-linked list deletion requires O(n) time, whereas bidirectional lists require only O(1) time. 4. Bidirectional circular linked listsAs shown in the figure, the concept of a bidirectional linked list is easy to understand: a combination of “bidirectional linked list” + “cyclic linked list”.

Tree 🏈

define

Tree is a kind of data structure, which is composed of N (N >=1) finite nodes to form a set with hierarchical relationship. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down.

• The characteristics of

1. Each node has zero or more child nodes;
2. A node without a parent is called the root node.
3. Each non-root node has one and only one parent;
4. In addition to the root node, each child node can be divided into multiple disjoint subtrees.

The different parts of the tree are called:

• Root Node/parent Node (Root Node/parent Node) : A Node with children under it.
• Leaf nodes: Nodes that have no children associated with them.
• Edges: A link between two nodes.

Some definitions of trees:

• Path: A list of nodes required from the root node to the target node.
• Tree height: The number of nodes that form the maximum path between the root node and the farthest leaf node.

There are different types of trees according to the data structure:

• Binary tree, binary tree is a kind of special tree, add, delete elements are very fast, and in side also has a lot of search algorithm, so the binary tree both the list of benefits, also have the benefits of an array, is optimization of the two, is very useful in dealing with a mass of dynamic data, they are also used to create the binary search tree. One of his potential use cases is compression algorithms. It has the following characteristics:

1. Each node has at most two subtrees, and the degree of each node is at most two.
2. The left and right subtrees are ordered and cannot be reversed.
3. Even if a node has only one subtree, you have to distinguish between the left and right subtrees.

• A binary search tree: also called a binary search tree, ordered binary tree, or sorted binary tree. It is an empty tree or a binary tree with the following properties

1. If the left subtree of any node is not empty, the values of all nodes in the left subtree are less than the values of its root node.
2. If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than or equal to the value of its root node.
3. The left and right subtrees of any node are binary search trees respectively.

• Depth-first search (DFS) : This is a way to find a tree. It works by first traversing the entire left side, then backtracking to the parent that was last accessed, and then moving to the right subtree.

Traversal result: A-> B-> C-> D-> E. The order of the nodes is determined by the DFS method and can be traversed in reverse order.

implementation

Example:

Implement a binary search tree

class BinaryTreeNode {
 constructor(value) {
   this.value = value;
   this.left_child = null;
   this.right_child = null;
 }
 compare(v) {
   if (this.value > v) return -1;
   if (this.value == v) return 0;
   if (this.value < v) return 1; }}class BST {
 constructor() {
   this.root_node = null;
 }
 /* If the root node is empty (the tree is empty), then elem will become the root node. If the elem is lower than the root node, switch to the left child node and check if it is empty. If it is empty, elem will become the left child node. Switch to the right child and check if it is empty if it is, elem becomes the correct child if it is not, continue down this path */
 add(elem) {
   if (!this.root_node) {
     this.root_node = new BinaryTreeNode(elem);
     return;
   }
   let inserted = false;
   let currentNode = this.root_node;
   do {
     let comp = currentNode.compare(elem);
     if (comp == -1) {
       if(! currentNode.left_child) { currentNode.left_child =new BinaryTreeNode(elem);
         inserted = true;
       } else{ currentNode = currentNode.left_child; }}if(comp ! = -1) {
       if(! currentNode.right_child) { currentNode.right_child =new BinaryTreeNode(elem);
         inserted = true;
       } else{ currentNode = currentNode.right_child; }}}while(! inserted); }inorder(parent) {
   if (parent) {
     this.inorder(parent.left_child);
     console.log(parent.value);
     this.inorder(parent.right_child); }}print() {
   this.inorder(this.root_node); }}Copy the code

Use:

const Tree = require("./bst")
const t = new Tree()
t.add(10)
t.add(8)
t.add(11)
t.add(23)
t.add(1)
t.add(9)
t.print()
/* Prints: 1 8 9 10 11 23 */
Copy the code

The most complicated method is Add. It mainly consists of doing a loop through the tree while looking for the location of a new value. The inorder method is just a quick recursive implementation of traversing the order (first left, then center, then right). You can switch the order and go through it in reverse order.

Extension:

Binary tree has a lot of extended data structure, including balanced binary tree, red black tree, B+ tree, etc., these data structure binary tree derived on the basis of a lot of functions, widely used in practical applications, such as mysql database index structure is B+ tree, and HashMap of the underlying source code used in the red black tree. These binary trees are powerful, but algorithmically complex, and it takes time to learn.

Figure 🏂

define

A graph consists of a finite set V of nodes and a set E of edges. In order to be different from tree structure, nodes are often called vertices in graph structure, edges are ordered pairs of vertices, and if there is an edge between two vertices, it means that the two vertices have adjacent relationship.

According to the direction pointed by the vertex can be divided into undirected graph and directed graph: graph is a relatively complex data structure, in the storage of data has a relatively complex and efficient algorithm, respectively, adjacency matrix, adjacency list, cross linked list, adjacency multiple list, edge set number group and other storage structures

• Applicable scenario

Diagrams are very generic because they can be used to represent almost any scenario in which entities are connected. I’m talking about use cases, ranging from network layouts to microservices-based architectures to real-world maps to just about anything you can imagine.

So much so that entire database engines are based on the concept of graphs (Neo4J, for example, is a very popular engine). All of the tree concepts we just covered (edges, nodes, paths, etc.) are still valid here.

implementation

Here is a simple tree, including a way to implement depth-first search traversal (see the Tree section to see what it means).

Example:

class Node {

   constructor(value) {
       this.value = value
       this.links = []
   }
   
   linkTo(node, weight) {
       this.links.push(new Link(this, weight, node))
   }
}

class Link {

   constructor(a, weight, b) {
       this.left = a;
       this.weight = weight
       this.right = b
   }
}

class Graph {

   constructor(root_node) {
       this.root_node = root_node
       this.dfs_visited = new Set(a); }dfs(starting_node) {
       if(! starting_node) starting_node =this.root_node
       let node = starting_node 
       console.log(node.value);
       this.dfs_visited.add(node);
       node.links.forEach( neighbour= > {
           if (!this.dfs_visited.has(neighbour.right)) {
               this.dfs(neighbour.right); }}}})Copy the code

Use:

Each node has a list of “links” that represent the relationship between the two nodes. And you can add values anywhere you want (e.g., ms latency of a network connection, traffic between two locations or just about anything you want). Use the DFS method to traverse the diagram, ensuring that each node is accessed only once. Here’s an example:

// Define a node
let A = new Node("A")
let B = new Node("B")
let C = new Node("C")
let D = new Node("D")
let E = new Node("E")
let F = new Node("F")
let G = new Node("G")

// Define the relationship between nodes
A.linkTo(B, 1)
A.linkTo(C, 2)
B.linkTo(D, 1)
C.linkTo(E, 10)
D.linkTo(E, 10)
D.linkTo(F, 1)
D.linkTo(G, 1)
G.linkTo(G, 1)

let g = new Graph(A)
// Iterate over the chart
g.dfs()
Copy the code

In other words, each node can only be accessed once. You can do more interesting things with graphs, such as implementing Dijkstra’s algorithm to find the shortest path between two nodes, or taking AI routes and implementing neural networks. Imagination is the Graphs limit, so don’t correct them yet and give them a chance.

Hash table 🎉

define

A hash table, also known as a hash table, is a data structure that is accessed directly by key and value. The key and value are mapped to a location in the set, so that the corresponding elements in the set can be found quickly.

Record storage location =f(key)

F is a hash function, and a hash function converts a Key to an integer number through a fixed algorithmic function called a hash function, and then modulates that number to the length of the array. The result is the index of the array. The value is stored in the array space with the number as the subscript. This storage space can take full advantage of array lookup to find elements, so the search is fast. It allows you to store key-value pairs and retrieve them quickly (some would say O (1) best case) and is amazing. HashTable is also quite common in the application. For example, some collection classes in Java are constructed based on hash principle, such as HashMap and HashTable.

• advantages

1. Using the advantages of hash tables, it is very convenient to find elements of collections.

• disadvantages

1. Because hash tables are data structures derived from arrays, they are slow to add and delete elements.

• Applicable scenario

There are many application scenarios of hash table, of course, there are also many problems to consider, such as the problem of hash conflict, if not handled well will waste a lot of time, resulting in application crash. If implemented properly, this structure can be so effective that it is widely used in scenarios such as database indexing (where fields are often set as indexes when quick lookup operations are required), and even cache implementations that allow quick lookup operations to retrieve cached contents. As you might have guessed, this is a good structure if you want to do quick and repetitive lookups.

implementation

In JavaScript, hash mapping is very easy to implement because we have object literals that can be used to add random attributes (i.e. keys). This is to implement a hash map that allows the use of numeric keys.

Example:

class HashMap {
   
   constructor() {
       this.map = {}
   }
   
   hash(k) {
       return k % 10
   }
   
   add(key, value) {
       let k = this.hash(key)
       if(!this.map[k]) {
           this.map[k] = []
       }
       this.map[k].push(value)
   }
   
   get(key) {
       let k = this.hash(key)
       return this.map[k]
   }
   
}

let h = new HashMap()

h.add(10."hello")
h.add(100001."world")
h.add(1."this is a string")

console.log(h)
Copy the code

Use:

The output is as follows

HashMap {
map: { '0': [ 'hello'].'1': [ 'world'.'this is a string']}}Copy the code

Note that to make sure we only have 10 keys at most, my hash method does a spare 10 operation that causes “world” and “this is a string” to be associated with the same key, which is called a hash conflict. This can be helpful if you have limited memory, or need strict keys for some reason. How the hash method is implemented will determine the final effect of the hash map.

Conclusion 🥇

It’s important to understand data structures and use them in everyday tasks, so have some fun with the above implementation and try implementing them yourself

Extension 🏆

If you find this article helpful, check out my other articles at ❤️ :

👍 5 Design patterns to know for Web development 🍊

👍 10 simple tips to make your vue.js code more elegant 🍊

👍 classic interview questions! From entering urls to displaying pages, why don’t you start learning? 🍊

👍 The handshake process of the SSL protocol 🍊

Refer to the article 📜

LeetCodeAnimation

Data Structures You Should Know as a JavaScript Developer