当前位置：首页 > news >正文

数据结构之双链表

news 2025/5/2 19:25:16

2.双链表

在C++中，双链表（Doubly Linked List）是一种常见的数据结构，它允许我们在链表的任何位置高效地插入和删除节点。与单链表不同，双链表的每个节点都包含两个指针：一个指向下一个节点

格式：

 struct 类型名
{
类型1 变量1; // 数据1...
类型n 变量n; // 数据nstruct 类型名 *前向指针变量; // 存储数据元素的地址。在双链表结构里面，存储上一个数据元素
的内存地址
struct 类型名 *后向指针变量; // 存储数据元素的地址。在双链表结构里面，存储下一个数据元素
的内存地址
};

2.1 定义链表节点结构：

首先，需要定义一个链表节点的结构体，该结构体至少包含三个成员：存储数据的部分（数据域）和指向上一个节点的指针、指向下一个节点的指针。（指针域）。

//定义链表节点结构
typedef struct listNode
{int val;//整形数据struct listNode *p_prev;//指向下一个节点的指针struct listNode *p_next;//指向上一个节点的指针
}listNode;

2.2初始化链表头指针

在创建链表之前，需要初始化链表的头指针。头指针是一个指向链表第一个节点的指针。如果链表为空，则头指针通常设置为 NULL 。

//初始化链表头指针
ListNode* head = NULL; // 初始化链表为空链表

在这里插入图片描述

*2.3 创建并添加节点到链表

**接下来，可以通过创建新的节点并将其插入到链表中来构建链表。插入操作可以根据需要在链表的不同位置进行（如头部、尾部或特定位置）。

如果头节点为空，新创建的节点即为头节点

if (head == NULL){// 如果链表为空，新节点即为头节点head = createNode(value);}

在这里插入图片描述

头部插入，让新节点的 p_next 指向头节点，头节点的 p_prev 指向新节点，那么新节点就变成了新的头节点

头节点变化就返回返回新的头节点

//头部添加节点 head：头节点 value：插入的值
//listNode*返回头节点
listNode* insertNodeAtHead(listNode*&head,int value)
{//创建新节点listNode*newHead=createNode(value);//新节点指向头节点newHead->p_next=head;    //让新节点的p_next指向头节点head->p_prev= newHead; //让头节点的p_prev指向新节点return  newHead;   //返回新的头节点}

在这里插入图片描述

尾部插入：如果要在链表尾部添加节点，需要遍历链表直到最后一个节点，然后将最后一个节点的 p_next 指针指向新节点，将新节点的 p_prev 指向尾节点。

头节点没变返回返回原来的头节点（head）

/尾插
listNode* insertNodeATail(listNode*&head,int value)
{//为空，新节点就是头节点if(head==nullptr){head= createNode(value);}else{//定义中间变量遍历listNode *current=head;while(current->p_next){current=current->p_next;}listNode *newNode=createNode(value);newNode->p_prev=current;current->p_next=newNode;}return head;
}

在这里插入图片描述

中间插入：按照一定规则在某个位置插入元素，头节点没变返回返回原来的头节点（head）

//中间插入
listNode* insertNodeAMiddle(listNode*&head,int value)
{if(head==nullptr){head=createNode(value);return  head;}else{//比头节点小if(value<head->val){head= insertNodeAtHead(head,value);return head;}//在中间listNode* first=head;listNode* second=first->p_next;while(second){if(value>=first->val&&value<=second->val){//不用太在意顺序，但是最好对称listNode*newNode=createNode(value);newNode->p_next=second;second->p_prev=newNode;first->p_next=newNode;newNode->p_prev=first;return head;}first=second;second=second->p_next;}//循环结束也没有插入，就是尾插head=insertNodeATail(head,value);}return head;}

在这里插入图片描述

2.4删除链表中的节点

将链表中某个节点删除，删除时要注意，创建节点时申请了内存，删除时要释放内存以防止内存泄露，同时将指针置为空

//删除节点
listNode*deleteNode(listNode* head, int value){if (head == NULL){// 如果链表为空，结束return NULL;}//删除的是头节点else if (head->val == value){//记录新的头节点listNode*newHead = head->p_next;//新的头节点前面为空newHead->p_prev = NULL;//删除头节点。防止内存泄露delete head;//更新头节点head = newHead;}//非头节点else{//从前往后遍历listNode* current = head;//遍历链表 判断current即可，因为要删除的是currentwhile (current){//使用一个指针的方式//找到要删除的元素 current->next->val而不是curren->val是因为要删除节点，如果
// 是curren->val则无法定位到前面的节点信息//所以要删除当前节点的下一个节点if (current->val == value){//要删除的是当前节点//ListNode* needDelNode = current;//不是尾节点 例如：1-2-3删除2 变成1-3if (current->p_next){//更新节点指向 1的p_next指向3  current是2current->p_prev->p_next = current->p_next;//3的p_prev指向1  current是2current->p_next/*->p_next*/->p_prev = current->p_prev;}//尾节点 例如：1-2删除2 变成1else{//1的p_next指向空 current是2current->p_prev->p_next = NULL;}//删除当前节点delete current;current = NULL;//提前结束return head;}//向后遍历current = current->p_next;
}}//执行到此处说明没找到删除的这个节点信息
return head;

删除头节点

在这里插入图片描述

删除尾节点

在这里插入图片描述

删除中间节点

在这里插入图片描述

2.5 清空链表

//清空链表
void  deinitNode(listNode*&head)
{//判断链表是否为空if(head==NULL){cout<<"链表为空"<<endl;}else{listNode*current=head;while(current){listNode*newNode=current;current=current->p_next;delete newNode;newNode=nullptr;}}head=nullptr;}

2.6 完整代码

#include <iostream>
using namespace std;//定义链表节点结构
typedef struct listNode
{int val;//整形数据struct listNode *p_prev;//指向下一个节点的指针struct listNode *p_next;//指向上一个节点的指针
}listNode;
//创建节点 
listNode *createNode(int value)
{ listNode*newNode =new listNode{value};if(newNode!=nullptr){newNode->p_prev=nullptr; // 指向上一个节点的指针 newNode->p_next=nullptr; // 指向上一个节点的指针 }return newNode;//此处可以返回局部变量的地址是因为newNode在堆区，// 生命周期在delete后才结
}//头部添加节点 head：头节点 value：插入的值
//listNode*返回头节点
listNode* insertNodeAtHead(listNode*&head,int value)
{if (head == NULL){// 如果链表为空，新节点即为头节点head = createNode(value);}//创建新节点listNode*newHead=createNode(value);//新节点指向头节点newHead->p_next=head;    //让新节点的p_next指向头节点head->p_prev= newHead; //让头节点的p_prev指向新节点return  newHead;   //返回新的头节点}//尾插
listNode* insertNodeATail(listNode*&head,int value)
{//为空，新节点就是头节点if(head==nullptr){head= createNode(value);}else{//定义中间变量遍历listNode *current=head;while(current->p_next){current=current->p_next;}listNode *newNode=createNode(value);newNode->p_prev=current;current->p_next=newNode;}return head;
}
//中间插入
listNode* insertNodeAMiddle(listNode*&head,int value)
{if(head==nullptr){head=createNode(value);return  head;}else{//比头节点小if(value<head->val){head= insertNodeAtHead(head,value);return head;}//在中间listNode* first=head;listNode* second=first->p_next;while(second){if(value>=first->val&&value<=second->val){//不用太在意顺序，但是最好对称listNode*newNode=createNode(value);newNode->p_next=second;second->p_prev=newNode;first->p_next=newNode;newNode->p_prev=first;return head;}first=second;second=second->p_next;}//循环结束也没有插入，就是尾插head=insertNodeATail(head,value);}return head;}//删除节点
listNode*deleteNode(listNode* head, int value){if (head == NULL){// 如果链表为空，结束return NULL;}//删除的是头节点else if (head->val == value){//记录新的头节点listNode*newHead = head->p_next;//新的头节点前面为空newHead->p_prev = NULL;//删除头节点。防止内存泄露delete head;//更新头节点head = newHead;}//非头节点else{//从前往后遍历listNode* current = head;//遍历链表 判断current即可，因为要删除的是currentwhile (current){//使用一个指针的方式//找到要删除的元素 current->next->val而不是curren->val是因为要删除节点，如果
// 是curren->val则无法定位到前面的节点信息//所以要删除当前节点的下一个节点if (current->val == value){//要删除的是当前节点//ListNode* needDelNode = current;//不是尾节点 例如：1-2-3删除2 变成1-3if (current->p_next){//更新节点指向 1的p_next指向3  current是2current->p_prev->p_next = current->p_next;//3的p_prev指向1  current是2current->p_next/*->p_next*/->p_prev = current->p_prev;}//尾节点 例如：1-2删除2 变成1else{//1的p_next指向空 current是2current->p_prev->p_next = NULL;}//删除当前节点delete current;current = NULL;//提前结束return head;}//向后遍历current = current->p_next;
}}//执行到此处说明没找到删除的这个节点信息
return head;}
//清空链表
void  deinitNode(listNode*&head)
{//判断链表是否为空if(head==NULL){cout<<"链表为空"<<endl;}else{listNode*current=head;while(current){listNode*newNode=current;current=current->p_next;delete newNode;newNode=nullptr;}}head=nullptr;}
//打印链表
void printNode(listNode *head)
{//如果是空链表if(head==nullptr){cout<<"链表为空"<<endl;return;}//前向遍历指针listNode*current=head;//后向遍历指针listNode*current_prev=head->p_prev;//正向while(current){//输出内容cout<< current->val<<" ";current_prev= current;current=current->p_next;}cout<<endl;//反向 1-2-3while(current_prev){//输出内容cout<< current_prev->val<<" ";//向前遍历current_prev= current_prev->p_prev;}cout<<endl;
}
int main()
{//初始化链表listNode*head=nullptr;//插入head=insertNodeAMiddle(head,1);//头head=insertNodeAMiddle(head,5);//尾head=insertNodeAMiddle(head,3);//中间head=insertNodeAMiddle(head,4);head=insertNodeAMiddle(head,2);//打印printNode(head);// 删除head=deleteNode(head,1);//头head=deleteNode(head,5);//尾head=deleteNode(head,3);//中间//打印printNode(head);deinitNode(head);printNode(head);return 0;
}

查看全文

http://www.xdnf.cn/news/229843.html