带头节点 (非头指针) 双向循环链表 (doubly linked list)

浅浅的花香味﹌ 2023-01-11 13:00 130阅读 0赞

#  带头节点 (非头指针) 双向循环链表 (doubly linked list) #

bidirectional circular linked list：双向循环链表

建议使用带头结点，而非头指针的双向循环链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

## 1. 双向链表 ##

双向链表的每个数据结点中都有两个指针，分别指向直接后继 (next) 和直接前驱 (prev) 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

## 2. 双向循环链表 ##

**本节图片参考** [https://www.cnblogs.com/skywang12345/p/3561803.html][https_www.cnblogs.com_skywang12345_p_3561803.html]

双向链表和单链表都是由节点组成，双向链表的每个数据结点中都有两个指针，分别指向直接后继 (next) 和直接前驱 (prev) 。

双向循环链表最后一个结点的直接后继 (next) 指向表头 (head) 结点，而不像双向链表置为 NULL。

在判断是否到达表尾时，判断该结点直接后继 (next) 是否是表头结点，当直接后继 (next) 等于表头指针时，说明已到表尾。而不像双向链表那样判断直接后继 (next) 是否为 NULL。

从**双向链表**中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造**双向循环链表**。  
![在这里插入图片描述][20210220093059930.png_pic_center]

头节点 (非头指针) 双向循环链表示例图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

![在这里插入图片描述][2021022400252355.png_pic_center]

表头 head 为空，head 的后继节点 (next) 为节点 10 (数据为 10 的节点)；节点 10 的后继节点 (next) 是节点 20 (数据为 20 的节点)，节点 20 的前继节点 (prev) 是节点 10；节点 20 的后继节点 (next) 是节点 30，节点 30 的前继节点 (prev) 是节点 20；…；末尾节点的后继节点 (next) 是表头 head。

### 2.1 头节点 (非头指针) 双向循环链表删除节点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

头节点 (非头指针) 双向循环链表删除节点示例图

**删除节点 30 (数据为 30 的节点)**  
**删除之前**：节点 20 的后继节点 (next) 为节点 30，节点 30 的前继节点 (prev) 为节点 20。节点 30 的后继节点 (next) 为节点 40，节点 40 的前继节点 (prev) 为节点 30。  
**删除之后**：节点 20 的后继节点 (next) 为节点 40，节点 40 的前继节点 (prev) 为节点 20。

### 2.2 头节点 (非头指针) 双向循环链添加节点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]

![在这里插入图片描述][20210224003934259.png_pic_center]

头节点 (非头指针) 双向循环链表添加节点示例图

**在节点 10 与 节点 20 之间添加节点 15**  
**添加之前**：节点 10 的后继节点 (next) 为节点 20，节点 20 的前继节点 (prev) 为节点 10。  
**添加之后**：节点 10 的后继节点 (next) 为节点 15，节点 15 的前继节点 (prev) 为节点 10。节点 15 的后继节点 (next) 为节点 20，节点 20 的前继节点 (prev) 为节点 15。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 8]

## 3. 带头节点 (非头指针) 双向循环链表 (doubly linked list) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 9]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 10]

## 3.1 insert\_first - delete\_node - display ##

//============================================================================
    // Name        : doubly linked list
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #define MAX_NODE_LEN 401
    #define NULL 0
    
    #include <stdio.h>
    
    typedef struct NODE {
    	int data;
    	struct NODE *prev;
    	struct NODE *next;
    } Node;
    
    Node node_array[MAX_NODE_LEN];
    int node_array_idx = 0;
    
    void insert_first(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    
    	// equality: head->next->prev = node;
    	node->next->prev = node;
    	head->next = node;
    }
    
    void delete_node(const Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	// current node - node
    
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    void delete_node_v1(const Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    void delete_node_v2(Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    
    	node->next = node->next = NULL;
    }
    
    void display(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->next;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->next;
    	}
    }
    
    int main()
    {
    	// 头节点 (非头指针)
    	Node root;
    
    	// initialization
    	// root.prev = &(root);
    	// root.next = &(root);
    	root.prev = root.next = &(root);
    	root.data = 0;
    
    	for (int i = 0; i < MAX_NODE_LEN; ++i)
    	{
    		node_array[i].prev = NULL;
    		node_array[i].next = NULL;
    		node_array[i].data = 0;
    	}
    
    	// insert 0
    	node_array[0].data = 0;
    	insert_first(&root, &(node_array[0]));
    
    	// insert 2
    	node_array[2].data = 2;
    	insert_first(&root, &(node_array[2]));
    
    	// insert 4
    	node_array[4].data = 4;
    	insert_first(&root, &(node_array[4]));
    
    	// insert 6
    	node_array[6].data = 6;
    	insert_first(&root, &(node_array[6]));
    
    	// insert 8
    	node_array[8].data = 8;
    	insert_first(&root, &(node_array[8]));
    
    	display(&root);
    
    	// delete 4
    	delete_node_v1(&(node_array[4]));
    	printf("\ndelete data %d\n", 4);
    	display(&root);
    
    	// delete 0
    	delete_node_v1(&(node_array[0]));
    	printf("\ndelete data %d\n", 0);
    	display(&root);
    
    	// delete 8
    	delete_node_v1(&(node_array[8]));
    	printf("\ndelete data %d\n", 8);
    	display(&root);
    
    	// insert 10
    	node_array[10].data = 10;
    	insert_first(&root, &(node_array[10]));
    	printf("\ninsert data %d\n", 10);
    	display(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->next;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->next;
    			if (2 == ptr_node->data) {
    				delete_node(ptr_node);
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ndelete data %d\n", 2);
    	display(&root);
    
    	// insert 12
    	node_array[12].data = 12;
    	insert_first(&root, &(node_array[12]));
    	printf("\ninsert data %d\n", 12);
    	display(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->prev;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->prev;
    			if (10 == ptr_node->data) {
    				delete_node(ptr_node);
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ndelete data %d\n", 10);
    	display(&root);
    
    	return 0;
    }

node 1: 8
    node 2: 6
    node 3: 4
    node 4: 2
    node 5: 0
    
    delete data 4
    node 1: 8
    node 2: 6
    node 3: 2
    node 4: 0
    
    delete data 0
    node 1: 8
    node 2: 6
    node 3: 2
    
    delete data 8
    node 1: 6
    node 2: 2
    
    insert data 10
    node 1: 10
    node 2: 6
    node 3: 2
    
    delete data 2
    node 1: 10
    node 2: 6
    
    insert data 12
    node 1: 12
    node 2: 10
    node 3: 6
    
    delete data 10
    node 1: 12
    node 2: 6
    请按任意键继续. . .

## 3.2 insert\_first - delete\_node\_v1 - display ##

//============================================================================
    // Name        : doubly linked list
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #define MAX_NODE_LEN 401
    #define NULL 0
    
    #include <stdio.h>
    
    typedef struct NODE {
    	int data;
    	struct NODE *prev;
    	struct NODE *next;
    } Node;
    
    Node node_array[MAX_NODE_LEN];
    int node_array_idx = 0;
    
    void insert_first(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    
    	// equality: head->next->prev = node;
    	node->next->prev = node;
    	head->next = node;
    }
    
    void delete_node(const Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	// current node - node
    
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    void delete_node_v1(const Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    void delete_node_v2(Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    
    	node->next = node->next = NULL;
    }
    
    void display(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->next;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->next;
    	}
    }
    
    int main()
    {
    	// 头节点 (非头指针)
    	Node root;
    
    	// initialization
    	// root.prev = &(root);
    	// root.next = &(root);
    	root.prev = root.next = &(root);
    	root.data = 0;
    
    	for (int i = 0; i < MAX_NODE_LEN; ++i)
    	{
    		node_array[i].prev = NULL;
    		node_array[i].next = NULL;
    		node_array[i].data = 0;
    	}
    
    	// insert 0
    	node_array[0].data = 0;
    	insert_first(&root, &(node_array[0]));
    
    	// insert 2
    	node_array[2].data = 2;
    	insert_first(&root, &(node_array[2]));
    
    	// insert 4
    	node_array[4].data = 4;
    	insert_first(&root, &(node_array[4]));
    
    	// insert 6
    	node_array[6].data = 6;
    	insert_first(&root, &(node_array[6]));
    
    	// insert 8
    	node_array[8].data = 8;
    	insert_first(&root, &(node_array[8]));
    
    	display(&root);
    
    	// delete 4
    	delete_node_v1(&(node_array[4]));
    	printf("\ndelete data %d\n", 4);
    	display(&root);
    
    	// delete 0
    	delete_node_v1(&(node_array[0]));
    	printf("\ndelete data %d\n", 0);
    	display(&root);
    
    	// delete 8
    	delete_node_v1(&(node_array[8]));
    	printf("\ndelete data %d\n", 8);
    	display(&root);
    
    	// insert 10
    	node_array[10].data = 10;
    	insert_first(&root, &(node_array[10]));
    	printf("\ninsert data %d\n", 10);
    	display(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->next;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->next;
    			if (2 == ptr_node->data) {
    				delete_node_v1(ptr_node);
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ndelete data %d\n", 2);
    	display(&root);
    
    	// insert 12
    	node_array[12].data = 12;
    	insert_first(&root, &(node_array[12]));
    	printf("\ninsert data %d\n", 12);
    	display(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->prev;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->prev;
    			if (10 == ptr_node->data) {
    				delete_node_v1(ptr_node);
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ndelete data %d\n", 10);
    	display(&root);
    
    	return 0;
    }

## 3.3 insert\_first - delete\_node\_v1 - display\_v1 ##

//============================================================================
    // Name        : doubly linked list
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #define MAX_NODE_LEN 401
    #define NULL 0
    
    #include <stdio.h>
    
    typedef struct NODE {
    	int data;
    	struct NODE *prev;
    	struct NODE *next;
    } Node;
    
    Node node_array[MAX_NODE_LEN];
    int node_array_idx = 0;
    
    void insert_first(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    
    	// equality: head->next->prev = node;
    	node->next->prev = node;
    	head->next = node;
    }
    
    void delete_node(const Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	// current node - node
    
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    void delete_node_v1(const Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    void delete_node_v2(Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    
    	node->next = node->next = NULL;
    }
    
    void display(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->next;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->next;
    	}
    }
    
    void display_v1(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->prev;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->prev;
    	}
    }
    
    int main()
    {
    	// 头节点 (非头指针)
    	Node root;
    
    	// initialization
    	// root.prev = &(root);
    	// root.next = &(root);
    	root.prev = root.next = &(root);
    	root.data = 0;
    
    	for (int i = 0; i < MAX_NODE_LEN; ++i)
    	{
    		node_array[i].prev = NULL;
    		node_array[i].next = NULL;
    		node_array[i].data = 0;
    	}
    
    	// insert 0
    	node_array[0].data = 0;
    	insert_first(&root, &(node_array[0]));
    
    	// insert 2
    	node_array[2].data = 2;
    	insert_first(&root, &(node_array[2]));
    
    	// insert 4
    	node_array[4].data = 4;
    	insert_first(&root, &(node_array[4]));
    
    	// insert 6
    	node_array[6].data = 6;
    	insert_first(&root, &(node_array[6]));
    
    	// insert 8
    	node_array[8].data = 8;
    	insert_first(&root, &(node_array[8]));
    
    	display_v1(&root);
    
    	// delete 4
    	delete_node_v1(&(node_array[4]));
    	printf("\ndelete data %d\n", 4);
    	display_v1(&root);
    
    	// delete 0
    	delete_node_v1(&(node_array[0]));
    	printf("\ndelete data %d\n", 0);
    	display_v1(&root);
    
    	// delete 8
    	delete_node_v1(&(node_array[8]));
    	printf("\ndelete data %d\n", 8);
    	display_v1(&root);
    
    	// insert 10
    	node_array[10].data = 10;
    	insert_first(&root, &(node_array[10]));
    	printf("\ninsert data %d\n", 10);
    	display_v1(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->next;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->next;
    			if (2 == ptr_node->data) {
    				delete_node_v1(ptr_node);
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ndelete data %d\n", 2);
    	display_v1(&root);
    
    	// insert 12
    	node_array[12].data = 12;
    	insert_first(&root, &(node_array[12]));
    	printf("\ninsert data %d\n", 12);
    	display_v1(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->prev;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->prev;
    			if (10 == ptr_node->data) {
    				delete_node_v1(ptr_node);
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ndelete data %d\n", 10);
    	display_v1(&root);
    
    	return 0;
    }

node 1: 0
    node 2: 2
    node 3: 4
    node 4: 6
    node 5: 8
    
    delete data 4
    node 1: 0
    node 2: 2
    node 3: 6
    node 4: 8
    
    delete data 0
    node 1: 2
    node 2: 6
    node 3: 8
    
    delete data 8
    node 1: 2
    node 2: 6
    
    insert data 10
    node 1: 2
    node 2: 6
    node 3: 10
    
    delete data 2
    node 1: 6
    node 2: 10
    
    insert data 12
    node 1: 6
    node 2: 10
    node 3: 12
    
    delete data 10
    node 1: 6
    node 2: 12
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 11]

## 3.4 在任意节点之后插入新节点 ##

//============================================================================
    // Name        : doubly linked list
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #define MAX_NODE_LEN 401
    #define NULL 0
    
    #include <stdio.h>
    
    typedef struct NODE {
    	int data;
    	struct NODE *prev;
    	struct NODE *next;
    } Node;
    
    Node node_array[MAX_NODE_LEN];
    int node_array_idx = 0;
    
    void insert_first(Node *head, Node *node)
    {
    	node->next = head->next;
    	node->prev = head;
    
    	// equality: head->next->prev = node;
    	node->next->prev = node;
    	head->next = node;
    }
    
    void delete_node(const Node *node)
    {
    	Node *prev_node = node->prev;
    	Node *next_node = node->next;
    	// current node - node
    
    	prev_node->next = next_node;
    	next_node->prev = prev_node;
    }
    
    void delete_node_v1(const Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    }
    
    void delete_node_v2(Node *node)
    {
    	// current node - node
    
    	node->prev->next = node->next;
    	node->next->prev = node->prev;
    
    	node->next = node->next = NULL;
    }
    
    void display(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->next;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->next;
    	}
    }
    
    void display_v1(const Node *head)
    {
    	int n = 1;
    
    	Node *node = head->prev;
    	while (node != head)
    	{
    		printf("node %d: %d\n", n, node->data);
    		++n;
    		node = node->prev;
    	}
    }
    
    int main()
    {
    	// 头节点 (非头指针)
    	Node root;
    
    	// initialization
    	// root.prev = &(root);
    	// root.next = &(root);
    	root.prev = root.next = &(root);
    	root.data = 0;
    
    	for (int i = 0; i < MAX_NODE_LEN; ++i)
    	{
    		node_array[i].prev = NULL;
    		node_array[i].next = NULL;
    		node_array[i].data = 0;
    	}
    
    	// insert 0
    	node_array[0].data = 0;
    	insert_first(&root, &(node_array[0]));
    
    	// insert 2
    	node_array[2].data = 2;
    	insert_first(&root, &(node_array[2]));
    
    	// insert 4
    	node_array[4].data = 4;
    	insert_first(&root, &(node_array[4]));
    
    	// insert 6
    	node_array[6].data = 6;
    	insert_first(&root, &(node_array[6]));
    
    	// insert 8
    	node_array[8].data = 8;
    	insert_first(&root, &(node_array[8]));
    
    	display(&root);
    
    	// insert 10
    	node_array[10].data = 10;
    	insert_first(&root, &(node_array[10]));
    	printf("\ninsert data %d\n", 10);
    	display(&root);
    
    	/********************************* traverse function *********************************/
    	{
    		Node *head = &root;
    		Node *ptr_node = head->prev;
    		Node *tmp_node;
    		while (ptr_node != head)
    		{
    			tmp_node = ptr_node->prev;
    			if (8 == ptr_node->data) {
    				// insert 24
    				node_array[24].data = 24;
    				insert_first(ptr_node, &(node_array[24]));
    			}
    
    			ptr_node = tmp_node;
    		}
    	}
    	/********************************* traverse function *********************************/
    
    	printf("\ninsert data %d\n", 24);
    	display(&root);
    
    	return 0;
    }

node 1: 8
    node 2: 6
    node 3: 4
    node 4: 2
    node 5: 0
    
    insert data 10
    node 1: 10
    node 2: 8
    node 3: 6
    node 4: 4
    node 5: 2
    node 6: 0
    
    insert data 24
    node 1: 10
    node 2: 8
    node 3: 24
    node 4: 6
    node 5: 4
    node 6: 2
    node 7: 0
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 12]

## References ##

[https://www.cnblogs.com/skywang12345/p/3561803.html][https_www.cnblogs.com_skywang12345_p_3561803.html]  
[https://www.alphacodingskills.com/ds/circular-doubly-linked-list.php][https_www.alphacodingskills.com_ds_circular-doubly-linked-list.php]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/d5436e78f2924429b8f4ea8c8742a017.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/ff96bcaa60ae40ff8753185a802ac4db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221119/9946934860e14bbc9436ae6807c48f00.png
[https_www.cnblogs.com_skywang12345_p_3561803.html]: https://www.cnblogs.com/skywang12345/p/3561803.html
[20210220093059930.png_pic_center]: https://img-blog.csdnimg.cn/20210220093059930.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210220105335205.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[2021022400252355.png_pic_center]: https://img-blog.csdnimg.cn/2021022400252355.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210220093644531.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20210220094250721.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[20210224003934259.png_pic_center]: https://img-blog.csdnimg.cn/20210224003934259.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20210224003214344.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20210224003339302.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 8]: https://img-blog.csdnimg.cn/2021022400374026.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 9]: https://img-blog.csdnimg.cn/2021022500171983.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 10]: https://img-blog.csdnimg.cn/20210225001830603.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 11]: https://img-blog.csdnimg.cn/20210224000301916.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 12]: https://img-blog.csdnimg.cn/20210224225748752.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[https_www.alphacodingskills.com_ds_circular-doubly-linked-list.php]: https://www.alphacodingskills.com/ds/circular-doubly-linked-list.php