数据结构学习系列之双向链表的三种插入方式

• 头插法：
• 在双向链表的头结点和第0个结点之间插入新结点，即头插法，代码如下：
• 示例代码：

	int insert_dplink_list_1(node_t *phead,int data){
	
	    if(NULL == phead){
	
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    //创建新结点
	
	    node_t *pnew = NULL;
	    
	    create_dplink_node_2(&pnew,data);
	    //头插到链表
	    pnew->next = phead->next;
	
	    pnew->front = phead;
	
	    if(NULL != phead->next)
	    {
	        phead->next->front = pnew;
	
	    }
	    phead->next = pnew;
	
	    
	
	    return 0;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• 操作步骤：

• 1.创建新结点pnew；

• 2.将新结点的后继指针（即pnew->next）指向头结点的后继指针（phead->next）此处存储的是第0个结点的地址，可能是空指针（NULL）即pnew->next = phead->next；

• 3.再将新结点的前驱地址（即pnew->front）指向头结点的地址，即pnew->front = phead；

• 4.判断是否有第0个结点；

• 5.如果存在，则第0个结点的前驱指针指向新结点的地址，即phead->next->front = pnew；

• 6.最后，头结点的后继指针（phead->next）指向新结点的地址（pnew），即phead->next = pnew；

• 尾插法：

• 在双向链表的最后一个结点后面插入新结点，即尾插法，代码如下：

• 示例代码：

	int insert_dplink_list_2(node_t *phead,int data){
	
	    if(NULL == phead){
	
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    //创建新结点
	
	    node_t *pnew = NULL;
	    
	    create_dplink_node_2(&pnew,data);
	
	    //遍历链表，找到最后一个结点
	
	    node_t *ptemp = phead;
	
	    while(NULL != ptemp->next){
	
	
	        ptemp = ptemp->next;
	
	
	    }
	
	    ptemp->next = pnew;
	
	    pnew->front = ptemp;
	
	    return 0;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

• 操作步骤：
• 1.创建新结点pnew；
• 2.遍历双向链表，找到链表的最后一个结点ptemp；
• 3.尾结点的后继指针指向新结点的地址，即ptemp->next = pnew；
• 4.新结点的前驱指针指向尾结点的地址，即pnew->front = ptemp；
• 任意位置插入：
• 在双向链表的任意一个位置，插入新结点，代码如下：
• 示例代码：

	int insert_dplink_list_3(node_t *phead,int pos,int data){
	
	    if(NULL == phead){
	
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    if(pos < 0){
	
	        printf("插入位置不合理，插入失败\n");
	
	        return -1;
	
	    }
	
	    node_t *ptemp = phead;
	
	    int i = 0;
	
	    for(i = 0; i < pos; i++){
	
	
	        if(NULL == ptemp->next){
	
	            break;
	
	        }
	        
	        ptemp = ptemp->next;
	
	    }
	    if(i < pos){
	
	        printf("插入位置不合理，插入失败\n");
	
	        return -1;
	
	
	    }
	    //创建新结点
	
	    node_t *pnew = NULL;
	    
	    create_dplink_node_2(&pnew,data);
	
	    pnew->next = ptemp->next;
	
	    pnew->front = ptemp;
	
	    if(NULL != ptemp->next)
	    {
	        ptemp->next->front = pnew;
	
	    }
	    ptemp->next = pnew;
	
	    return 0;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

• 操作步骤：
• 1.遍历链表，找到待插入位置的前一个结点，即ptemp;
• 2.创建新结点pnew；
• 3.此处使用头插法插入即可；