数据结构学习之双向链表（各种操作合集）

双向链表（各种操作合集）

双向链表的两种创建方式：

方法1：根据函数的返回值创建

• 通过返回值返回所申请的头结点所在的内存空间首地址，即创建双向链表的头结点，代码如下：

• 示例代码：

	node_t *create_dplink_node_1(){
	
	    node_t *phead = (node_t *)malloc(sizeof(node_t));
	    
	    if(NULL == phead){
	
	        printf("内存分配失败\n");
	
	        exit(-1);
	
	    }
	
	    phead->data = -1;
	    phead->front = NULL;
	    phead->next = NULL;
	
	    return phead;
	
	}

• 注意事项：
• 1.分配完头结点的内存地址空间后，一定要检查内存分配是否成功；
• 2.若头结点的内存分配失败，需要使用shell命令exit(-1)退出；
• 3.双向链表的每个结点都有三个部分，即前驱、元素、后继（front、data、next），而头结点的数据域可以不储存任何数据，头结点的数据域在此处，我将其被赋值 -1；
• 4.头结点的指针域（含前驱、后继）被赋值 NULL，表示此时的双向链表只有一个头结点；

方法2：根据地址传参创建

• 使用地址传参的方法创建双向链表的头结点，代码如下：
• 示例代码：

	int create_dplink_node_2(node_t **phead,int data){
	
	    if(NULL == phead){
	
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    *phead = (node_t *)malloc(sizeof(node_t));
	
	    if(NULL == *phead){
	
	
	        printf("内存分配失败\n");
	
	        return -1;
	
	    }
	
	    (*phead)->data = data;
	    (*phead)->front = NULL;
	    (*phead)->next = NULL;
	
	    return 0;
	
	}

• 注意事项：
• 1.所传入的形参必须是二级指针变量，因为二级指针用来存储一级指针变量的地址，即所申请的双向链表头结点在内存空间的地址；
• 2.形参传入到创建双向链表头结点的功能函数后，一定要做入参合理性检查；
• 3.同方法1一样，分配完头结点的内存地址空间后，一定要检查内存分配是否成功；
• 4.头结点的数据域（即链表元素）被赋值 -1；
• 5.头结点的指针域（含前驱、后继）被赋值 NULL；

双向链表的三种插入方式：

头插法：

• 在双向链表的头结点和第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.创建新结点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.创建新结点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.遍历链表，找到待插入位置的前一个结点，即ptemp;
• 2.创建新结点pnew；
• 3.此处使用头插法插入即可；

双向链表的三种删除方式 ：

头删法：

• 删除双向链表头结点后的结点，即头删法，代码如下：
• 示例代码：

	int delete_dplink_list_1(node_t *phead){
	
	    if(NULL == phead){
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    if(NULL == phead->next){
	
	        printf("链表只有一个头结点，无其他的结点\n");
	
	        return -1;
	
	    }
	
	    node_t *pdel = phead->next;
	
	    if(NULL != pdel->next)
	    {
	        pdel->next->front = phead;
	    }
	
	    phead->next = pdel->next;
	
	    free(pdel);
	
	    pdel = NULL;
	
	    return 0;
	
	}

• 操作步骤：
• 1.定义待删结点pdel,并将待删结点的指针指向头结点的后继结点地址，即node_t *pdel = phead->next；
• 2.判断双向链表是否有第0个结点；
• 3.若有，则让待删除结点的下一个结点的前驱指针指向头结点地址，即pdel->next->front = phead；
• 4.最后，头结点的后继指针指向待删除结点的下一个结点的地址，即phead->next = pdel->next；
• 5.用free函数释放待删结点所占用的空间，即 free(pdel)；
• 6.防止野指针产生，给待删结点的地址赋值NULL，即pdel = NULL；

尾删法：

• 删除双向链表的最后一个结点，即尾删法，代码如下：
• 示例代码：

	int delete_dplink_list_2(node_t *phead){
	
	    if(NULL == phead){
	
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    if(NULL == phead->next){
	
	
	        printf("链表只有一个头结点，无其他的结点\n");
	
	        return -1;
	
	    }
	
	    //遍历链表，找到倒数第二个结点
	
	    node_t *ptemp = phead;
	
	    while(NULL != ptemp->next->next){
	
	
	        ptemp = ptemp->next;
	
	
	    }
	
	
	    free(ptemp->next);
	
	    ptemp->next = NULL;
	
	    return 0;
	
	}

• 操作步骤：
• 1.利用while循环，遍历双向链表，找到倒数第二个结点，即ptemp；
• 2.释放ptemp后继指针，并赋值NULL，这样就删除了双向链表的尾结点；
• 友情提示：
• 单向链表和双向链表的尾删法基本一致；

任意位置删除旧节点：

• 选择结点在链表中的位置，然后根据链表元素的位置，删除待删结点，代码如下：

• 示例代码：

	int delete_dplink_list_3(node_t *phead,int pos){
	
	    if(NULL == phead){
	
	
	        printf("入参为NULL\n");
	
	        return -1;
	
	    }
	
	    if(NULL == phead->next){
	
	
	        printf("链表只有一个头结点，无其他的结点\n");
	
	        return -1;
	
	    }
	
	    if(pos < 0){
	
	        printf("删除位置不合理，删除失败\n");
	
	        return -1;
	
	    }
	    node_t *ptemp = phead;
	
	    int i = 0;
	
	    for(i = 0; i < pos; i++){
	
	        ptemp = ptemp->next;
	
	
	        if(NULL == ptemp->next){
	
	            break;
	
	        }
	        
	        
	
	    }
	    if(i < pos){
	
	        printf("删除位置不合理，删除失败\n");
	
	        return -1;
	
	
	    }
	    node_t *pdel = ptemp->next;
	
	    if(NULL != pdel->next)
	    {
	        pdel->next->front = ptemp;
	    }
	
	    ptemp->next = pdel->next;
	
	    free(pdel);
	
	    pdel = NULL;
	
	    return 0;
	
	}

• 操作步骤：
• 1.找到双向链表待删结点的前一个结点ptemp;
• 2.此处类比使用上述头删法即可；

双向链表的翻转

• 与单向链表翻转的思路一致，都是 将第0个数据结点后面的所有数据结点，依次头插到头结点和第0个数据结点之间即可，代码如下：
• 示例代码：

//翻转
int filp_dplink_list(node_t *phead){

    if(NULL == phead){
        printf("入参为NULL,请检查..\n");
        return -1;
    }

    if(NULL == phead->next){

        printf("只有一个头结点\n");

        return -1;
    }

    if(NULL == phead->next->next){

        printf("只有一个数据结点\n");

        return -1;

    }

    node_t *p = phead->next;

    node_t *q = p->next;

    node_t *ptemp = NULL;

    p->next = NULL;

    while(NULL != q){

        ptemp = q->next;

        q->next = phead->next;

        q->front = phead;

        phead->next->front = q;

        phead->next = q;

        q = ptemp;

    }

    return 0;
}

• 注意事项：
• 1.定义一个指针，用来保存指针q的指针域，即ptemp = q->next，以便于循环遍历双向链表的所有数据结点，即每次循环结束前，令q = ptemp，就可以继续向后遍历其他的数据结点；
• 2.采用头插法的形式，并利用while循环，将第1个数据结点及其以后的所有数据结点依次头插到头结点和第0个数据结点之间，直到指针q为NULL，即原双向链表的第0个结点的指针域为NULL，就完成了双向链表的所有数据结点的翻转；

相关提示：

• 其他的操作，诸如双向链表的节点查找、节点修改、节点排序、节点去重、节点的清空、节点的销毁等相关操作均与单向链表的操作保持一致，本文不再赘述；
• 可以参考以下单向链表各种操作合集链接：

	https://blog.csdn.net/qq_41878292/article/details/135679744