Relearn data structures (ii) : linear tables

A List is a finite sequence of zero or more data elements. It is the most common and simplest type of data structure.

Premise note, this article will only introduce the theoretical knowledge of linear table related concepts, algorithm implementation of linear table operation, will be used in a separate article to introduce, has been completed, interested in the JS algorithm implementation of linear table

Basic concepts and features

The number of linear table elements n (n ≥ 0) is defined as the length of the linear table. When n = 0, it is called an empty table.

In a more complex linear table, a data element may consist of several data items. In this case, the data element is often called a record, and a linear table containing a large number of records is also called a file.

Common operations on linear tables include: creating and initializing, resetting empty tables, inserting data, deleting data, merging linear tables, and so on.

When the data element is a non-empty finite set, the linear structure has the following characteristics:

There exists a unique data element called “first”
There is a unique data element called “the last”
Except for the first, each data element in the collection has only one precursor
There is only one successor for each data element in the collection except the last one

Sequential storage structure

The sequential storage structure of a linear table refers to the sequential storage of the data elements of a linear table by using a segment of storage units with consecutive addresses. The characteristics of the sequential storage structure are that the two logically adjacent elements are also physically adjacent. Since each data element in a linear table is of the same type, we often use one-dimensional arrays to implement sequential storage structures.

Relevant concepts

The sequential storage structure is described by three properties:

The initial location of the storage space: that is, the array data, its storage location is the storage location of the storage space
Maximum storage capacity for linear tables: array length MaxSize
Current Length of a linear table: Length

It is important to distinguish between data length and linear table length. The length of data, namely the length of the array, is the length of the storage space for storing linear tables. After storage allocation, this amount is generally unchanged. The length of a linear table is the number of data elements in a linear table, which varies with the insertion and deletion of a linear table. Therefore, the length of a linear table should be less than or equal to the length of the array.

Each location in storage has its own number, which is called an address. For each data element, no matter whether it is an integer, a real type or a character type, it needs to occupy a certain amount of storage unit space. Assuming that c storage units are occupied, the storage location of the I +1 data element and the storage location of the I th data element in the linear table meet the following relationship:

LOC(a_i+1) = LOC(a_i) + c

Where LOC represents the function that obtains the storage location. Thus, it can be concluded that the storage location of the ith data element AI can be calculated by A1

LOC(a_i) = LOC(a₁) + (i – 1) * c

By using this formula, we can calculate the address of any position in the linear table at any time, and we can also calculate the deposit or withdrawal of each position in the linear table. The algorithm complexity is O(1), and we call the storage structure with this characteristic as random access structure.

The advantages and disadvantages

Advantages:

No additional storage is required to represent logical relationships between elements in the table
You can quickly access elements anywhere in the table

Disadvantages:

Insert and delete operations require moving a large number of elements
When the length of linear table varies greatly, it is difficult to determine the capacity of storage space
Fragmentation of storage space

Chain storage structure

The chain storage structure is characterized by an arbitrary set of storage units that store the data elements of a linear table. This set of storage units can be continuous or discontinuous, which means that the data elements can be stored in any location that is not occupied by memory.

Linear list

In order to represent the logical relationship between each data element AI and its immediate successor data element AI +1, for the data element AI, in addition to storing its own information, it needs to store information indicating its immediate successor (that is, the storage location of the immediate successor). We call the domain where data element information is stored data domain, and the domain where direct successor location is stored pointer domain. The information stored in a pointer domain is called a pointer or chain. These two parts of information constitute the storage image of data element AI, which is called Node.

N nodes (storage image of AI) are linked to form a linked list, which is the linked storage structure of a linear list, because each node of the linked list contains only one pointer field, which is also called a linear linked list or a single linked list. A singly linked list is simply a linear list of data elements linked together in their logical order through the pointer field of each node.

We call the pointer to the first node of the link (the storage location) the header pointer; The pointer to the last node is NULL (usually represented by NULL or ^).

Sometimes, in order to facilitate the operation of linked lists, a node is attached to the first node of a single linked list, called the head node. The data field of the head node can store no information or additional information, such as the length of a linear list. The pointer field of the head node stores the pointer to the first node.

Note the difference between header pointer and header:

A header pointer is a pointer to the first node in the list, or to the first node if the list has a header
Header Pointers are used as identifiers, so they are often preceded by the name of the linked list
The header pointer is not null whether the list is null or not, and is a necessary element of the list

Head node:

The header node is set up for unity and convenience of operation. It is placed before the node of the first element and its data field is generally meaningless (it can also store the length of the linked list).
With a header, inserting and deleting the first element before the first element is done in the same way as any other node
The header is not necessarily a list element

A static linked list

How can we describe the single-line lists of early programming high-level languages, such as Basic and Fortran, because they had no Pointers? Instead of Pointers, we use arrays to describe lists as static lists, and we call them cursor implementations.

We treat the first and last elements of the array as special elements and store no data.

Circular linked list

If the pointer end of the terminal node in a single linked list is changed from a null pointer to a head node, the whole single linked list will travel through a ring. Such head to tail single linked list is called a single circular linked list, or circular Linked list for short.

Two-way linked list

A double Linked list is a field of Pointers to its precursor in each node of a single linked list. So every node in a bidirectionally linked list has two pointer fields, one pointing to its immediate successor and one pointing to its immediate precursor.