Linked storage structure of linear table

Do we have any good solutions to the shortcomings of the sequential structure?

The linked storage structure of the linear list we are going to introduce today can very well solve the shortcomings of the sequential structure. Let’s take a look at it together.

Chain storage structure, also called linked storage structure. A set of arbitrary storage units is used in the computer to store the data elements of the linear table (this set of storage units can be continuous or discontinuous).

Basic introduction

It does not require that logically adjacent elements are also physically adjacent. Therefore, it does not have the weaknesses of the sequential storage structure, but it also loses the randomness of the sequential table. Advantages of access.

Features

1. The storage density is smaller than the sequential storage structure (each node in the chain storage structure consists of a data field and a pointer The domain is composed of two parts, which increases the storage space compared to the sequential storage structure).

2. Logically adjacent nodes do not have to be physically adjacent.

3. Flexible insertion and deletion (no need to move the node, just change the pointer in the node).

4. Chained storage is slower than sequential storage when searching for nodes.

5. Each node is composed of data field and pointer field.

6. Since clusters are randomly assigned, this also reduces the probability of overwriting after data deletion and increases the possibility of recovery.

Recommended course:C Language Tutorial.

The last element of the linear list has no direct successor, so in linked storage, we set the pointer field of the last node to null.

Let’s do this Look at the specific code implementation of a singly linked list

typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域，用来指向本节点的直接后继 }LNode,*LinkList; //定义节点，以及头指针

Many students can’t tell the relationship and difference between the head pointer, head node, and the first node. Let’s make a simple distinction below. Down.

Head pointer: It is a pointer to the linked list. If the linked list has a head node, it will point to the head node

Head node: an auxiliary before the first node Node, its next points to the first node

The first node: It is a node, the data variable stores the first data, and the next pointer variable points to the second node

What should be noted here is that the head pointer is a necessary element of a linked list, but the head node is not. So what is the significance of the existence of the head node?

My personal understanding is to make the insertion and deletion operations of the first node consistent with the operations of subsequent nodes. Otherwise, when we modify the first node, we need to modify the head pointer.

If there is no head node, the head pointer points directly to the first node.

The above is the detailed content of Linked storage structure of linear table. For more information, please follow other related articles on the PHP Chinese website!