Basic knowledge is like the foundation of a building, it determines the height of our technology. And want to do something quickly, the premise must be the basic ability is excellent, “internal work” to be in place. — Beauty of data structures and algorithms
This paper summarizes some concepts of basic data structures and algorithms, as well as the characteristics, advantages and disadvantages of some common basic data structures. Only by understanding the meaning of the existence of each data structure; When you encounter a problem, you have the ability to choose the data structure and the solution that best suits you.
Some simple concepts of data structures and algorithms
- What is a data structure
A data structure is the way a computer stores and organizes data. It is a collection of data elements that have one or more specific relationships with each other.
To put it bluntly, that’s how data is stored.
We know that data is stored for a purpose, to facilitate subsequent reuse of the data. Storing worthless data is playing tricks on storage space. And in storage, what does data look like? It couldn’t have been misplaced, otherwise how would you find it when you wanted to use it? That’s what data structures are for.
Then the problem arises. In this case, wouldn’t it be more convenient to store all data as a data structure? Using an array [2,3,5,6] as an example, it is perfectly fine to store such a piece of data; But if you use an array to store the father,brother,sister data, the data store is fine, but how can you represent the logical relationship between the data? If not reflected, the use of late nature is also a big problem. Therefore, there are a lot of existing data structures, and each has its own unique characteristics, master these characteristics, can better solve the problem.
- What is time complexity and what is space complexity
- Time complexity refers to the amount of work required to perform the algorithm
- Spatial complexity refers to the amount of memory required to perform this algorithm
So the idea of both is a little bit easier to understand, but what is the complexity of the algorithm? Or how is it represented? This is the big O notation.
- Big O notation
- The big O notation tells you how fast the algorithm is. For example, suppose a list contains n elements. Simple lookup requires checking each element, so n operations are performed, and the algorithm runs in O(n) time. The unit? No — the big O notation does not refer to speed in seconds. It tells you how fast the algorithm is running.
- So how do you think about how fast the algorithm is going to run? Again, if I’m writing a search algorithm, and I’m looking at 100 elements, if I check one element in a millisecond, with a simple search, I have to check 100 elements in a millisecond; Binary lookup, on the other hand, requires only log2 (100) to 7 elements to be checked, so it takes only 7 milliseconds. But what if you’re looking for a list of 10,000, a billion elements? What are their respective search times?
In terms of speed, binary search takes 30 milliseconds (log2 (1000000000)) if the search list has 1 billion elements. Binary lookup is about 15 times faster than simple lookup, so simple lookup takes 450 milliseconds, is that correct?
Big mistake. If the list contains a billion elements, a simple lookup would take a billion milliseconds, because binary lookup and simple lookup run at different speeds. That is, as the elements increase, binary lookup doesn’t take much extra time, while simple lookup takes much extra time. As a result, binary lookup is much faster than simple lookup as the list grows.
The big O notation should be clear from the above examples. If you have any questions, please discuss them in the comments section.
Second, the basic data structure
Linear structure
- What is a linear structure
A linear structure is an ordered set of N data elements. That is, a data structure with a ‘one to one’ linear relationship between data elements. If the official still can’t understand, take a look at these characteristics, should be clear: 1. There must be a unique “first element” in a set; 2. There must be a single “last element” in the set; 3. All data elements except the last have a unique successor; 4. All data elements except the first have a unique “precursor”
1, the array
A one-dimensional array
An array is a linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type. — Beauty of data structures and algorithms
- The characteristics of
- Arrays use a contiguous set of memory Spaces to store data.
- Arrays can be accessed directly by subscript, so array look-up is very efficient and the time complexity is only O(1).
- Each insert and delete of an array requires moving the element behind the position (for the first reason: arrays are contiguous memory Spaces), so array inserts and deletes are inefficient.
Note: the number 5 in JS is special and does not necessarily satisfy the first feature above
In JS, if we define only one type of element in an array, such as:
Const arr1 =,3,5,9 [1]
It is a purely numeric array, so it does correspond to contiguous memory, but when we define different types of elements:
const arr2 = ['hello',1,{a:1}]
Instead of a contiguous memory, the underlying memory is a hash map, which is implemented by a linked list of objects. So it follows that arrays in JS are not necessarily real arrays. The so-called “real array” is judged by the condition: stored in contiguous memory space
A two-dimensional array, the matrix
2. Special arrays
The queue
A queue is a special kind of linear table, special in that it only allows deletions at the front of the table. With inserts at the back end of the table, a queue, like a stack, is a linear table with limited operations.
- The characteristics of
- The end where the insertion is performed is called the end of the queue
- The end that is deleted is called the header
- First in, first out
- The difference between stack and queue
- The stack is sealed at one end, while the queue is open at both ends
- Stack first in first out, queue first in first out
- How queues are implemented
- Sequential queue, a queue based on sequential table implementation
- Linked queue, queue based on linked list implementation
The difference between the two is only the difference between the sequential list and the linked list, that is, in the actual physical space, the queue for centralized storage is the sequential queue, and the queue for decentralized storage is the chain queue.
- Practical application of queues
Queue registration in the hospital is a typical queue application, the first to first out, the insertion is called the end of the queue, the first out of the queue.
The stack
A stack is a first-in, last-out data structure that can be simulated using arrays.
- Note: when using stacks
- Push, you can only pop out
- Unshift on the stack, shift off the stack
3, the linked list
A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list.
- Characteristics of linked lists
- Composition structure: A linked list consists of a series of nodes that can be dynamically generated at run time. Each node consists of two parts: a data field that stores data elements and a pointer field that stores the address of the next node.
- Storage features: Data elements of a linear table can be stored in any set of storage units (this set of storage may be continuous or non-continuous)
- Advantages and disadvantages compared to other data structures
- Compared to arrays
Advantage: Linked list can overcome the disadvantage that array needs to know the data size in advance. Linked list structure can make full use of computer memory space and achieve flexible memory dynamic management. Bad: lost the advantage of random array reads, and because of the increase in node pointer fields, space overhead is higher.
Tree structure
- What is a tree structure
A tree structure is a hierarchy of nested structures. The outer and inner layers of a tree structure have similar structures, so the structure can be recursively represented. The various tree graphs in classical data structures are typical tree structures: a tree can be simply represented as a root, a left subtree, and a right subtree. The left and right subtrees have their own subtrees.
- The characteristics of
- Tree structure is a kind of nonlinear data structure. There is a one-to-many tree relationship between its data elements
- Because the outer and inner layers of a tree structure have similar structures, consider recursion once you use this data structure.
- In the tree structure, the root node has no precursor node, and the rest nodes have one or only one precursor node. Leaf nodes have no subsequent nodes, and each of the remaining nodes can have one or more subsequent nodes.
Special tree — binary tree
Graph structure
- What is a schematic structure
Graph structure is a more complex nonlinear structure than tree structure.
- The characteristics of
- In the tree
In a tree, nodes in each layer can be associated with at most one node in the previous layer, but may be associated with multiple nodes in the next layer. 2. In the graph structure, any two nodes can be correlated, that is, all nodes can be correlated.
The collection structure
- What is a set structure
There is no other relation between elements in the same data set except that they belong to the same set. Like all the passengers on the bus, products in storage. The main operations in the collection are find and sort. There is no inherent relationship between the elements of a collection structure and no need to store relationships, often with the help of other data structures, such as linear tables and trees.
- Note: The only data structures dedicated to collection types are hash tables
Bo read
Array application
1, (1) sum of two numbers
Do the algorithm of the idea: get the first step of the topic
- Think of a violent solution
- To think of the optimization method of violent solution: 1, space for time
The answer to this question is:
- Violent solution: double loop until the inner and outer layers add up to the specified value, return
- Space for time, using Map
- Iterate over the number group, and maintain a Map, record the traversed value and the corresponding subscript, each traversed a new number, go to the Map to query the value and targetNum
Important conclusions
- Almost any sum problem can be transformed into a difference problem