在处理单向链表的问题时像删除指定的某个节点和排序问题中我们经常也要对找到的这个节点的前一个节点和后一个节点进行操作但是由于单向链表的特性我们不好对找到的这个节点的前一个节点进行表示解决这些问题时我们只能一开始就只找到这个节点的前一个节点这样使我们对结束条件条件的分析变得复杂容易出现问题。双向链表顾名思义就是组成链表的每个节点除了数据域本身还有两个指针域一个指向后面的节点一个指向前面的节点。1.双向链表的创建思路域与单向链表类似就是创建一个头节点不关心它的数据域它的next指向NULL它的prev也指向NULL表示这个节点向前不指向任意一个节点向后也不指向任意一个节点。创建结束后返回指向头节点的指针后续对链表的操作要通过这个指针操作。#include stdio.h #include stdlib.h typedef int data_t; typedef struct node { data_t data; struct node *prev; struct node *next; }node_t; node_t *dlinklist_create(void) { node_t *head malloc(sizeof(node_t));//创建头节点 if(headNULL)//判断头节点是否创建成功 { printf(dlinklist_create fail\n); return NULL; } head-prev NULL;//头节点向前不指向任意一个节点 head-next NULL;//头节点向后不指向任意一个节点 return head;//返回头节点的地址 }2.双向链表的头插无效的不能插思路我们先看一般情况对非空链表的头插首先要创建一个新节点pnew,将要插的数据放到新节点的数据域中然后让原先头节点向前指向新节点让新节点向后指向原先的首节点最后让新节点向前指向头节点头节点向后指向新节点这样数据就插入进来了。再看特殊情况空链表没有首节点没有让首节点向前指向新节点的操作剩下的操作就是一样适用的。int dlinklist_insert(node_t *phead,data_t data)//0表示成功 非0不成功 { if(pheadNULL) { return -1; } node_t *pnew malloc(sizeof(node_t));//创建新节点 if(pnewNULL)//判断新节点是否创建成功 { printf(new node create fail\n); return -1; } pnew-data data;//新节点创建成功后将要插入的数据放进新节点的数据域里 if(phead-next!NULL)//只有不是空链表才执行这段代码 { phead-next-prev pnew; } pnew-next phead-next;//对于空链表插入新节点pnew-nextphead-nextNULL是正确的 pnew-prev phead; phead-next pnew; return 0; }3.判断双向链表是不是空链表。思路空链表只有一个头节点头节点的nextNULL。int is_empty(node_t *phead)//返回1是空链表 0是非空链表 { if(pheadNULL) { return 0; } if(phead-nextNULL) { return 1; } return 0; }4.双向链表的打印无效链表和空链表不用打思路和单向链表一样从首节点到尾节点依次打印就行。int dlinklist_print(node_t *phead)//返回0表示打印成功 非0不成功 { if(pheadNULL||is_empty(phead)1) { return -1; } node_t *p phead-next;//从首节点开始打印 while(p!NULL)//还有节点没有打印 如果连尾节点也打印了p会等于NULL { printf(%d ,p-data); p p-next;//准备去打印下一个节点 } putchar(\n); return 0; }5.双向链表的尾插、有效节点个数计算、查找、替换都是和单向链表的思路一样按照从首到尾的方向依次判断就行不涉及对当前节点的前一个节点和后一个节点的处理所以思路和步骤与单向链表相同这里不重复书写。6.双向链表的头删无效链表和空链表不能删思路先看一般情况不是只有一个有效节点时p指向首节点让首节点的后一个节点的prev指向头节点让头节点的next指向首节点的后一个节点然后释放首节点。接下来我们来看这个流程适不适用特殊情况当链表只有一个有效节点我们要删除首节点首节点没有后一个节点更无法访问到它的prev步骤一就不能照搬过来出去这个步骤运行剩下的步骤没有任何问题所以我们只需要限制步骤一执行的条件。int dlinklist_delete_head(node_t *phead)//返回0表示头删成功 非0不成功 { if(pheadNULL||is_empty(phead)1) { return -1; } node_t *p phead-next;//从首节点开始 if(p-next!NULL)//不是只有一个有效节点时才执行这一步 { p-next-prev phead;//让首节点的后一个节点的prev指向头节点 } phead-next p-next;//让头节点的next指向首节点的后一个节点 free(p);//释放首节点 p NULL; return 0; }7.双向链表的尾删无效和空链表不用删思路由于单向链表的特性限制单向链表的尾删我们只能找到尾节点的前一个节点然后进行处理。而对于双向链表我们可以精准地找到尾节点让尾节点的前一个节点指向NULL然后释放点尾节点所占的空间只有一个有效节点的链表很容易验证也适用这个步骤。int dlinklist_delete_tail(node_t *phead)//返回0表示操作成功 非0不成功 { if(pheadNULL||is_empty(phead)1) { return -1; } node_t *p phead-next;//从首节点开始找 while(p-next!NULL)//一直找到尾节点 { p p-next; } p-prev-next NULL;//让尾节点的前一个节点成为新的尾节点 free(p);//释放原来的尾节点所占空间 p NULL; return 0; }8.双向链表指定删除某个节点无效和空节点不用删思路与单向链表相比我们也是可以直接定位到要删除的节点然后让他的前一个节点和后一个节点链接起来。对于特殊情况要删除只有一个有效节点的首节点它不指向任意节点我们无法让它的后一节点的prev指向它的前一个节点所以这一步要判断性执行。int dlinklist_delete_key(node_t *phead)//返回0表示操作成功非0不成功 { if(pheadNULL||is_empty(phead)NULL) { return -1; } node_t *p phead-next;//从首节点开始找 while(p!NULLp-data!key)//如果没找完并且也没找到 继续找 //找完了没找到或者找到了都会跳出这个循环 { p p-next; } if(pNULL)//全部节点都判断过了还是没找到 { return -1; } if(p-next!NULL)//找到了 { p-next-prev p-prev;//如果不是删除只有一个有效节点的链表的首节点才执行这一句 } p-prev-next p-next;//让找到的节点的前一个节点指向找到节点的后一个节点 free(p);//释放找到的节点 p NULL; return 0; }9.销毁整个双向链表无效不用销毁思路从首节点到尾节点依次销毁最后销毁指向链表的指针。int dlinklist_destory(node_t **pphead)//因为我们最后要对指向链表的指针进行操作 //这里要传指针的地址 { if(ppheadNULL) { return -1; } node_t *p *pphead;//从头节点开始,头节点也得释放 node_t *q NULL; while(p ! NULL)//所有的节点还没释放完 { q p-next;//先记录一下下一个要释放的节点 free(p); p q;//准备去处理下一个节点 } *pphead NULL;//把指向这个链表的指针置空 防止野指针 return 0; }