Zhou Ligong's new content sharing: What is a two-way linked list?

Professor Zhou Ligong has recently published a long-awaited book titled "Programming and Data Structure." This comprehensive work has been made available for free download to electronic engineers and college students. With Professor Zhou’s authorization, the content of this book is now being serialized for broader access.

> > >> 1.1 Doubly Linked List

When working with a singly linked list, adding or removing a node requires finding its previous node so that you can adjust the p_next pointer accordingly. However, since a singly linked list node doesn’t have a pointer to its previous node, you must traverse the list from the head each time, which significantly reduces efficiency. In contrast, the next node in a singly linked list can be directly accessed because each node contains a p_next pointer pointing to the next element. To solve this limitation, we can introduce a p_prev pointer in each node of a doubly linked list, allowing direct access to the previous node. This enhancement makes the data structure more efficient and versatile.

Figure 3.15: Schematic Diagram of a Doubly Linked List

Like the singly linked list, the doubly linked list also includes a head node. Following the design principle of separating application data from structural information, the nodes of a doubly linked list only contain the p_next and p_prev pointers. The structure is defined as follows:

Typedef struct _dlist_node {

Struct _dlist_node *p_next;

Struct _dlist_node *p_prev;

} dlist_node_t;

Here, “dlist” stands for “double list,” indicating that this is a node used in a doubly linked list. While the addition of a forward pointer improves performance by making it easier to navigate backward, it also doubles the memory usage compared to a singly linked list. In practice, developers must weigh efficiency against memory constraints. When memory is limited and operations are infrequent, a singly linked list may be preferable.

In Figure 3.15, the p_prev of the head node and the p_next of the tail node are set to NULL. This setup means that to find the tail from the head or vice versa, the entire list must be traversed. To improve this, we can make the list circular by having the head’s p_prev point to the tail and the tail’s p_next point to the head. This creates a circular doubly linked list, as shown in Figure 3.16.

Figure 3.16: Schematic Diagram of a Circular Doubly Linked List

The circular doubly linked list offers better performance since it allows direct access to both the head and tail without traversal. It uses existing pointers efficiently, avoiding extra memory consumption. Therefore, the doubly linked lists discussed here are typically considered circular.

Similar to a singly linked list, the head node is functionally equivalent to a regular node but serves a different purpose. It marks the start of the list. To distinguish between the head and other nodes, we can define a separate type for the head node, such as:

Typedef dlist_node_t dlist_head_t;

When using a doubly linked list, the first step is to define a head node of this type. For example:

Dlist_head_t head;

At this point, there are no other nodes, so the head node acts as both the first and last node. According to the definition of a circular list, the tail node's p_next points to the head, and the head's p_prev points to the tail. This configuration is illustrated in Figure 3.17.

Figure 3.17: Empty List

When the list contains only the head node, both p_next and p_prev point to itself:

head.p_next = &head;

head.p_prev = &head;

To prevent users from directly modifying these members, an initialization function is needed. The prototype of this function (in dlist.h) is:

Int dlist_init(dlist_head_t *p_head);

This function initializes the head node. A typical call would be:

Dlist_head_t head;

Dlist_init(&head);

The implementation of dlist_init() 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;

9 }

Just like the singly linked list, the doubly linked list provides several basic functions. Their prototypes include:

Dlist_node_t *dlist_prev_get (dlist_head_t *p_head, dlist_node_t *p_pos); // Get the previous node

Dlist_node_t *dlist_next_get (dlist_head_t *p_head, dlist_node_t *p_pos); // Get the next 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 first user node

Dlist_node_t *dlist_end_get (dlist_head_t *p_head); // Get the end position

For dlist_prev_get() and dlist_next_get(), the predecessor and successor can be retrieved directly using the existing pointers. See Listing 3.34 for details.

Listing 3.34: Implementation of Functions to Get Previous and Next Nodes

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;

15 }

The dlist_tail_get() function retrieves the tail node. In a circular doubly linked list, the p_prev of the head node points to the tail. See Listing 3.35 for more details.

Listing 3.35: Implementation of dlist_tail_get()

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;

7 }

The dlist_begin_get() function returns the first user node. Its implementation is shown in Listing 3.36.

Listing 3.36: Implementation of dlist_begin_get()

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;

7 }

The dlist_end_get() function is used to get the end position. In a circular doubly linked list, the end position is the head node itself. Its implementation is provided in Listing 3.37.

Listing 3.37: Implementation of dlist_end_get()

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;

7 }

On the official WeChat account, reply to the keyword " program design " to read "Programming and Data Structure" online ; reply to the keyword " programming " to read "Programming for AMetal Framework and Interface (on)" online.