The method of self-study of data structure: first, in the first stage, understand the data structure, understand the basic composition and performance; then in the second stage, go deep into the data structure, master the relevant characteristics, and be able to write code; finally, in the third stage, retrieve the data structure, Apply the knowledge points learned to practical problems.
How to self-study data structure:
The first stage: understanding the data structure
Step one:To learn it, you should know what the 10 data structures of arrays, linked lists, stacks, queues, hash tables, jump tables, graphs, trees, heaps, and dictionary trees are used for. Why and how to do it? Xiaolu recommends reading some basic data structure books or using Baidu and Google to briefly understand what each data structure is used for, why and how to do it, and then you can simply take notes and blog.
Second step: Each data structure has its advantages, disadvantages and performance. So what standards do we use to measure the performance of data structures and algorithms? The second step is to learn the content of complexity analysis related to time complexity and space complexity. This part of the content is very important, because the data structures and algorithms to be learned later must have a performance standard. In order to be able to differentiate Problem solving selects data structures and algorithms with the best performance.
The second stage: in-depth data structure
The first step: write code. The ten most basic data structures related characteristics and usage conditions have been noted above. Then we will conduct an in-depth study of each data structure from the beginning. First, the operations involved in the data structure, such as adding, deleting, modifying, checking and other operations are required. Implement it yourself and run it on the machine. When writing code, you must pay attention to the following points: boundary conditions, pointers, and code specifications.
This will make you more in awe of the code. You should take it seriously every time you write code. If there is no problem writing the code on the machine, you can do it yourself by handwriting it with a pen on your notebook. , which will help you deepen your understanding of the logic of your code.
Second step: In the first stage we learned about the performance measurement standards, then the next step will be to go back to the 10 most commonly used data structures involved. Perform performance analysis of operations. You may ask, why not perform performance analysis while writing code? I think the advantage of stages is that we can focus on solving problems. Writing code is to exercise the thinking and logic ability of writing code. Performance analysis is to improve one's analysis ability. After the performance analysis is completed, let's take a look at the code written before and which can be optimized. improved. During this period, you will encounter various problems. When encountering problems, I usually go to Baidu or Google to summarize and record them in my notebook with the help of articles written by others.
The third step: After the performance analysis of each data structure is completed, proceed with in-depth analysis of each data. What I recommend in the first stage is to read some basic books, which do not involve a deep level of knowledge. But we still need to have at least one data structure book with authoritative and in-depth analysis in order to have an in-depth understanding of some concepts. After all, basic books are meant to get you started. We can use these authoritative and comprehensive content to check for gaps in the data structure knowledge points we have learned.
Step 4: What if in-depth learning alone is really boring and complicated? Then we will analyze examples from real life, such as guessing numbers games, 0/1 knapsack problems, Maze walking, eight queens problem, full minus sum single problem, etc. For example, in a number guessing game, we can think about how to guess the correct number in the shortest time. You may think of using binary search. Okay, let’s ask ourselves the problems with binary search. During this process, you must ask yourself why. Only in this way will your knowledge level be expanded. For example, if there is duplicate data in the binary search, how to solve it?
I still want to emphasize that you must ask yourself why, because psychologically speaking, the human brain conforms to the principle of least resistance, that is, thinking is the least favorite thing to do, so here we have to go in reverse. , can further breakthroughs be made. If you feel that there are no problems in the above two stages, we will proceed to the third stage below to retrieve the data structure.
The third stage: retrieval of data structure
The first step: At this time you may learn a lot about data structure, But it is difficult to apply, so how can it be applied in actual practical problems? Have we already organized the fragmented knowledge points into our notebooks? What to do next? We can use mind maps to systematically organize knowledge, which will help us further strengthen whether it is review or consolidation.
Second step:After organizing the above into a system, then go to Google or Baidu to search for actual problems with clear solutions and use them for analysis and study. You will find in these actual projects, Many problems involve multiple data structures. What we solved before was only for a single data structure. Then try to establish a connection between data structures yourself, such as arrays and linked lists. Each data structure has its advantages and disadvantages. In the process of learning, you will find that the advantages of one data structure are exactly the disadvantages of another data structure. Arrays are continuous in memory space and are friendly to CPU cache, while linked lists are fragmented memory space in memory and are not good for CPU cache. Friendly, but linked lists can be dynamically expanded but arrays cannot.
For another example, in order to improve the efficiency of the program, we have to replace another data structure with a data structure that consumes more memory space. If the memory is tight and the execution efficiency is not high, we can use the memory-saving execution efficiency A slightly lower data structure replaces a data structure that takes up a lot of memory and executes quickly.
Step Three: Learn to convert actual problems into the data structures you have learned. How to convert it? For example: If you were an engineer, how would you solve the problem of optimizing the algorithm for caching linked lists? Let's first convert the problem into the data structure we have learned, which mentions linked lists. Now we know that there are linked lists. What operations are implemented using linked lists? Eliminating data, searching data, and caching data all involve searching. We have to traverse the entire linked list, and the time complexity is O(n).
Then we wonder if we can optimize the search? Find an applicable data structure based on the characteristics of the problem or data. The three operations of caching involve fast insertion, deletion, and query of data. What are the data structures that we can quickly retrieve, delete, and query in our brains? Balanced binary trees, hash tables, skip tables, etc. For example, if we choose a hash table, we will finally analyze whether the time complexity has been optimized a lot, otherwise we will change to another data structure for performance analysis.
It is not difficult for us to find that the actual problem will be decomposed step by step into the basic operation analysis of the data structure we learned, and then use the advantages, disadvantages and performance analysis of the data structure we learned to obtain the optimal There are no solutions, but the actual problems encountered in enterprises are often more complicated than the actual problems we use for practice.
Related recommendations: Programming video course
The above is the detailed content of How to learn data structure by yourself. For more information, please follow other related articles on the PHP Chinese website!