Zhou Ligong's new content sharing: What is a 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 Doubly linked list

To add or delete a singly linked list, you must find the previous node of the current node, so that you can modify the p_next pointer of the previous node to complete the corresponding operation. Since the node of the singly linked list does not have a pointer to its previous node, only the linked list is traversed from the head node. When a node's p_next points to the current node, it indicates that it is the previous node of the current node. Obviously, every time you have to traverse from the beginning, its efficiency is extremely low. In the singly linked list , the reason for directly obtaining the next node of the current node in the singly linked list is because the node contains a pointer p_next pointing to the next node. If you add a forward pointer p_prev to its previous node in the node of the doubly linked list, then all problems will be solved. Then, the linked list that points to both the next node and the pointer to the previous node is called a doubly linked list. See Figure 3.15 for details .

Figure 3.15 Schematic diagram of the doubly linked list

Like the singly linked list, the doubly linked list also defines a head node. Based on the design idea that the unidirectional linked list completely separates the application data from the linked list structure related data, the doubly linked list node only retains the p_next and p_prev pointers. Its data structure is defined as follows:

Typedef struct _dlist_node{

Struct _dlist_node *p_next;

Struct _dlist_node *p_prev;

Where dlist is an abbreviation for double list, indicating that the node is a doubly linked list node. It can be seen that although the forward pointer makes it easy to find the last node of the linked list, because of the addition of a pointer in the node, its memory overhead will be twice that of the singly linked list. In practical applications, efficiency and memory space should be weighed. In the case where memory resources are very scarce, if the addition and deletion operations of nodes are rare and the effect of efficiency is acceptable, then the unidirectional linked list is selected. Rather than blindly pursuing efficiency, the two-way linked list is better than the one-way linked list, and always chooses to use a doubly linked list.

In Figure 3.15 , the p_prev of the head node and the p_next of the tail node are directly set to NULL. In this case, if the tail node is to be found directly by the head node, or the head node is found by the tail node, the entire node must be traversed. Linked list. You can use these two pointers slightly, so that the head node's p_prev points to the tail node, and the tail node's p_next points to the head node. At this point, the doubly linked list becomes a circular doubly linked list. See Figure 3.16 for details . .

Figure 3.16 Schematic diagram of the circular doubly linked list

Because the circular doubly linked list is more efficient, you can find the tail node directly from the head node, or find the head node from the tail node, and there is no extra memory space consumption, just use two pointers that are not intended to be used. Waste utilization, so the doubly linked list described below is considered a circular doubly linked list.

Similar to a singly linked list, although the head node is exactly the same as the normal node, their meanings are different. The head node is the head of the linked list, which represents the entire linked list. Has the entire list. In order to distinguish between the head node and the normal node, a head node type can be defined separately. such as:

Typedef dlist_node_t dlist_head_t;

When you need to use a doubly linked list, you first need to define a header node with this type. such as:

Dlist_head_t head;

Since no other nodes have been added at this time, there is only one head node, so the head node is both the first node (head node) and the last node (tail node). According to the definition of the circular linked list, the p_next of the tail node points to the head node, and the p_prev of the head node points to the tail node. The schematic diagram of only one node is shown in Figure 3.17 .

Figure 3.17 Empty chain

Obviously, when there are only head nodes, both p_next and p_prev point to themselves. which is:

Head.p_next = &head;

In order to prevent users from directly manipulating members, you need to define an initialization function that is used to initialize the values ​​of each member of the linked list header. The function prototype (dlist.h) is:

Int dlist_init(dlist_head_t *p_head);

Among them, p_head points to the link header node to be initialized. The form of its call is as follows:

Dlist_head_t head;

The implementation of the dlist_init() function is detailed in Listing 3.33 .

Listing 3.33    Doubly linked list initialization function

1 int dlist_init(dlist_head_t *p_head)

2 {

3 if (p_head == NULL){

4 return -1;

5 }

6 p_head -> p_next = p_head;

7 p_head -> p_prev = p_head;

8 return 0;

Similar to a singly linked list, it will provide some basic operational interfaces. Their function prototypes are as follows:

Dlist_node_t *dlist_prev_get (dlist_head_t *p_head, dlist_node_t *p_pos); // Find the previous node of a node

Dlist_node_t *dlist_tail_get (dlist_head_t *p_head); // Get the tail node

Dlist_node_t *dlist_begin_get (dlist_head_t *p_head); // Get the starting position , the first user node

For dlist_prev_get() and dlist_next_get(), there are already pointers to the predecessor in the linked list node, as shown in Listing 3.34 .

Listing 3.34    Get node predecessor and subsequent function implementation

1 dlist_node_t *dlist_prev_get(dlist_head_t *p_head, dlist_node_t *p_pos)

2 {

3 if (p_pos != NULL){

4 return p_pos -> p_prev;

5 }

6 return NULL;

7 }

9 dlist_node_t *dlist_next_get(dlist_head_t *p_head, dlist_node_t *p_pos)

10 {

11 if (p_pos != NULL){

12 return p_pos -> p_next;

13 }

14 return NULL;

The dlist_tail_get() function is used to get the tail node of the linked list. In the circular doubly linked list, the p_reev of the head node points to the tail node . See Listing 3.35 for details .

Listing 3. 35 dlist_tail_get () function to achieve

1 dlist_node_t *dlist_tail_get(dlist_head_t *p_head)

2 {

3 if (p_head != NULL) {

4 return p_head->p_prev;

5 }

6 return NULL;

dlist_begin_get () function is used to obtain a first user node, see Listing 3.36.

Listing 3. 36 dlist_begin_get () function to achieve

1 dlist_node_t *dlist_begin_get(dlist_head_t *p_head)

2 {

3 if (p_head != NULL){

4 return p_head->p_next;

5 }

6 return NULL;

dlist_end_get () for obtaining the end position of the list, when the circular doubly linked list is a doubly linked list design, the p_prev p_next tail node and the first node it is effectively utilized, and p_prev p_next any node is not valid Then NULL . Obviously, NULL can no longer be used as the end position. When the nodes of the linked list are sequentially accessed from the first node, the next node of the tail node is the head of the list, so the end position is the head. The node itself. The implementation of dlist_end_get() is detailed in Listing 3.37 .

Listing 3. 37 dlist_end_get () function to achieve

1 dlist_node_t *dlist_end_get(dlist_head_t *p_head)

2 {

3 if (p_head != NULL) {

4 return p_head->p_prev;

5 }

6 return NULL;

In the background of the public number, reply to the keyword " program design ", you can read "Programming and Data Structure" online ; reply to the keyword " programming ", you can read "Programming for AMetal Framework and Interface (on)" online.