数据结构与算法_线性表_双向循环链表_双向循环链表接口实现

双向循环链表

双向循环链表特点

• C++容器 List 就是双向循环链表实现的
• 每一个节点除了数据域，还有next指针域指向下一个节点，pre指针域指向前一个节点
• 头节点的pre指向末尾节点，末尾节点的next指向头节点

双向循环链表接口实现

这个代码实现在上一个双向链表的基础上改的。

#include <iostream>
#include <time.h>
using namespace std;

struct Node
{
	Node(int data = 0)
		:data_(data)
		, next_(nullptr)
		, pre_(nullptr)
	{}   // Module 库的代码风格
	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_;
		}
		delete head_;
		head_ = nullptr;
	}

public:
	// 头插 
	void InsertHead(int val)
	{
		Node *p = new Node(val);
		// 记住修的时候先改新节点的前后，再次改head后边的节点，最后改head
		p->next_ = head_->next_;
		p->pre_ = head_;
		head_->next_->pre_ = p;
		head_->next_ = p;
	}

	// 尾插法 O(1)
	void InsertTail(int val)
	{
		Node *p = head_->pre_;  // P指向尾结点
		Node *node = new Node(val);
		p->next_ = node;
		node->pre_ = p;
		node->next_ = head_;
		head_->pre_ = node;
	}
	// show
	void Show() const
	{
		Node *p = head_->next_;
		while (p != head_)
		{
			cout << p->data_ << " ";
			p = p->next_;
		}
		cout << endl;

	}

	// 删除节点 
	void RemoveAll(int val)
	{
		Node *p = head_->next_;
		while (p != head_)
		{
			if (val == p->data_)
			{
				p->pre_->next_ = p->next_;// p前指向p后
				p->next_->pre_ = p->pre_;
				delete p;
				return;
			}
			else
			{
				p = p->next_;
			}
		}
	}

	// 查询 
	bool Find(int val)
	{
		Node *p = head_->next_;
		while (p != head_)
		{
			if (p->data_ == val)
			{
				return true;
			}
			else
			{
				p = p->next_;
			}
		}

	}
private:
	Node *head_;

};

int main()
{
	DoubleCircleLink dlink;

	dlink.InsertTail(1);
	dlink.InsertTail(2);
	dlink.InsertTail(3);
	dlink.InsertTail(4);
	dlink.InsertTail(5);
	dlink.Show();

	dlink.InsertHead(6);
	dlink.Show();

	dlink.RemoveAll(2);
	dlink.Show();
	dlink.RemoveAll(5);
	dlink.Show();
	system("pause");
	return 0;
}