Does javascript have data structures?

There are data structures in JavaScript. Data structures refer to a collection of data elements that have one or more specific relationships with each other. Data structures can effectively manage data objects and improve computing performance. Data structures in JavaScript There are lists, stacks, queues, linked lists, dictionaries, hashes, graphs, and binary search trees.

The operating environment of this tutorial: Windows 10 system, JavaScript version 1.8.5, Dell G3 computer.

Does javascript have a data structure?

javascript has a data structure

Data structure: list, stack, queue, linked list, dictionary, hash, graph And binary search tree

List

In daily life, people often use lists: to-do list, shopping list, best Top ten lists and more. Computer programs also use lists. Select lists are particularly useful as data structures under the following conditions:

The data structure is relatively simple

There is no need to find elements in a long sequence, Or sort it

On the contrary, if the data structure is very complex, the role of the list is not that great.

Stack

The stack is a special kind of list. The elements in the stack can only be accessed through one end of the list. This end is called the stack top. Imagine that the stack of plates we usually see in restaurants is an example of a common stack in the real world. The plates can only be taken from the top. After the plates are washed, they can only be placed on the top. The stack is known as a last-in-first-out data structure. It is an efficient data structure because data can only be added or deleted at the top of the stack, so such operations are fast.

Conditions of use:

As long as the data storage meets the last-in-first-out or first-in-last-out principle, priority will be given to using the stack

Queue

A queue is also a kind of list. The difference is that a queue can only insert elements at the end of the queue and delete elements at the beginning of the queue. Imagine that we are queuing up at the bank, and the people at the front of the line are the first to do business, while those coming from behind have to wait in the back of the line until it is their turn.

Usage conditions:

As long as the data storage meets the first-in-first-out and last-in-last-out principles, priority will be given to using the queue

Common application scenarios:

Queues are mainly used in places related to time, especially in operating systems. Queues are an important mechanism for realizing multitasking.

The message mechanism can be implemented through queues, and process scheduling is also implemented using queues.

Linked list

The linked list is also a kind of list. Why is there a need for a linked list? The main problem with arrays in JavaScript is that they are implemented as objects, unlike other Arrays in languages ​​such as C and Java are relatively inefficient. If you find that arrays are slow in actual use, consider using a linked list instead.

Usage conditions:

Linked lists can be used in almost any situation where a one-dimensional array can be used. If random access is required, arrays are still a better choice.

Dictionary

A dictionary is a data structure that stores data in key-value pairs. The Object class in JavaScript is based on a dictionary. Formally designed. JavaScript can make this dictionary type object easier to use by implementing the dictionary class. The dictionary can realize the common functions of the object and expand the functions you want accordingly. Objects can be seen everywhere in JavaScript writing, so the role of the dictionary It’s also extremely obvious.

Hash

Hashing (also called hash table) is a commonly used array storage technology. Arrays can be inserted or retrieved quickly. The data structure used for hashing is called a hash table. Inserting, deleting, and retrieving data on a hash table is very fast, but it is inefficient for search operations, such as finding the maximum and minimum values ​​in an array. These operations require recourse to other data structures, such as the binary search tree described below.

Hash tables can be designed based on arrays in JavaScript. The length of the array is preset, and all elements are stored in specific locations in the array according to the key corresponding to the element. The keys here and the keys of the object are the concept of type. When using a hash table to store an array, a hash function maps the key to a number that ranges from 0 to the length of the hash table.

Even if an efficient hash function is used, it is still possible for two keys to be mapped to the same value. This phenomenon is called a collision. Common collision processing methods include: open chain method and linear detection method (those who are interested in specific concepts can confidently learn about them online)

Conditions of use:

can be used for data insertion, deletion and retrieval. Used, not suitable for finding data

图

The graph consists of a set of edges and a set of vertices. Maps are very common real-life scenes around us. For example, every two towns are connected by some kind of road. Each town above can be regarded as a vertex, and the roads connecting the towns are edges. An edge is defined by a pair of vertices (v1, v2), where v1 and v2 are the two vertices in the graph. Vertices also have weights and become costs. If the vertex pairs of a graph are ordered, it is called a directed graph (such as a common flow chart), otherwise, it is called an unordered graph.

Usage scenarios (use graphs to model real-life systems):

In transportation systems, vertices can be used to represent street intersections, and edges can be used to represent streets. Weighted edges can represent speed limits or the number of lanes. The system can be used to determine the best routes and which streets are most likely to be jammed.

Any transportation system can be modeled using graphs. For example, airlines can use diagrams to model their flight systems. Consider each airport as a vertex and each route passing through two vertices as an edge. Weighted edges can represent the cost of a flight from one airport to another, or the distance between two airports, depending on what is being modeled.

There are two main algorithms for searching graphs: depth-first search and breadth-first search.

Binary tree and binary search tree

Tree is a data structure often used in computer science. A tree is a non-linear data structure that stores data in a hierarchical manner.

Each node of a binary tree is not allowed to have more than two child nodes. The two child nodes of a parent node are called the left node and the right node respectively. By limiting the number of child nodes to 2, efficient programs can be written to insert, search and delete data in the tree.

Binary Search Tree (BST) is a special binary tree in which relatively small values ​​are stored in the left node and larger values ​​are stored in the right node. This feature makes searches very efficient, both for numeric and non-numeric data, such as words and strings.

Binary search tree implementation method

function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 显示树的数据
  return this.data
}
function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}
function insert (data) { // 向树中插入数据
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
  parent = current
  if (data < current.data) {
current = current.left;
if (current == null) {
  parent.left = n;
  break;
}
  } else {
current = current.right;
if (current == null) {
  parent.right = n;
  break;
}
  }
    }
  }
}

There are three ways to traverse BST: in-order traversal (access all nodes in the tree in ascending order, first visit the left node, then visit the root node, and finally visit right node), pre-order traversal (visit the root node first, and then access the left and right nodes in the same way), post-order traversal (visit the leaf nodes first, from the left subtree to the right subtree, and then to the root node)

【Related recommendations: javascript video tutorial, web front-end】

The above is the detailed content of Does javascript have data structures?. For more information, please follow other related articles on the PHP Chinese website!