C语言的双向链表头插法和尾插法，指定节点删除

前言

双向链表和单链表的唯一区别就是多个一个指针域而已，该指针域可以访问链表的上一个节点。

关于构造双向链表的过程我们常见的有两种方法，和单链表一样：头插法和尾插法。
头插法：字面意思也是很好理解，每次插入的元素在上一个节点之前
尾插法：字面意思也表达出了每次的元素插入会在上一个节点之后
详细插入过程可以参考如下

---

头插法

头插法基本过程如下图，已经描述的很清楚了

简单讲一下，这里需要有一个指向的顺序问题
第三步和第四步是需要有先后关系的
第三步： head -> next -> prev = p ，这一步是更新head节点下一个节点的pre域链接的；而第四步: head -> next = p，则是更新head的next域。
如果第四步在前，第三步的head -> next -> prev 就变为了 p -> prev = p，显然不合理。

实现算法如下（文末有完整源码）

Data *insert_head(int n) {
    Data *head = (Data *)malloc(sizeof(Data));
    head->next = NULL;
    head -> prev = head;
    Data *r = head -> next;
    while (n--)
    {
        int tmp;
        Data *p = (Data *)malloc(sizeof(Data));
        scanf("%d", &tmp);
        p -> data = tmp;
        /*考虑头节点的next域为空，防止访第3步head->next->prev访问到空的指针*/
        if (head -> next == NULL) { 
             p -> next = NULL;
             p -> prev = head;
             head -> next = p;
        } else
        {
            p -> next = head -> next;
            p -> prev = head;
            head -> next -> prev = p;
            head -> next = p;
        }
    }
    return head -> next;
}

尾插法

具体步骤如下：

具体指向的过程看图就可以，非常清晰
这里多了一个第五步，是为了保证临时节点r的移动，持续指向插入节点的上一个节点。
实现代码如下:

Data *insert_tail(int n){
    Data *head = (Data *)malloc(sizeof(Data));
    head->next = NULL;
    head -> prev = head;
    Data *r = head;
    while (n --){
        int tmp;
        Data *p = (Data *)malloc(sizeof(Data));
        scanf("%d", &tmp);
        p -> data = tmp;
		/*同样为了防止第三部 r->next->prev访问到了空节点，提前进行处理*/
        if (r -> next == NULL) {
            p -> next = NULL;
            p -> prev = r;
            r -> next = p;
        } else  {
            p -> next = NULL;
            p ->prev = r;
            r -> next -> prev = p;
            r -> next = p;
        }
        
        r = p;
    }
    return head -> next;
}

删除节点

删除过程很简单，主要是上下节点的直接指向：

1. 找到要删除的节点p，以及其上一个节点r
2. 重新指向r的next域，跳过需要删除的节点

Data *delete_list(Data *head, int data) {
    Data *p;
    Data *r = head ;
    /*找到要删除的节点，命名为p，同时需要获取p的上一个节点r*/
    while (r->next) {
        if (r-> next ->data == data) {
            p = r->next;
            break;
        }
        r = r->next;
    }
	/*删除节点p*/
    r->next = p -> next;
    p->next->prev = r;

    p = NULL;
    return head;
}

测试代码如下

#include <stdio.h>
#include <stdlib.h>

typedef struct DoubleLink {
    int data;
    struct DoubleLink *next;
    struct DoubleLink *prev;
}Data;

/*打印链表,先next顺序打印，再prev逆序打印*/
void print_list(Data *head) {
	if(head == NULL)
		return;
    printf("next \n");
	while (head -> next) {
		printf("%d ",head->data);
		head = head -> next;
	}
    printf("%d\n",head->data);
    Data *p = head;
    printf("\nprev \n");
    while (p -> prev != p) {
        printf("%d ",p->data);
        p = p ->prev;
    }
	printf("\n");
}

/*尾插法*/
Data *insert_tail(int n){
    Data *head = (Data *)malloc(sizeof(Data));
    head->next = NULL;
    head -> prev = head;
    Data *r = head;
    while (n --){
        int tmp;
        Data *p = (Data *)malloc(sizeof(Data));
        scanf("%d", &tmp);
        p -> data = tmp;

        if (r -> next == NULL) {
            p -> next = NULL;
            p -> prev = r;
            r -> next = p;
        } else  {
            p -> next = NULL;
            p ->prev = r;
            r -> next -> prev = p;
            r -> next = p;
        }
        
        r = p;
    }
    return head -> next;
}

/*头插法*/
Data *insert_head(int n) {
    Data *head = (Data *)malloc(sizeof(Data));
    head->next = NULL;
    head -> prev = head;
    Data *r = head -> next;
    while (n--)
    {
        int tmp;
        Data *p = (Data *)malloc(sizeof(Data));
        scanf("%d", &tmp);
        p -> data = tmp;
        if (head -> next == NULL) {
             p -> next = NULL;
             p -> prev = head;
             head -> next = p;
        } else
        {
            p -> next = head -> next;
            p -> prev = head;
            head -> next -> prev = p;
            head -> next = p;
        }
    }
    return head -> next;
    
}

/*删除链表,删除节点data为2的链表*/
Data *delete_list(Data *head, int data) {
	if(head == NULL)
		return NULL;
    Data *p;
    Data *r = head ;
    while (r->next) {
        if (r-> next ->data == data) {
            p = r->next;
            break;
        }
        r = r->next;
    }

    r->next = p -> next;
    p->next->prev = r;

    p = NULL;
    return head;
}

int main()
{
    printf("construct the double list tail\n");
    Data * head = insert_tail(5);
    print_list(head);

    printf("construct the double list head\n");
    Data * tail = insert_head(5);
    print_list(tail);

    printf("delete the double list node\n");

    Data * test = insert_head(5);
    Data *result = delete_list(test,2);
    print_list(result);
    return 0;
}

输出结果如下:

construct the double list tail
1 2 3 4 5

next 
1 2 3 4 5
prev 
5 4 3 2 1 

construct the double list head
1 2 3 4 5

next 
5 4 3 2 1
prev 
1 2 3 4 5 

delete the double list node
1 2 3 4 5
next 
5 4 3 1
prev 
1 3 4 5