Introduction to front-end algorithms – Data structures

Basic Knowledge

1) What is an algorithm?

An algorithm is a step to calculate or solve a problem.

2) What’s the difference between an algorithm and a program?

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

3) How to select the algorithm?

For the same problem, different developers solve it differently, different programming languages, different writing methods, the purpose of setting criteria for algorithms is to choose the algorithm of the best standard. There are two criteria to judge whether an algorithm is good or bad: one is how much space it takes to calculate the result from running, and the other is how much time it takes to calculate the result from running. They are called space complexity and time complexity. In general, less complexity, less memory, faster execution, and easier to understand. In general, the most important thing is the running time of the algorithm.

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

Algorithm is different, different equipment, different amount of data will result in algorithm of time difference, the running time is calculated through the theory of a polynomial, and we need to be able to get the most intuitive understanding to time with the amount of data, the relationship between change often ignore the important items, get one of the most simple and most can reflect the trend of running time expressions, we put the: Omit the unimportant items and write it in the form of O (n), where O is uppercase and means to ignore the content other than the important items. It is pronounced as order. N represents the amount of data participating in the algorithm.

The data structure

★ Why multiple data structures? Different data types can be used to provide the memory space utilization.

1) list

Linked list is one of the data structures, its data is linear arrangement; In memory space, data is stored in memory, each data is composed of two parts, one part is the data itself, and the other part is a pointer to the next piece of storage space. When accessing data, you can only follow the pointer to access one by one until you find or access to the end. If the amount of data in the list is N, then, to find a data, the fastest need to search once, at most need to search n times; When you need to add or delete a data in the list, you only need to change one or two of the data Pointers, and the list of data is irrelevant, is constant level. Summary: The linked list data is linear, the storage space is discontinuous, the time complexity of access is O(n), the time complexity of adding and deleting is O(1). Extension: circular list: the list of the tail of the data is not a pointer, when the tail data to add a pointer to the list of the head of the data, the list pointer between the formation of a ring structure, known as circular list or circular list. Bidirectional linked list: When the internal pointer to the list can point from the previous data to the data can also point from the latter element to the previous data, a bidirectional linked list is formed. Note that the definition states that data consists of the body itself and the pointer. As the pointer increases, the data needs more storage space and consumes more memory. At the same time, when the number of Pointers is larger and data is added or deleted, the number of Pointers that need to be changed is more complex and the number of Pointers that need to be changed is more.

2) array

Arrays are also linear data structures. Unlike lists, arrays are stored contiguously in memory. When accessing an array, you only need to find the corresponding position according to the array index. The search complexity is constant, expressed as O (1). If the array header is added, the array must be expanded first. Then we move each element backwards in order of complexity, which is O (n). If we add an element to the end of the array, the complexity becomes O (1). Similarly, if we delete an element, the end is O (1), and the head is O (n). As you can see, compared to the list, although the array query is convenient, but the operation complexity is high.

3) stack

Stack is a kind of linear data structure, when for the stack to add an element, the element is added to the top of the stack, when remove elements, only one-way read from the front position, and then you can read the back of the elements, that is to say, the last is added, it is the first to be read, therefore, the stack is called last in, first out (LIFO) model, The way data is added and removed is also known as pushing and pushing. Because of the LIFO nature of the stack, it is often used to hold the latest data.

4) queue

Queue and the data structure of the linear structure, it is very similar to the stack, is a one-way operation in order, however, lifo, and queue like waiting in line, the first row in front, and then the row behind, belong to the first in first out (FIFO), to allow access to the back of the element, only finished all the elements in front of the visit, to access to the target element. The operations of adding and removing queues are also known as enqueuing and dequeuing.

5) Hash table

Hash tables store data in pairs of keys and values, generally using the keys as the identity of the data and the values as the contents of the data. Hash table is usually used in combination with hash function. In the process of building hash table, we need to use hash function to calculate the hash value of data, and store it in an array, so that when accessing, we can quickly use the characteristics of array to access; If there are multiple values in the same array location at the time of array creation, the linked list is used to store the same values again. The use of hash table accelerates the speed of array query and has great advantages in flexibility and efficiency. In programming, associative arrays often use hash tables.

6) heap

Heap is a kind of graph, which is a two-dimensional data structure. Its diagram can be represented by a two-position tree graph. The data value of the child node is always larger than the parent node. In the heap, the data at the top is always the smallest, so the complexity of fetching the minimum is always O (1), no matter how much data there is. In addition, since it is necessary to move the last data to the top after fetching data, and then move it down while comparing its size with that of the child node data, the running time required for fetching data is proportional to the height of the tree. Assuming that the amount of data is N, according to the shape characteristics of the heap, The height of the tree is log base n, so the complexity of the refactoring tree is order log base n. The same goes for adding data. You add data at the end of the heap, and the data moves up as it compares its size with that of its parent until the heap conditions are met. If you need to frequently extract minimum values from the data, then the heap is a good choice.

7) Binary search trees

A binary search tree is also called a binary search tree, or a binary sort tree. It’s a two-dimensional graph structure. Its characteristics are as follows: each node has at most two nodes, respectively called the left subtree and the right subtree. The value on each node is greater than the value on the left subtree, and the value on each node is less than the value on the right subtree. According to these two characteristics, we can know that the binary search tree to find the minimum value to the bottom left end, to find the maximum value to the bottom right end.

summary

Which data structure should be selected according to the purpose of use to determine, the front end commonly used for the above 7, specific how to use these data structures flexibly? What can be done? Let’s do the next video.

At the end of the article

It is not easy to summarize and sort out, but after reading it, it is helpful to like and follow it, and the platform will recommend more high-quality articles on similar topics.

Preparing for an interview? To communicate, every day to interview questions to improve themselves; Ready for advanced full stack? Let’s talk about the path to progress, less detours; Tired of typing code? Come to the group chat, make work more efficient.

Due to the restriction, the current number is over 200, can only be invited to join, so, please search the public number [front advanced interview push], I invite into the group. Come here, find more like-minded front end partners ~