“My First Algorithm Book” is based on the iOS and Android app “Algorithm Animation Diagram,” and has been supplemented and revised for publication, specifically adding basic theory content.

Determines the order and position of the data

Data is stored in the computer’s memory. Memory, as shown in the figure on the right, looks like a box arranged in one column, with one box storing one data.

When data is stored in memory, it is the “data structure” that determines the order and location of the data.

The data structure of the phone book

▶ Example 1 Add them from top to bottom

Let’s take a simple example. Let’s say we have a phone book — although many people now store phone numbers in their cell phones, let’s consider using paper phone books — and each time we get a new phone number, we write it down in the phone book from top to bottom.

Hypothesis at this time we want to call “zhang wei”, but because the data is according to the order, so we do not know where zhang wei of the number, can only from head down, looking for (though “from the front after” or “random search”, but the efficiency is not higher than “from above to find”). If you don’t have many numbers in the phone book, you can find them quickly, but if you have 500 numbers in the phone book, it is not so easy to find them.

Arrange the names in alphabetical order

Next, try alphabetizing your contacts in alphabetical order. Because the data is in lexicographical order, it is “structured”.

Sorting contacts this way makes it much easier to find people to target. The approximate location of the data can be inferred from the pinyin initials of the name.

So how do you add data to the phonebook, which is arranged in alphabetical order? Let’s say we meet our new friend “Zimbo” and get his phone number. We plan to put it in the phone book. Since the data are arranged in alphabetical order, ke Jinbo must be written between Han Hongyu and Li Xi, but there is no space to fill in the table above, so we need to move the data of Li Xi and below one line down.

In this case, we need to write this line to the next line and then clear this line from the bottom up. If there are 500 pieces of data and one operation takes 10 seconds, an hour won’t do the job.

▶ The advantages and disadvantages of the two methods

In general, if the data is arranged according to the order of acquisition, although it is very simple to add data, just need to add the data at the end, but it is more troublesome to query; In pinyin order to arrange words, although in the query is relatively simple, but add data will be more troublesome.

Both methods have their advantages and disadvantages, but the choice depends on how the phone book is used. If the phone book is ready and no new numbers are added, the latter is more appropriate; If you need to add new numbers frequently, but rarely need to query them again, you should choose the former.

▶ How about combining the fetch order with the pinyin order

We can also consider a new arrangement that combines the best of both. That is to use different tables to store different alphabetic initials, such as table L, table M, table N, etc., and then arrange the data in the same table according to the order of acquisition.

In this way, when adding new data, you can simply add the data to the end of the corresponding table, and when querying the data, you only need to look up the corresponding table.

Since the data stored in each table is still random, you still have to start at the top of the table, but it’s still a lot easier than looking through the entire phone book.

Choose the right data structure to improve memory utilization

The same ideas for data structures were used to create the phone book. When storing data in memory, select an appropriate data structure according to its purpose to improve memory utilization.

This chapter will cover seven data structures. As mentioned at the beginning of this section, the data is arranged in a linear fashion in memory, but we can also use props such as Pointers to construct complex structures like “trees” (tree structures are explained in more detail in Section 4-2).

Reference: 4-2 breadth-first search

1 to 2

A linked list is a data structure in which data is arranged in a linear fashion. In linked lists, data can be easily added and deleted, but access is time consuming.

commentary

What is the running time for a linked list operation? So in this case, we call the amount of data in the linked list n. To access the data, we need to search from the head of the list (linear search), and if the target data is at the end of the list, it takes O(n) time.

Also, adding data only requires changing the pointing of two Pointers, so the time taken is independent of n. If you have reached the point where you want to add data, the add operation takes O(1) time. Deleting data also takes O(1) time.

Reference: 3-1 linear lookup

added

The linked list described above is the most basic kind. In addition, there are several linked lists that can be easily extended.

Although the list mentioned above does not have a pointer at the end, we can also use a pointer at the end of the list and point to the data at the head of the list, turning the list into a ring. This is called a circular list, also known as a circular list. Circular lists have no concept of heads and tails. Such lists are often used when you want to keep a fixed amount of up-to-date data.

In addition, each item in the list above has only one pointer, but we can set the pointer to two and have them point to the data before and after. This is a “two-way linked list”. With this list, you can easily traverse data not only from front to back, but also from back to front.

However, there are two disadvantages of bidirectional linked lists. First, the increase of Pointers will increase the storage space demand. Second, more Pointers need to be changed when adding and deleting data.

1-3 array

An array is also a data structure in which data is arranged in a linear fashion. Unlike the linked lists in the previous section, in an array, accessing data is simple, and adding and deleting data is time-consuming. This is similar to the phonebook in which names are arranged in alphabetical order described in Section 1-1.

1-1 What is a data structure

commentary

Here’s how much time it takes to operate on an array. Suppose there are n data in the array, and since the data is accessed using random access (the memory address is calculated by subscript), the running time required is only constant O(1).

On the other hand, when you want to add new data to the array, you must remove the data after the target location one by one. So, if you add data to the header of the array, it takes O(n) time. The same is true for deleting a vm.

added

In both linked lists and arrays, data is arranged in a linear column. Accessing data in linked lists is more complicated, adding and deleting data is simpler; While accessing data in an array is simple, adding and deleting data is more complex.

We can decide which data structures to use based on which operations are more frequent.

1-4 stack

A stack is also a data structure in which data is arranged in a linear fashion, but in which only the most recently added data can be accessed. A stack is like a stack of books. When we get a new book, we put it on the top of the stack. When we get a book, we can only take the new book from the top.

commentary

The Last data added to a stack is taken Out First, a “Last In, First Out” structure we call Last In First Out, or LIFO.

Like linked lists and arrays, data is arranged in a linear manner, but in a stack, data can be added and removed only at one end, and data can be accessed only at the top. In order to access the data in the middle, the target data must be moved to the top of the stack by an off-stack operation.

The sample application

The fact that the stack operates on only one side may seem inconvenient, but it is handy when you only need to access the latest data.

For example, if (AB (C (DE) F) (G ((H) I J) K)) is a string of characters, the parentheses are read from the left, the left parentheses are pushed onto the stack, and the left parentheses at the top are pushed off the stack. At this point, the left parenthesis out of the stack matches the currently read right parenthesis. By doing this, we know exactly where the matching brackets are.

Additionally, depth-first search algorithms, which we will study in sections 4-3, usually select the most recent data as alternate vertices. Stacks can be used for managing alternate vertices.

Reference: 4-3 depth-first search