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

发布时间:2024年01月20日

双向链表(各种操作合集)

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

方法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
文章来源:https://blog.csdn.net/qq_41878292/article/details/135720782
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。