To follow all the textbooks and all the books on data structures, let’s start with linear tables. Today’s article is more conceptual, a summary of a knowledge point about having a linear table.

As mentioned above, physical structure is used to determine how data is stored. Other data structures (trees, graphs), algorithms and so on are basically built on such a physical structure, it can also be said that the physical structure is the fundamental data structure. Here, we’ll start by introducing two physical structures that will be the cornerstone of our future study of data structures: sequential lists and linked lists.

The order sheet

No complicated definitions, no mathematical expressions, the most intuitive understanding is that a sequential list is an array.

That’s right. In the PHP or C world, we define sequential tables as arrays, and the same terms include sequential storage, sequential structure, and so on. When you see a noun like that, you immediately think of an array. Of course, in Java, we can also think of a collection like a List as a sequential storage structure. Note, however, that Java’s HashMap, which is defined in PHP as an array of key-value pairs, is a Hash table. Formally, they are not sequential. It’s important to remember here that a sequential structure like an array index increment is a sequential storage structure.

Sequential tables generally occupy contiguous memory space. Not only logically, but physically, they are contiguous.

The list

A linked list is usually defined in C as a structure that contains data and Pointers to the next linked list. It is not sequential. Although there is sequential logic (Pointers to the next linked list), it is physically separable. That is, linked lists do not occupy contiguous memory space and do not need to be initialized with a given length, like an array.

In PHP, we don’t have the syntax of a structure, so we use classes to represent a linked list structure.


class Node{
    public $data;
    public Node $next;
}

This is a simple linked list structure, which we can call a “node.” Data is where we store the data that we want to store, and it can be of any type. Next is our next linked list node. If we need to simply traverse the list, simply call next until it is empty.


while($n->next){
    $n = $n->next;
    echo $n->data, PHP_EOL;
}

The diagram above shows the logical state of a linked list and its traversal direction. The specific linked list operation related functions will be explained in the following articles.

Linked lists can take many forms, but the one we defined above is a simple one-way list. We can also define bidirectional linked lists (adding a prev to the previous node), circular linked lists (the last next refers to the first node), and bidirectional circular linked lists (the last next refers to the first node, and the first prev refers to the last node). We will cover these topics in a later article.

The linear table

Now that we’ve looked at ordered and linked lists, let’s finally talk about linear lists.

In fact, what the two kinds of physical structures, the ordered list and the linked list, achieve by default is the logical data structure of the “ordered list”.

2. A finite sequence of n(n>) elements with the same data characteristics. (Rigid Version)

A few key points to note:

  • Limited: array length, linked list memory size
  • Sequences: Logical order (arrays are both logically and physically ordered, lists are logically ordered but physically unordered)
  • The data properties are the same: it’s not obvious in PHP, and arrays are of fixed type in C or Java, and they have to be given an initial length

Why is a linear table so important? If you think about a relational database like MySQL, which stores data row by row, isn’t a table a linear table? Especially as PHP programmers, we are dealing with arrays every day (of course, we may use hash more). That is to say, when we are doing development, we are dealing with this thing every day, whether you say it is important or not.

However, data structures such as trees and graphs are not linear tables. In the classification of reality, they belong to the category of nonlinear tables. A big feature of linear tables is that they only have context, whether they are linked lists or arrays, they all follow this context, but in trees and graphs, in addition to front and back, there are more complex relationships, such as up, down, left, and so on. Although their basic representation is still using arrays and linked lists, they really aren’t linear in a strict sense, or in an exam interview sense, but should be classified as non-linear.

conclusion

Today’s article is a foundation for learning the basics of data structures. Of course, it is best to see how C uses structures to define arrays and lists. PHP has solved too many problems at the bottom level, so we can no longer use these primitive syntax structures. Being able to learn data structures in C is the more recommended form.

The next article will look at linear table-related logic operations for sequential tables (arrays).

References:

Data Structures, 2nd Ed., Weimin Yan

Data Structure, 2nd Edition, Yue Chen

“Notes on Data Structure with High Score”, 2020 edition, Tianqin postgraduate entrance examination

= = = = = = = = = = =

Search for “Hardcore Project Manager” on all media platforms