1、双向链表
1）特点:
每一个节点除了数据域，还有下指针域指向下一个节点，前指针域指向前一个节点
头节点的前缀是NULL，未尾节点的后缀是NULL
2）代码功能实现思路导图
3）代码
//定义双向链表的节点类型
struct Node
{Node(int data=0):data_(data),next_(nullptr),pre_(nullptr){}int data_; //数据域Node* pre_; //指向前一个节点Node* next_; //指向下一个节点
};//带头节点的双向链表
class DoubleLink
{
public:DoubleLink(){head_ = new Node();}~DoubleLink(){Node* p = head_;while(p != nullptr){head_ = head_->next_;delete p;p = head_;}}public://头插法void InsertHead(int val){Node* node = new Node(val);node->next_ = head_->next_;node->pre_ = head_;if(head_->next_ != nullptr){head_->next_->pre_ = node;}head_->next_ = node;}//尾插法void InsertTail(int val){//是双向链表，需要找到尾节点Node* p = head_;while(p->next_ != nullptr){p = p->next_;}//p->尾节点Node* node = new Node(val);node->pre_ = p;p->next_ = node;}bool Find(int val){Node* p = head_->next_;while(p != nullptr){if(p->data_ == val){return true;}else{p = p->next_;}}}//链表节点输出void Show(){Node*p = head_->next_;while(p != nullptr){cout<<p->data_<<" ";p = p->next_;} cout<<endl;}//节点删除void Remove(int val){Node* p = head_->next_;while(p != nullptr){if(p->data_ == val){//删除p指向的节点p->pre_->next_ = p->next_;if(p->next_ != nullptr){p->next_->pre_ = p->pre_;}delete p;return ;//删除一个就结束//删除所有符合条件的节点/*Node* next = p->next_;delete p;p = next;*/}else{p = p->next_;}}}private:Node* head_;//指向头节点
};
4）代码测试
int main()
{DoubleLink dlink;dlink.InsertHead(10);dlink.InsertHead(100);dlink.InsertHead(1000);dlink.Show();dlink.InsertTail(20);dlink.InsertTail(200);dlink.InsertTail(2000);dlink.Show();dlink.InsertHead(300);dlink.Show();dlink.Remove(100);dlink.Show();dlink.Remove(200);dlink.Show();dlink.Remove(300);dlink.Show();}
测试结果：
2、双向循环链表
C++list容器底层就是双向循环链表
特点:
每一个节点除了数据域，还有下指针域指向下一个节点，前指针域指向前一个节点
头节点的前部指向末尾节点，未尾节点的前部指向头节点
代码实现
#include<iostream>using namespace std;//定义双向循环链表的节点类型
struct Node
{Node(int data = 0):data_(data),next_(nullptr),pre_(nullptr){}int data_;//数据域Node* pre_;//指向前一个节点Node* next_;//指向下一个节点
};//带头节点的双向循环链表
class DoubleCircleLink
{
public:DoubleCircleLink(){head_ = new Node();head_->next_ = head_;head_->pre_ = head_;}~DoubleCircleLink(){Node* p = head_->next_;while (p != head_){ head_->next_ = p->next_;p->next_->pre_ = head_;delete p;p = head_->next_; //让p重新指向第一个节点，进行删除}delete head_;head_ = nullptr;}//头插法 O(1)void InsertHead(int val){Node* node = new Node(val);node->next_ = head_->next_;node->pre_ = head_;head_->next_->pre_ = node;head_->next_ = node;}//尾插法 O(1)void InsertTail(int val){Node* node = new Node(val);node->next_ = head_;node->pre_ = head_->pre_;head_->pre_->next_ = node;head_->pre_ = node;}//链表节点输出void Show(){Node* p = head_->next_;while (p != head_){cout << p->data_ << " ";p = p->next_;}cout << endl;}//节点删除void Remove(int val){Node* p = head_->next_;while (p != head_){if (p->data_ == val)//找到所需删除元素，进行删除{p->pre_->next_ = p->next_;p->next_->pre_ = p->pre_;delete p;p = nullptr;return;//删一个就结束//删除所有符合条件的节点/*Node* next = p->next_;delete p;p = next;*/}else{p = p->next_;}}}private:Node* head_;//头节点};
测试
int main()
{DoubleCircleLink dlink;dlink.InsertHead(10);dlink.InsertHead(100);dlink.InsertHead(1000);dlink.Show();dlink.InsertTail(20);dlink.InsertTail(200);dlink.InsertTail(2000);dlink.Show();dlink.InsertHead(300);dlink.Show();dlink.Remove(100);dlink.Show();dlink.Remove(200);dlink.Show();dlink.Remove(300);dlink.Show();}
运行结果
