本文主要是介绍双向，带头节点，带环链表的基本操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前面已经介绍过了不带头节点，不带环的双向链表，以下将介绍带头节点，带环的双向链表的基本操作。
不带头结点时，用一个头指针代表整个链表。带头节点，则用头结点来表示整个链表。此时，头结点的数据域是没有意义的，对其任意赋值即可。如下图：
当链表是单向时，只有一个next指针指向下一个节点。而双向时，除有next指向下一个节点外，还有一个prev指针指向前一个结点。
当链表不带环时，链表的最后一个元素的next域为空，而带环时，链表的最后一个结点的next域要指向头结点，而头结点的prev域要指向链表的最后一个节点。这样，整个链表就呈一个环状。
通过上述分析，便可知道，当双向链表为空时，头结点的next域和prev域均指向头结点。
1. 链表的结点结构
上述分析已经知道，双向链表的一个节点包括三部分：数据域，next域，prev域，所以，结点结构定义如下：
typedef char DlinklistType;//将节点的数据域类型统一表示 //定义双向链表的节点结构
typedef struct DlinkNode
{DlinklistType data;//数据域struct DlinkNode* next;//指向下一个节点struct DlinkNode* prev;//指向上一个节点
}DlinkNode;
2. 双向链表的初始化
因为该链表是带头节点的，所以初始化时，要创建一个头结点来表示整个链表，此时，还没有真正的节点，所以链表为空，所以将头结点的next指针和prev指针均指向自己，数据任意赋值。
因为初始化时，要使头指针指向头结点，即要改变头指针的指向，所以，在函数传参时，传的是头指针的地址，即二级指针（在测试函数中定义的是头指针，即DlinkNode*类型的变量）。
代码如下：
//创建结点
DlinkNode* CreateNode(DlinklistType value)
{DlinkNode* new_node = (DlinkNode*)malloc(sizeof(DlinkNode));new_node->data = value;new_node->next = new_node;//初始时，使节点的两个指针域均指向自身 new_node->prev = new_node;return new_node;
}//初始化双向链表
void InitDlinklist(DlinkNode** phead)
{if(phead == NULL){ //非法输入return;} //申请头结点,使头指针指向新节点*phead = CreateNode(0);return;
} 因为再对头指针初始化后，头指针始终指向头结点，对链表进行以下操作（不包括销毁链表）时，改变的是头结点的相关指针域，而未改变头指针的指向，所以，在函数传参时传的均是头指针，即一级指针。
3. 对双向链表进行尾插
在尾插时，首先要找到尾节点，因为链表是带环的双向链表，所以，可以通过头结点的prev指针找到尾节点。然后在尾节点后面创建一个新节点进行插入。
在插入时，需要改变四个指针的指向，两两一组，分别为：
（1）原尾节点的next域要指向新节点，新节点的prev要指向原尾节点；
（2）新节点的next域要指向头结点，头结点的prev要指向新节点。
代码如下：
//对双向链表进行尾插
//head为双向链表的头指针，value为要插入的值
void DlinklistPushBack(DlinkNode* head,DlinklistType value)
{if(head == NULL){//非法输入return;}DlinkNode* new_node = CreateNode(value);//创建新节点DlinkNode* tail = head->prev;//找到尾节点//一共要修改四个指针，两两一组进行修改 //tail和new_nodetail->next = new_node;new_node->prev = tail;//new_node和headhead->prev = new_node;new_node->next = head;return;
}
4. 对双向链表进行尾删
要删除尾节点
（1）首先，要判断链表是否为空。为空的删除失败。链表为空的条件是头结点head满足：
head->next = head 或 head->prev = head（2）若链表不为空。
1）首先要根据头结点的prev指针找到尾节点。
2）再根据尾节点找到它的前一个节点，将找到的前一个节点作为新的尾节点。
4）此时，只需修改两个指针域：将新的尾节点的next指针指向头结点，头结点的prev指针指向新的尾节点
5）最后释放原尾节点即可。
代码如下：
//销毁节点
void DestoryNode(DlinkNode* node)
{free(node);return;
}//对双向链表进行尾删
//head为双向链表的头指针，即头结点的地址
void DlinklistPopBack(DlinkNode* head)
{if(head == NULL){//非法输入return;}if(head->next == head){//空链表return;}//根据头节点找到尾节点DlinkNode* to_delete = head->prev;//根据尾节点找到它的前一个节点DlinkNode* prev_node = to_delete->prev;//修改两个指针的指向，使上一个节点作为新的尾节点prev_node->next = head; head->prev = prev_node;//释放原来的尾节点DestoryNode(to_delete);return;
}
5. 对链表进行头插
首先要创建一个新节点，然后在头结点之后，真正的第一个节点之前插入该新节点，根据头结点可以找到第一个结点，然后修改这三个结点的相关指针域即可：
共需修改四个指针，两两为一组：
（1）头结点的next指向新节点，新节点的prev指向头结点
（2）新节点的next指向第一个结点，第一个结点的prev指向新节点。
代码如下：
//头插
//head为双向链表的头指针，value为要插入的值
void DlinklistPushFront(DlinkNode* head,DlinklistType value)
{if(head == NULL) {//非法输入return;}//创建新节点DlinkNode* new_node = CreateNode(value);//找到第一个节点DlinkNode* next_node = head->next;//需要修改四个指针的指向//head和new_nodehead->next = new_node;new_node->prev = head;//new_node和next_nodenew_node->next = next_node;next_node->prev = new_node;return;
}
6. 头删链表
（1）首先，判断链表是否为空，为空则删除失败
（2）链表不为空：
1）根据头结点找到要删除的第一个结点。
2）使头结点指向要删除结点的下一个节点，使该下一个节点作为新的第一个节点
3）此时，需要修改两个指针的指向，将头结点的next指向下一个节点，下一个节点的prev指向头结点
4）最后，释放要删除的结点即可。
代码如下：
//头删，head为双向链表的头指针
void DlinklistPopFront(DlinkNode* head)
{if(head == NULL){//非法输入return;}if(head->next == head){//空链表return;}//根据头节点找到要删除的第一个节点DlinkNode* to_delete = head->next;//根据要删除的节点找到他的下一个节点DlinkNode* next_node = to_delete->next;//只需改变两个指针，将下一个节点作为新的第一个节点head->next = next_node;next_node->prev = head;//释放要删除的节点 DestoryNode(to_delete);return;
}
7. 在指定位置之前插入节点
要在指定位置之前插入节点
（1）首先，根据指定位置处的节点找到它的前一个节点
（2）然后，将新节点插入到指定结点和它的前一个节点之间。
（3）此时，需要修改四个指针的指向：
1）是前一个节点的next指向新节点，新节点的prev指向前一个节点
2）使新节点的next指向指定结点，指定结点的prev指向新节点
代码如下：
//在指定位置pos之前插入节点
void DlinklistInsert(DlinkNode* head,DlinkNode* pos,DlinklistType value)
{if(head == NULL || pos == NULL){ //非法输入return;}//根据pos找到他的前一个节点DlinkNode* prev_node = pos->prev;DlinkNode* new_node = CreateNode(value);//创建新节点//prev_node/new_nodeprev_node->next = new_node;new_node->prev = prev_node;//new_node/pos new_node->next = pos;pos->prev = new_node;return;
}
8. 在指定位置之后插入节点
与上述类似
（1）首先，根据指定位置处的节点找到它的下一个节点
（2）然后，将新节点插入到指定结点和它的下一个节点之间。
（3）此时，需要修改四个指针的指向：
1）使下一个节点的prev指向新节点，新节点的next指向下一个节点
2）使新节点的prev指向指定结点，指定结点的next指向新节点
代码如下：
//在指定位置之后插入节点
void DlinklistInsertAfter(DlinkNode* head,DlinkNode* pos,DlinklistType value)
{ if(head == NULL || pos == NULL){//非法输入return;}//创建新节点DlinkNode* new_node = CreateNode(value);//根据pos找到他的下一个节点DlinkNode* next_node = pos->next;//pos/new_nodepos->next = new_node;new_node->prev = pos;//new_node/next_nodenew_node->next = next_node;next_node->prev = new_node;return;
}
9. 查找指定值所在的位置
（1）如果链表为空，则查找失败
（2）若链表非空，则对链表从头开始遍历。使指定值和链表的每个节点的数据域进行对比，如果相同，返回该结点的地址，如果不同，指针后移
（3）当链表遍历结束时，还未找到指定值，说明，该值不存在与链表中，则查找失败。注意，链表遍历结束时，即又回到头结点处时。
代码如下：
//查找指定值所在的位置
DlinkNode* DlinklistFind(DlinkNode* head,DlinklistType to_find)
{if(head == NULL){//非法输入return NULL;}if(head->next == head){//空链表return NULL;}//定义cur为当前指针遍历来遍历链表，初始从真正的第一个节点开始DlinkNode* cur = head->next;while(cur != head)//当未遍历完链表时{if(cur->data == to_find)//当找到指定值时{return cur;//返回指定值所在节点的位置}cur = cur->next;//若没找到，继续后移}return NULL;//遍历完链表还没找到
}
10 . 删除指定位置处的节点
（1）首先要判断链表是否为空，为空在删除失败
（2）判断要删除的位置是不是头结点所在的位置。因为头结点代表着整个链表，除销毁链表外不能对其进行删除
（3）若不为（1）（2），根据指定位置找到它的前一个和后一个节点
（4）修改前，后节点的相应指针：使前一个节点的next指向后一个节点，后一个节点的prev指向前一个节点
（5）最后，释放指定位置处的结点。
代码如下：
//删除指定位置的节点
void DlinklistErase(DlinkNode* head,DlinkNode* pos)
{if(head == NULL || pos == NULL){//非法输入return;} if(head->next == head){//空链表return;} if(head == pos){//不能删除头节点return;} //找到指定位置处的下一个节点DlinkNode* next_node = pos->next;//找到指定位置处的上一个节点DlinkNode* prev_node = pos->prev;//修改相应指针的指向next_node->prev = prev_node;prev_node->next = next_node;//释放指定位置处的节点 DestoryNode(pos);return;
}
11. 按值删除节点
（1）如果链表为空，则删除失败
（2）根据上述的find函数先找到该值所在的位置，如果没找到，则删除失败
（3）若找到了，则根据该位置上述的Erase函数对其进行删除
代码如下：
//按值删除
void DlinklistRemove(DlinkNode* head,DlinklistType to_delete_value)
{if(head == NULL){//非法输入return;}if(head->next == head){//空链表return;}//找到指定值所在的位置DlinkNode* to_delete = DlinklistFind(head,to_delete_value);if(to_delete == NULL){//没找到该节点return;}//根据指定位置删除节点 DlinklistErase(head,to_delete);return;
}
12. 删除指定值所在的所有节点
与上述类似
（1）链表为空，删除失败
（2）链表不为空，先找到指定值所在的位置，然后根据位置删除节点
（3）一直循环过程（2），直到找不到指定值所在的位置，说明已经删除指定值处的所有结点
代码如下：
//按值删除所有
void DlinklistRemoveAll(DlinkNode* head,DlinklistType to_delete_value)
{if(head == NULL){//非法输入return;}if(head->next == head){//空链表return;}//根据指定值找所在的位置DlinkNode* to_delete = DlinklistFind(head,to_delete_value);while(to_delete != NULL)//如果一直能找到指定值所在的位置{DlinklistErase(head,to_delete);//则对其进行删除to_delete = DlinklistFind(head,to_delete_value);}return;//此时，所有指定值所在的节点已全部删除
}
13. 销毁链表
在对链表初始化前，链表只用一个头指针进行表示，所以销毁链表后，即恢复到初始化前的状态。
（1）首先，遍历链表，将链表的结点一个个进行释放
（2）然后，在对头结点进行释放
（3）因为头结点未释放前，由头指针指向。而释放后，头指针指向的是一个无效的 地址，即头指针变成了野指针。所以头结点释放后，要对头指针置空。此时，要改变头指针的指向，所以，函数传参时要传头指针的地址即二级指针。
代码如下：
//销毁链表
void DestoryDlinklist(DlinkNode** phead)
{if(phead == NULL){//非法输入return;}//遍历链表对各节点进行释放DlinkNode* to_delete = (*phead)->next;while(to_delete != *phead){DlinkNode* next_node = to_delete->next;DestoryNode(to_delete);to_delete = next_node;}//释放头节点DestoryNode(*phead);//头指针置空 *phead = NULL;}
14. 统计双向链表的长度
（1）首先判定链表是否为空，为空，则返回0
（2）然后从第一个结点开始遍历，遍历到一个结点，长度加1，直到回到头结点
代码如下：
//统计双向链表的长度
int DlinklistSize(DlinkNode*head)
{if(head == NULL){ //非法输入return -1; } if(head->next == head)//该部分代码可包含在下述代码中{ //空链表return 0;} //从第一个节点开始遍历，遍历一个，长度加1，直到回到头节点 DlinkNode* cur = head->next;int size = 0;while(cur != head){ size++;cur = cur->next;} return size;
}
这篇关于双向，带头节点，带环链表的基本操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
