[Data Structures] Creation of a single linked table – head insertion and tail insertion
[Data Structures] Creation of a single linked table – head insertion and tail insertion.
Building a single linked table
When we are ready to implement a linear table in the form of a single linked table, then the first step we need to take into account is the creation of the single linked table, which is the process of initialization. Because the chained table is a dynamic structure, it does not need to pre-allocate space, so the process of generating the chained table is a node by node “insertion” process, and the node insertion position is our choice, so according to the position of the node insertion of the single-chained table can be divided into the head insertion method and the tail insertion method.
①Head insertion method
The official description of this algorithm is: start from an empty table, repeat the read data, generate a new node, store the read data into the data field of the new node, and then insert the new node into the current linked table after the head node.
The point here is that each time a new node is generated, it is connected to the head node, and each new node is inserted in front of the original first node. The chained table created by this method is later-first, i.e., the chained table is in reverse order. Therefore, when a topic asks us to implement a reverse-order representation of a linear table, we should first consider the head insertion method.
The diagram shows:
Where pointer H always points to the head node and pointer s points to the new node. ① means initializing the empty table ② means applying for a new node and assigning a value ③ means inserting the first node ④ means inserting the second node (④-1 and ④-2 represent the order of precedence). The whole process shows the basic principle of header insertion.
The corresponding algorithm is:
2. Tail insertion
The official description of this algorithm is: start from an empty table, repeat the read data, generate a new node, store the read data into the data field of the new node, and then insert the new node into the current chain table after the end node.
The point here is that a new node is generated by inserting it directly into the end of the current singly linked table, i.e., by having the last node point to the new node. This is one of the most basic ways to grow the length of a linked table. Later comes later, and the resulting chained table is sequential.
The diagram shows:
Where pointer H always points to the head node, pointer s points to the new node, and pointer r always points to the end of the single linked table. ① means to initialize the empty table ② means to apply for a new node and assign a value ③ means to insert the first node ④ means to insert the second node (④-1 and ④-2 represent the order of precedence)
The whole process of the illustration shows the basic principle of the tail insertion method.
The corresponding algorithms are:
After analyzing the header and tail insertion methods, it is time for the classic problem of identifying the time complexity of both.
Head insertion method:
Each node: only need to move itself and the pointer to the head pointer can be moved, do not need to move the other elements, and actually have no relationship with the other elements, so the time complexity of a single node is O (n).
The whole chain table: set the total length of the single chain table is n, in a single chain table has n elements insert elements, if the insertion position is x then need to find its predecessor can be inserted, the worst time complexity is O (n), time complexity is also O (n)
Tail insertion:
Each node: only need to move a little bit of its own and the tail pointer pointing to No other elements need to be moved, and there is no relation to other elements, so the time complexity of a single node is O(1).
The whole chain table: let the total length of the single chain table is n, insert an element in a single chain table that already has N elements, if the insertion position is x then you need to find its predecessor before you can insert it, the worst time complexity is O (n), the time complexity is also O (n).
Thinking map:
The most complete self-study guide to computer fundamentals!
The most complete self-study guide to computer fundamentals is as follows:
1, data structures and algorithms
Programs = data structures + algorithms.
Data structures are often put together with algorithms, and in some colleges and universities, there are two courses, “Data Structures” and “Algorithm Design and Analysis”.
This has caused many students to be confused, what is the difference between data structures and algorithms? Some students even think that it is a kind of.
In fact:
Data structure mainly explains the organization of data. It is how we are going to store this data, so there are arrays, chain lists, stacks, queues, trees, graphs, which is the focus of data structures.
Algorithms, on the other hand, focus on ideas. For example, how to sort the elements in the array, how to find the largest number and the smallest number and so on. To put it bluntly, it’s the idea of solving problems in reality. That’s why there are these algorithms like greedy, dynamic programming, etc.
Data structures and algorithms, no matter how you think, must be seriously learn! It’s a must for both interviews and grad school!
The following summarizes some important knowledge points, so that you can have targeted learning.
[Complexity analysis]
Time complexity
Space complexity
Learning data structures and algorithms of the first lesson, I always choose complexity analysis, in my opinion, this is the most important data structures and algorithms in the most important knowledge points, and do not accept any refutation.
Article recommendation:
Nanny Teaching! Thoroughly learn time complexity and space complexity
[Data Structure]
Array: An array is an aggregated data type, which is a collection of a number of variables with the same type organized in an orderly fashion.
LinkedList: A linked list is a data structure in which data elements are stored according to a chained storage structure that is characterized by physical discontinuities.
Stack: Stack is a special kind of linear table, it can only be in a table at a fixed end of the insertion and deletion of data nodes.
Queue (Queue): queue and stack are similar, is also a special linear table. Unlike a stack, a queue only allows insertion operations at one end of the table and deletion operations at the other end.
Hashtable: Hashtable is derived from the hash function (Hashfunction), the idea is that if there is a record in the structure of the keyword and T is equal, then the record must be found in the storage location of F (T), so that you can directly obtain the record without comparison.
Heap: Heap is a special kind of tree data structure, generally discussed heap is a binary heap.
Tree: Tree is a typical non-linear structure, it is including, 2 nodes of the poor set K.
Graph: Graph is another non-linear data structure. In a graph structure, data nodes are generally called vertices and edges are ordered even pairs of vertices.
[Manipulating Data Structures]
Find: Finding a node in a data structure that satisfies certain conditions. Generally, given a value of a field, find the node with that field value.
Insert: add a new node to the data structure.
Delete: removes the specified node from the data structure.
Modify: changes the value of one or more fields of the specified node.
Sort: rearranges the nodes in some specified order. For example incrementing or decrementing.
[Data Structure Books Recommended]
Data Structures, Data Structures and Algorithm Analysis
Data Structures is a book that is more interesting and easy to read, and the algorithms are explained in detail compared to similar data structure books on the market.
It is a great read for self-study.
This book is narrated in a fun way, with a lot of references to a variety of life knowledge to analogize, and fully utilizes the graphical language to reflect the abstract content, and some of the classic algorithms involved in data structures to do line-by-line analysis, multi-algorithm comparison.
If you still can’t understand, you can look at the diagrams I wrote, but it’s a bit slow, but absolutely easy to understand:
Arrays: Eggs suffered an arrays Waterloo, and the interviewer suggested to go back to the village to raise pigs.
Chained table: chained table, draw a few times on the whole understand!
Stack and queue: tie! “Stack” live, queue!
Strings: Do you know this about strings?
[Algorithms]
The formula for learning algorithms is simple: read more, write more, and get on the computer more.
Backtracking algorithms
Partitioning algorithms
Enumeration algorithms
Greedy algorithms
Dynamic programming
Finding algorithms
Dichotomous finding
Hash table finding
Tree structure finding
String matching
String matching
Brutal matching
KMP Algorithm
Top 10 Sorting Algorithms
Bubbling Sort
Selection Sort
Insertion Sort
Hill Sort
Parametric Sort
Hex Sort
Hex Sort
Rapid Sort
Count Sort
Base Sort
Bucket Sort
Bucket Sort
[Recommended Algorithm Books]
Algorithms Illustrated
Example-rich and richly illustrated, this is an introductory algorithm book that reads like a novel.
Whether you are a professional programmer, a programming enthusiast, or a computer science major who needs to revisit algorithms, this is the book for you.
The first three chapters of the book will help you lay the groundwork, taking you through binary lookups, big-O representations, two basic data structures, and recursion.
The remainder of the book will focus on algorithms with a wide range of applications, specifically: solution techniques when faced with specific problems, such as when to use greedy algorithms or dynamic programming; applications of hash tables; graph algorithms; and the Kzui nearest neighbor algorithm.
Algorithms (4th Edition)
The classic reference in the field of algorithms contains the core body of knowledge on algorithms that has evolved over decades.
The book explains a wide range of algorithms and data structures, enabling you to implement, debug, and apply them in a variety of computer environments.
A classic reference in the field of algorithms, it provides a comprehensive introduction to the essential knowledge about algorithms and data structures, with special treatment of sorting, searching, graph processing, and string processing
The 4th edition specifically gives 50 algorithms that every programmer should know and know how to do, with actual code provided.
[Video Tutorial Recommendation]
“Data Structures”, co-taught by ZJU professors Chen Yue and He Qinming, the course is great system is complete, the class experience is good, while the difficulty factor is online, the quality is also very good. Can learn a lot of thinking methods and skills, want to learn a good data structure students should not miss.
“Data Structures and Algorithms”, the most important feature of this course is the combination of theory and practice, you will learn the algorithmic skills to solve a variety of computational problems and implement about 100 algorithmic coding problems.
[Website Recommendation]
If you still find it overwhelming to learn, you can take the help of the following website.
VisuAlgo, a dynamic visualization site for data structures and algorithms.
[Brush]
Data structures and algorithms learning, often accompanied by “brush”, if there are no special circumstances, I recommend that we brush LeetCode is good.
For LetCode, there are many solutions to the problem, and we tend to pursue the optimal solution. Here is a copy of the optimal solution of LetCode organized by the president of Tsinghua University, which is highly recommended:
The two should work together to make it very comfortable.
2, the principle of computer composition
The principle of computer composition, that is, “computer” “composition” of the “principle”.
I think it is the most difficult of all basic computer courses, the core of the entire course is to use digital logic circuits and triggers to build a machine that can run assembly instructions.
[Book recommendation]
How Computers Run, How Programs Run.
It’s precisely because Computer Composition Principles is so difficult to learn that the choice of introductory books for beginners has to be friendlier for this class than for a few others.
“How Computers Run” and “How Programs Run”, which are two very thin books where the authors present their knowledge in a big vernacular, illustrated, and quite NICE for beginners.
“How Computers Run”
“How Computers Run”
This book advocates a return to the computer in a world where computers are rapidly evolving, and where technology continues to be revolutionized. to the basics. By exploring the nature of computers, it promotes engineers’ interest in computers and their ability to quickly grasp the essentials and apply them flexibly when confronted with the complexities of the latest technology.
How Programs Work
This book starts with the internal structure of a computer and explains in detail, with illustrations and text, binary, memory, data compression, source and executable files, the relationship between the operating system and the application program, assembly language, and hardware control methods, with the aim of letting the reader understand what happens between the time the user double-clicks on a program’s icon and the time it starts to run. What really happens.
[Video Recommendation]
The first video in Carnegie Mellon University’s Deeper Understanding of Computer Systems series. It doesn’t matter, there are Chinese and English subtitles, after watching this set of videos, the knowledge + sixth grade smoothly get hand.
Watch this video supporting textbook is “Deeper Understanding of Computer Systems”.
3, operating system
No matter what language you study, you can’t avoid dealing with the operating system. The final execution of all the language, are relying on the operating system. For example, if you learn Java and use multithreading technology, the operating system is actually responsible for managing processes and threads.
Without understanding the operating system, you will be confused when you learn the advanced features of programming languages in the future, when it comes to threading, process scheduling, memory allocation, or when you learn about Linux.
Only if you learn the operating system, you will be able to learn other languages and technologies better. Therefore, the operating system is a must for programmers to advance their knowledge.
[Book Recommendations]
Recommendations for getting started: Introduction to Operating Systems, Modern Operating Systems.
In-depth series: “In-depth understanding of computer systems”, to understand computer systems from the programmer’s point of view.
This is an introductory level book, which is not really “in-depth”, it talks about relatively shallow content.
The “breadth of coverage” is really the best thing about this book. It tells us how computers are designed and work, what the operating systems focus on, and what they do.
After taking a look at this book, we can have a rational understanding of how the components of a computer system work. To a certain extent, it is actually an exercise in thinking – computational thinking.
[Video Recommendations]
Operating system, to be honest, in the beginning of learning is not recommended to directly bored to read the book. Because the book looks really meaningless.
Here we recommend Tsinghua University’s operating system course, divided into upper and lower. When you watch the video, you can combine it with the [book recommendation] above.
When you watch (upper), you can combine it with Introduction to Operating Systems, and when you watch (lower), you can combine it with Modern Operating Systems.
4, computer networks
Computer networks related knowledge used more often at work.
Learning computer networks, you need to know Socket programming, know the TCP/IP network model, understand the OSI seven-layer network architecture, know how a packet of data layers of packaging, and then layers of unpacking, from the client to the server.
But computer networks are much better, because they are not abstract, in real life, can find examples.
[Book Recommendation]
“HTTP”
The illustrations, simple and easy to understand, very suitable for the beginning. It’s not easy to write a book that is thin and readable and covers the major areas of knowledge. This book does that and does it quite well from the level of coverage of HTTP knowledge to the ease of reading.
This book features a large number of vivid communication illustrations to help readers better understand the interaction between the client and the server during HTTP communication.
Computer Networks
The vast majority of them are using Xie Xiren’s book Computer Networks, which is very good and easy to understand, and is also a common textbook for the 408 exam.
[Video Recommendation]
First of all, we must strongly push the computer network microclassroom of the University of Lake Teachers, a moving picture to do the best computer network video course, the teacher lectures logical and clear and especially easy to understand.
5, database
Database is the place to store data, but it is not just that simple.
Learning database, not only to understand the SQL statement, table design structure of these basic parts, but also understand the index, slow query optimization, configuration parameters tuning.
A little more in-depth, but also to learn SQL optimization, backup and recovery, architecture optimization and other advanced content.
[Book Recommendations]
Introduction Series: SQL Basic Tutorial, SQL Study Guide, Introduction to Database Systems.
This book introduces a more gentle pace, and with illustrations and keywords bold more vivid introduction to knowledge, suitable for zero-basic students.
For those with no prior knowledge, Mick’s sql basics is easier to read and learn, and is ideal for beginners.
In-depth series: “MySQL Technology Insider – InnoDB Storage Engine”, “Redis Design and Implementation”.
Algorithms and Algorithm Analysis of Data Structures[2]
Algorithms and data structures are complementary to each other, the algorithms for solving a particular type of problem can be selected from a variety of data structures, and the choice of the appropriate or not directly affects the efficiency of the algorithm, and vice versa, the advantages and disadvantages of a data structure by the implementation of a variety of algorithms
To design a good algorithm, it is usually necessary to consider the following Requirements
(1) the correct algorithm should meet the pre-specified functionality and performance requirements
(2) readable an algorithm should be clear and hierarchical, simple and easy to read and understand
(3) robust when the input of illegal data should be able to deal with it appropriately does not give rise to serious consequences
(4) efficient and effective use of storage space and a high degree of time-efficiency
(4) the efficient use of storage space and time-efficiency
The design of a good algorithm usually takes into account the following requirements Algorithm description
Algorithms can be described in a variety of ways
The simplest way is to use natural language to describe an algorithm The advantage of using natural language to describe an algorithm is that it is simple and easy for people to read the algorithm The disadvantage of using natural language is that it is not rigorous enough
You can use algorithmic descriptors such as the program flowchart, the NS diagram and other algorithmic descriptors which feature a simple and concise process
The algorithmic descriptor can be used in the following ways The algorithms described in these two ways cannot be directly executed on a computer, and there is a programming problem in converting them into executable programs
The algorithms can be described directly in a programming language, but it is not easy to use a programming language directly, and it is not very intuitive, and often you need to resort to annotations in order to make it understandable
The algorithms can be described by using some kind of programing language. lishixin/Article/program/sjjg/201311/23944