Zhou Ligong explains how to use an efficient two-way linked list

Recently, Professor Zhou Ligong has published his painstaking work "Programming and Data Structure" for several years. The electronic version has been distributed to electronic engineers and college groups for free download. Authorized by Professor Zhou Ligong, the content of this book is serialized.

> > >> 1.1.1 Adding Nodes

Assuming that the node is still added to the end of the list, the function prototype is:

Int dlist_add_tail(dlist_head_t *p_head, dlist_node_t *p_node);

Among them, p_head is a pointer to the node of the list header, and p_node is a pointer to the node to be added. For the usage example, see Listing 3.38 .

Listing 3. 38 dlist_add_tail () function uses the example

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5

6 dlist_init(&head);

7 dlist_add_tail(&head, &node);

8 // ......

In order to implement this function, you can first check the changes of the linked list before and after adding the node, as shown in Figure 3.18 .

Figure 3.18 Adding a node diagram

Thus, adding a node to the end of the list requires 4 pointers (dashed arrows in the figure):

● The new node's p_prev points to the tail node;

● The new node's p_next points to the head node;

● The p_next of the tail node is changed from pointing to the head node

To the new node;

● The p_prev of the head node is modified from pointing to the tail node to point to the new node.

After these operations, when the node is added to the end of the list, it becomes a new tail node. See Listing 3.39 for details .

Listing 3. 39 dlist_add_tail () function to achieve

1 int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 if (p_head == NULL){

4 return -1;

5 }

6 p_node -> p_prev = p_head->p_prev; //p_prev of the new node points to the tail node

7 p_node -> p_next = p_head; //p_next of the new node points to the head node

8 p_head -> p_prev->p_next = p_node; //p_next of the tail node points to the new node

9 p_head -> p_prev = p_node; //p_prev of the head node points to the new node

10 return 0;

In fact, the circular list, whether it is a head node, a tail node or a normal node, is essentially the same, with the p_next member pointing to the next node and the p_prev member pointing to the previous node. Therefore, for adding nodes, whether the nodes are added to the list header, the end of the chain, or any other location, the operation method is exactly the same. To do this, you need to provide a more general function, you can add nodes to any node, the function prototype is:

Int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node);

Where p_head is a pointer to the node of the list header, p_pos specifies the location to be added, the new node is added after the node pointed to by the pointer; p_node is a pointer to the node to be added. For example, the same list to add the node to the tail, using a detailed example of Listing 3.40.

Listing 3. 40 dlist_add () function uses the example

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5

6 dlist_init(&head);

7 dlist_add(&head, &(head.p_prev), &node);

8 // ......

It can be seen that the position where the tail node is added as a node can also be added to the tail of the linked list after the node is added to the tail node. Obviously, there is no need to write dlist_add_tail () implementation code, and use dlisd_add () can achieve modification dlist_add_tail () function, see Listing 3.41.

Listing 3. 41 dlist_add_tail () function to achieve

1 int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 return dlist_add(p_head, p_head->p_prev, p_node);

In order to implement the dlist_add() function, you can first check the situation after adding a node to any node, as shown in Figure 3.19 . The figure shows a general case. Since the addition position (head, tail or any other position) of the node has nothing to do with the method of adding the node, the head node and the tail node are not specifically marked.

In fact, comparison of FIGS. 3.18 and 3.19 can be found, Figure 3.18 shows just a special case of FIG. 3.19, i.e. just graph nodes is the end node, add node process also requires before a new node in 3.19 modified 4 The value of the pointer. For convenience of description, the node before the new node is called the former node, and the node after the new node is called the back node. Obviously, before adding a new node, the next node of the previous node is the back node. The description of setting 4 pointer values ​​is as follows:

● The new node's p_prev points to the previous node;

● The new node's p_next points to the last node;

● The p_next of the previous node changes from pointing to the next node to pointing to the new node;

● The p_prev of the post-node is modified by pointing to the previous node to point to the new node.

To compare the description of adding a node to the end of the list, just replace the "predecessor" in the description with the "tail node" and the "post node" with the "head node". Their meanings are exactly the same, obviously Adding a node to the end of the list is just a special case. The function implementation for adding a node is detailed in Listing 3.42 .

Listing 3. 42 dlist_add () function to achieve

1 int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node)

2 {

3 if ((p_head == NULL) || (p_pos == NULL) || (p_node == NULL)){

4 return -1;

5 }

6 p_node->p_prev = p_pos; //p_prev of the new node points to the previous node

7 p_node->p_next = p_pos->p_next; //p_next of the new node points to the back node

8 p_pos->p_next->p_prev = p_node; //p_prev of the post node points to the new node

9 p_pos->p_next = p_node; //p_next of the previous node points to the new node

10 return 0;

Although the above function does not use the parameter p_head when it is implemented, the p_head parameter is passed in , because the p_head parameter will be used to implement other functions , for example , to determine whether p_pos is in the linked list .

With this function, adding a node to any position is very flexible. For example, provide a function that adds a node to the head of the linked list as the first node of the linked list. The function prototype is:

Int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node);

At this point, the head node is the previous node of the newly added node, which can be realized by directly calling dlist_add(). For the implementation example, see Listing 3.43 .

Listing 3. 43 dlist_add_head () function to achieve

1 int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 return dlist_add(p_head, p_head, p_node);

> > >> 1.1.2 Deleting nodes

Based on the idea of ​​adding nodes to arbitrary locations, you need to implement a function that removes any nodes. Its function prototype is:

Int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node);

Wherein, p_head list head pointer to point to node, p_node be deleted to point to the node pointer, using the example see Listing 3.44.

Listing 3. 44 dlist_del () using the sample program

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5 dlist_init(&head);

6 dlist_add_tail(&head, &node);

7 dlist_del(&head, &node);

8 //......

9 return 0;

To achieve dlisd_del () function, you can view a schematic view schematic of deleting any node other nodes, Figure 3.20 (a) is a schematic view before the deletion node, FIG. 3.20 (2) is deleted.

Figure 3.20 Adding a node diagram

Thus, you only need to modify the values ​​of the two pointers:

● Modify the p_next of the previous node of the "Delete Node" to point to the back node of the "Delete Node";

● Modify the p_prev of the post node of the “Delete Node” to point to the previous node of the “Delete Node”.

See Listing realize delete nodes function of 3.45.

Listing 3. 45 dlist_del () function to achieve

1 int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

4 return -1;

5 }

6 p_node-> p_prev-> p_next = p_node- > p_next; p_next // node before the node is modified to point

7 p_node-> p_next-> p_prev = p_node- > p_prev; // p_prev the node before the node is modified to point

8

9 p_node->p_next = NULL;

10 p_node->p_prev = NULL;

11 return 0;

In order to prevent the deletion of the head node, p_head and p_node are compared in the program. When p_node is the head node, the error is directly returned.

> > >> 1.1.3 traversing the linked list

Similar to a singly linked list, you need a function that traverses each node of the linked list. The function prototype (dlist.h) is:

Int dlist_foreach (dlist_head_t *p_head,

Dlist_node_process_t pfn_node_process,

Among them, p_head points to the link header node, pfn_node_process is the node processing callback function, and each function is called when it is traversed to a node, which is convenient for the user to process the node. The dlist_node_process_t type is defined as follows :

Typedef int (*dlist_node_process_t) (void *p_arg, dlist_node_t *p_node);

The dlist_node_process_t type parameter is a p_arg pointer and a node pointer, and the return value is a function pointer of type int. Each time a node is traversed , the function pointed to by pfn_node_process is called , which is convenient for the user to process the node data as needed. When the callback function is called, the value passed to p_arg is the user parameter, and its value is the same as the third parameter of the dlist_traverse() function, that is, the value of the parameter is completely determined by the user; the value passed to p_node is Pointer to the node that is currently traversed . When traversing to a node, if the user wishes to terminate the traversal, at this point, simply return a negative value in the callback function to terminate the traversal. In general, if you want to continue traversing, you can return 0 after the execution of the function. The implementation of the dlist_foreach() function is detailed in Listing 3.46 .

Listing 3.46   Implementation of linked list traversal function

1 int dlist_foreach (dlist_head_t *p_head,

2 dlist_node_process_t pfn_node_process,

3 void *p_arg)

4 {

5 dlist_node_t *p_tmp, *p_end;

6 int ret;

7

8 if ((p_head == NULL) || (pfn_node_process == NULL)) {

10 }

11

12 p_tmp = dlist_begin_get(p_head);

13 p_end = dlist_end_get(p_head);

14

15 while (p_tmp != p_end) {

16 ret = pfn_node_process(p_arg, p_tmp);

17 if (ret < 0) { // no longer continue traversing

18 return ret;

19 }

20 p_tmp = dlist_next_get(p_head, p_tmp); // Continue to the next node

twenty one }

22 return 0;

For ease of reference, the contents of the dlist.h file are shown as shown in Listing 3.47 .

Listing 3. 47 dlist.h file contents

1 #ipragma once

2 #include