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

Professor Zhou Ligong has recently released his long-awaited book, "Programming and Data Structure". This comprehensive guide is now available for free download by electronic engineers and university students. The content of this book is being shared here with the official authorization from Professor Zhou.

> > >> 1.1 Doubly Linked List

In a singly linked list, when you want to add or remove a node, you need to locate its previous node in order to update the p_next pointer. However, since each node in a singly linked list only contains a pointer to the next node (p_next), finding the previous node requires traversing the entire list from the beginning, which is inefficient. This limitation arises because there's no direct reference to the previous node within the structure itself. To overcome this, a doubly linked list introduces an additional pointer, p_prev, which points to the previous node. This allows for more efficient navigation both forward and backward through the list.

Figure 3.15: Schematic of a Doubly Linked List

Like a singly linked list, a doubly linked list also starts with a head node. The design separates the data from the structural pointers, so each node only holds p_next and p_prev pointers. Here's the structure definition:

Typedef struct _dlist_node{

Struct _dlist_node *p_next;

Struct _dlist_node *p_prev;

The term 'dlist' stands for 'double list', indicating that this is a doubly linked list node. While the addition of the p_prev pointer makes it easier to access the previous node, it also doubles the memory usage compared to a singly linked list. Therefore, when choosing between the two, it's important to consider the trade-off between performance and memory consumption.

In Figure 3.15, the p_prev of the head node and the p_next of the tail node are set to NULL. This means that if you want to find the tail from the head or vice versa, you have to traverse the entire list. To improve efficiency, these two pointers can be used to form a circular doubly linked list, where the head's p_prev points to the tail and the tail's p_next points back to the head. See Figure 3.16 for details.

Figure 3.16: Schematic of a Circular Doubly Linked List

A circular doubly linked list offers better performance as it allows direct access to both the head and tail without traversal. It also avoids extra memory overhead by reusing the unused pointers. For this reason, the doubly linked lists discussed here are assumed to be circular unless otherwise stated.

Similar to a singly linked list, the head node is structurally identical to a regular node but serves a different purpose. It represents the start of the list. To distinguish it, 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, first define a head node of this type:

Dlist_head_t head;

Initially, the head node is the only node, so it acts as both the head and the tail. According to the circular linked list definition, the tail's p_next points to the head, and the head's p_prev points to the tail. This is illustrated in Figure 3.17.

Figure 3.17: Empty List

When the list is empty, the head's p_next and p_prev point to itself. That is:

head.p_next = &head;

To prevent users from directly accessing these members, an initialization function should be defined. The function prototype is:

Int dlist_init(dlist_head_t *p_head);

It is called like this:

Dlist_head_t head;

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

Just like a singly linked list, a doubly linked list provides several basic operations. Their function 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_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 functions like dlist_prev_get and dlist_next_get, the nodes already contain the necessary pointers, making them straightforward to implement. See Listing 3.34 for details.

Listing 3.34: Get Previous and Next Node Functions

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 retrieves the last node of the list. In a circular doubly linked list, the p_prev of the head node points to the tail. See Listing 3.35 for implementation details.

Listing 3.35: dlist_tail_get() Function Implementation

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;

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

Listing 3.36: dlist_begin_get() Function Implementation

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;

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

Listing 3.37: dlist_end_get() Function Implementation

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;

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