Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "what are the data structure knowledge points of the front end of web". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1) what is an algorithm?

An algorithm is the step of calculating or solving a problem.

2) what is the difference between algorithm and program?

The difference is that the program is written in a programming language that the computer can understand and can run on the computer, while the algorithm is described in a mathematical way that humans can understand and is used before programming. However, algorithms and programming have no specific boundaries.

3) how to choose the algorithm?

Different developers have different solutions to the same problem, and different programming languages have different writing methods. The purpose of setting up evaluation criteria for the algorithm is to select the algorithm with the best standard. There are two criteria for judging the quality of the algorithm: one is the amount of space it takes from running to calculating the result, and the other is how much time it takes from running to calculating the result. They are called space complexity and time complexity respectively. In general, the lower the complexity, the less memory is consumed, the faster the execution, and the easier it is to be understood. Generally speaking, the most important thing is the running time of the algorithm.

4) how to reflect the running time of the algorithm?

Different algorithms, different devices and different amounts of data will lead to differences in algorithm time. The running time calculated by theory is a polynomial, and we need to be able to most intuitively understand the relationship between time and the amount of data. We often ignore non-important items and get the simplest expression that best reflects the trend of running time. We write "O (n)" in the form of ignoring unimportant items and minimizing the relationship between running time and the amount of data, where O is uppercase, which means ignoring other important items, and its pronunciation is the same as order. N represents the amount of data participating in the algorithm.

Data structure

Why should there be multiple data structures?

Depending on the purpose of use, using different data types can provide memory space utilization.

1) linked list

Linked list is one of the data structures, whose data is arranged linearly; in memory space, the data is scattered in memory, and each data is composed of two parts, one is the data itself, the other is a pointer, it points to the next storage space. When accessing data, you can only follow the pointer to access one by one until you find it or access it to the end. If the amount of data in the linked list is n, then you need to find a data as soon as possible and need to find it at most n times; when you need to add or delete a data in the linked list, you only need to change one or two of the data pointers, which has nothing to do with the amount of data in the linked list and is of constant order.

Summary:

The linked list data is linear, the storage space is discontinuous, the time complexity of access is O (n), and the time complexity of adding and deleting is O (1).

Expand:

Circular linked list: the data at the end of the linked list has no pointer. When a pointer to the head of the linked list is added to the tail data, a circular structure is formed between the pointers of the linked list, which is called circular linked list or circular linked list.

Bi-directional linked list: a bi-directional linked list is formed when the internal pointer of the linked list can point to the next data from the previous data as well as from the latter element.

Note here: when giving the definition, it is said that the data consists of the data body itself and the pointer, and when the pointer increases, the storage space required for the data will also increase, which will take up more memory. At the same time, when there are more pointers, when adding or deleting data, the more complex the pointers need to be changed, and the more pointers that need to be changed.

2) Array

Array is also one of the linearly arranged data structures, which differs from linked lists in that arrays are stored continuously in memory space. When accessing the array, you only need to find the corresponding position according to the array index, and the search complexity is constant, which is expressed as O (1). When increasing the array, if you increase the array header, you need to expand the array first. Then move each element backward in turn, the complexity of the process is O (n), and if you add an element to the end of the array, the complexity becomes O (1). Similarly, delete an element, O (1) when the tail is deleted, and O (n) when the head is deleted. As you can see, compared with the linked list, although the array query is convenient, but the operation complexity is high.

3) Stack

Stack is a linear data structure, when adding an element to the stack, this element is added to the top of the stack. When the element is taken out, it can only be read from the front position one-way, and then the later elements can be read. That is to say, the last addition is the first to be read. Therefore, the stack is called last-in, first-out (LIFO) mode, and the way of adding and deleting data is also known as entering and leaving the stack. Because of the LIFO characteristics of the stack, it is often used to keep the latest data.

4) queue

The queue is also a linear data structure, much like the stack, it is an one-way orderly operation, but the queue is like a queue, first-in, first-out, FIFO, first-in, first-out, first-in, first-out Adding and removing queues are also known as queuing and dequeuing.

5) Hash table

Hash tables store data combined by key-value pairs. generally, the key is regarded as the identification of the data, and the value is regarded as the content of the data. The hash table is usually used in combination with the hash function. In the process of establishing the hash table, you need to use the hash function to calculate the hash value of the data and store it in the array, so that you can quickly access it using the characteristics of the array when you access it. If there are multiple values in the same array position when creating the array, use the linked list to store the same value again.

The use of hash table accelerates the speed of array query and has great advantages in flexibility and efficiency. In programming, hash tables are often used when associating arrays.

6) heap

Heap is a kind of graph, which is a two-dimensional data structure, which can be represented by a two-bit tree diagram. The data value of the child node is always larger than that of the parent node. In the heap, the data at the top is always the smallest, so no matter how much data is available, the complexity of fetching the minimum is always O (1). In addition, because it is necessary to move the final data to the top after fetching the data, and then comparing it with the size of the child node data, the running time required to extract the data is proportional to the height of the tree. Assuming that the amount of data is n, according to the shape and characteristics of the heap, the height of the tree is log2n, then the complexity of the reconstructed tree is O (logn). The same is true of adding data at the end of the heap, which compares it with the size of the parent node and moves up until the conditions of the heap are met.

If you need to frequently extract the minimum value from the data, then the heap is a good choice.

7) binary search tree

A binary search tree is also called a binary search tree, or binary sort tree. It is a kind of two-dimensional graph structure. Its characteristic is that each node has at most two nodes, which are called left subtree and right subtree respectively. The value on each node is greater than that on its left subtree, and the value on each node is less than that on its right subtree.

According to these two characteristics, we can know that the minimum value of binary search tree should be found at the lower left end, and the maximum value should be found at the lower right end.

Which data structure should be selected according to the purpose of use, the front end is commonly used for the above 7 kinds.

This is the end of the content of "what are the knowledge points of the data structure of the front end of web". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.