c++数据结构算法复习基础-- 5 -- 线性表-双向链表/双向循环链表-常用操作接口-复杂度分析

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();

}

运行结果