The beginning of the story

Recently, I talked with some colleagues who just graduated two or three years ago. I found that most of them were busy with business development and were quite proficient in their daily development tools and CRUD. Moreover, I am competent for all the development tasks arranged above. I am very skilled in the application level, so I can say that I am a qualified CRUD BOY. But when it comes to basic things, it seems a little hesitant and awkward, which is often said that the basic skills are not solid. It’s easy to get confused when you encounter a complex or even difficult problem.

In my personal experience, software development engineers are like characters in martial arts novels. If you want to achieve a better realm and become a martial arts master, “deep internal skills” must be the basic premise. All the technologies used in software development, equivalent to all kinds of tricks, such as: micro services, big data, etc., are generated in order to solve some scenarios. So if you want to use good, basic can not leave the basic support. So, when you learn something for a while, you go back and look at the basics, and the more you learn the basics, the more you understand the technology. For example, if you want to use a microservice registry well, you need to understand the principles of service registry discovery and the communication patterns (RPC or HTTP) between services. Also understand what CAP is, the election algorithm for registry clusters (e.g. Raft), and so on.

So as Java development, you need to understand: data structures, algorithms, JVM memory model, concurrent programming, GC principles, and so on. These basics may not be needed in daily development, because Java already provides a lot of packaging, and even some open source tools on the web do it for you. But you want to go in the middle and advanced development direction, and these are all required courses for you. You might be able to get things done on a daily basis, and you might be able to do poorly written code. But when you go into an interview and you’re asked these questions, you can’t answer them? Sorry, GG. Because these are the things the interviewer will definitely ask. For example: when asked about concurrent programming, how is reentrant locking implemented? What does a CLH queue do? What is CAS? These are the kinds of technologies that Internet product concurrency is bound to use.

Recently, WHILE reviewing these basic contents, I wrote some articles as a base for future reference. On the other hand, I also hope that while reviewing, I can also help some students who ignore these contents to become a qualified programmer. So come up with a “internal exercise series” article, each topic is divided into two parts, the first part mainly introduces the concept, speak clearly. The next part is mainly for the last period to do some code implementation, common interview on the computer code practice, after all, the real knowledge of practice. At the same time, we talk about growth and become friends with everyone. I even wrote some inappropriate things, I hope you can directly accuse me in the comment area or add me on wechat.

Enter the theme

So let’s take a look at some of the most common linear data structures: arrays, linked lists, stacks, queues, hashes.

An array of

❝

An array is an ordered collection of data of the same type. An array describes several pieces of data of the same type arranged in a certain order. Each piece of data is called an element, and each element can be accessed by an index (subscript).

❞

Let’s take a look at a picture (PS: The picture is drawn with PPT, it is ugly, look at it first)

An array of length 6 is created above, and the contents of the table on the right are simulated JVM memory addresses. Arrays have the following characteristics:

  • The length is fixed. Once an array is created, its size cannot be changed;
  • The elements must be of the same type, with no mixed types allowed.
  • Array types can be any data type, including primitive and reference types;
  • The elements of the array are allocated space in the heap memory, and are allocated consecutively;
  • The elements of an array are ordered numbered, starting at 0;

So once we’ve initialized the array, we’ve allocated the contiguous contents, and it’s very easy to get the corresponding values from the array ordinals, and we can get the values of the elements from the array ordinals at will. And the time is O (1), which means that you can get the element value of the data in a single query. Now let’s look at the other operations: insert and delete.


When we insert “director” into the third position in the array, the “patient” element, originally subscript 2, and the following elements, move and reassign each element. In the same way, when deleting a patient, the following elements are moved and copied again. From this point of view, inserts and deletes are not as efficient as queries, and the time complexity of inserts and deletes is O (n). This allows us to see that arrays are not suitable for frequent inserts and deletions, especially for large arrays.

The list

❝

A linked list is a non-sequential and non-sequential storage structure in physical storage structure. The logical order of data elements is realized by reference link order in the linked list.

❞


Linked lists are divided into one-way linked lists and two-way linked lists.

Singly linked list (unidirectional linked list) : consists of two parts: Data domain and Node domain. Each Node has a pointer. The pointer of each Node points to the next Node of its own Node. The head of the last Node points to null.

Double linked list (double linked list) : Compared with single linked list, double linked list has a tail pointer. Each node of double linked list has a head pointer head and tail pointer. Double linked list is easier to operate than single linked list, head of the first node of double linked list is null, tail is the tail of the next node. The head of the tail node points to the head of the previous node, and tail points to null, which is a bidirectional relationship.


In a singly linked list if need to find a certain element, must start from the first element of lookup, query the number of times is closely related to the number of nodes, such a singly linked list query time complexity is o (n), and for insert, only need to add a new node next point to the next node, the node of the next point to the new node;

Delete is the same reason, as long as the node before the node to delete the next node to delete the node can be. It can be seen from here that the insertion and deletion of linked list can be completed only by two operations, regardless of the number of nodes, and the time complexity is o(1). As you can see, linked list data structures are much more efficient for insert and delete scenarios than arrays.

The stack and queue

❝

A stack is a linear data structure (FILO) characterized by the fact that data can be inserted and deleted only through one end, called the “top of the stack”, and the corresponding other end, called the “bottom of the stack”.

❞

❝

A queue is also a linear data structure (FIFO), special in that it allows only deletion at the front end and insertion at the back end of the table. Like a stack, a queue is a linear table with limited operations. The end where the insertion operation is performed is called the end of the queue, and the end where the deletion operation is performed is called the end of the queue.

❞


Stacks and queues are also the most common data structures in our daily development, and many functions can be achieved by using their own characteristics. The first in, last out feature of the stack can be used in some matching scenarios. For example: matching parentheses, pairwise pairing, etc. The first in, first out (FIFO) feature of queue, the most common is our message queue, multi-threaded double-ended queue and so on. Like linked lists, stack and queue query complexity is O (n), insert and delete operations are 0(1), you can choose according to the scenario.

Hash table

❝

A Hash table (also called a Hash table) is a data structure that is directly accessed based on Key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping function is called a hash function, and the array of records is called a hash table.

❞


When using a hash table, you usually hash the key first, which is to “compress” the input value into a smaller value, which is usually unique and extremely compact. After the hash algorithm, sum the ASCII characters of each letter of the key and modulo the length with the memory address 30. Then calculate that the subscript is 9. Then put the value under the ninth element. So even if we evaluate it next time, we can get value directly from key. And the time is order 1.

This might sound a little complicated, but I think I’ll give you an example, and the most typical example is dictionaries. If I want to check the “Dong” word details, I will certainly go according to pinyin dong to find pinyin index, first to check the position of dong in the dictionary, checked to get “Dong”. It’s called key-code mapping, and in the formula, it’s finding f of key by key. Where, dong is the key, the page number checked is the hash value, and value is the detailed information of Dong.

Hash conflict


If KEY is “NO,” the hash value is 429, which is a problem, that is, hash conflict. Solution: Chain address method. If the principle of chained address method encounters a conflict, it creates a new space at the original address and inserts it into that space as a linked list node. I think the one that’s used the most in the industry is chained address. “No President wants to be a President,” says The statement, “NO President wants to be a President,” and “Lies” next points to “No President”. Hash table is also the most visible data structure in Java development process, and Java has encapsulated HashSet, HashMap, etc., can be used quickly.

The last

Today, I briefly reviewed common data structures in development: arrays, linked lists, stacks, queues, hash tables. The next chapter will be based on the content of this article, several practical application scenarios, and through the code to achieve. Hope you continue to pay attention to support! Let’s make progress together.

Special statement

This article is an original article. If you need to reprint it, please contact me and indicate the source. Thank you very much!

“Previous articles:“

Linear Data Structure (Part 1)

Linear Data Structure (Part 2)