带头节点的双向循环链表的增删查改

#include<iostream>
#include<assert.h>
using namespace std;
typedef int DataType;
//循环双向链表，有头节点，最后一个节点连在头节点上
struct LinkNode
{
	//struct默认是公有访问限定符
public:
	LinkNode(const DataType& x)
		:_data(x)
		, _prev(NULL)
		, _next(NULL)
	{}
	~LinkNode()
	{

	}
public:
	DataType _data;
	LinkNode* _prev;
	LinkNode* _next;
};

class List
{
public:
	List()
		:_head(0)
	{
		_head._prev = &_head;
		_head._next = &_head;
	}
	~List()
	{

	}
public:
	void PushBack(const DataType &x)
	{
		LinkNode* tmp = new LinkNode(x);
		LinkNode* tail = &_head;
		while (tail->_next != &_head)
		{
		tail = tail->_prev;
		}
		tmp->_prev = tail;
		_head._prev = tmp;

		tail->_next = tmp;
		tmp->_next = &_head;
	}
	void  PopBack()
	{
		if (_head._next == &_head)
			return;
		LinkNode* del = _head._prev;
		del->_prev->_next = &_head;
		_head._prev = del->_prev;
		delete del;
	}
	void PushFront(const DataType& x)
	{
		LinkNode* tmp = new LinkNode(x);
		tmp->_next = _head._next;
		_head._next->_prev = tmp;

		tmp->_prev = &_head;
		_head._next = tmp;

	}
	void PopFront()
	{
		if (_head._next == &_head)
			return;
		LinkNode* del = _head._next;
		_head._next = del->_next;
		del->_next->_prev = &_head;
		
		delete del;
	}
	LinkNode*  Find(const DataType& x)
	{
		LinkNode* cur = _head._next;
		while (cur != &_head)
		{
			if (cur->_data == x)
				return cur;
			cur = cur->_next;
		}
		return NULL;
	}
	void  Erase(LinkNode* pos)
	{
		assert(pos);
		if (_head._next == &_head)
			return;
		LinkNode* prev = pos->_prev;
		LinkNode* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

		delete pos;

	}
	//在pos位置后插入x
	void  Insert(LinkNode* pos,const DataType x)
	{
		assert(pos);
		LinkNode* tmp = new LinkNode(x);
		LinkNode* prev = pos->_prev;
		LinkNode* next = pos->_next;
		prev->_next = tmp;
		tmp->_next = next;

		next->_prev = prev;
		tmp->_prev = prev;
	}
	void Display()
	{
		LinkNode* cur = _head._next;
		while (cur != &_head)
		{
			cout << (cur->_data) << "->";
			cur = cur->_next;
		}
		cout << "Tail" << endl;
	}
	void Clear()
	{
		if (_head._next == &_head)
			return;
		LinkNode* cur = _head._next;
		while (cur!=&_head)
		{
			//全部释放已不需要考虑prevhenext指针
			LinkNode* del = cur;
			cur = cur->_next;
			delete del;
		}
		_head._next = _head._prev = &_head;
	}
private:
	LinkNode _head;
};
void Test1()
{
	List s1;
	s1.PushBack(1);
	s1.PushBack(2);
	s1.PushBack(3);
	s1.PushBack(4);
	s1.PushBack(5);

	s1.Display();

	s1.PopBack();
	s1.PopBack();
	s1.PopBack();
	s1.PopBack();
	s1.PopBack();
	s1.PopBack();
	s1.PopBack();

	s1.Display();
}
void Test2()
{
	List s2;
	s2.PushFront(1);
	s2.PushFront(2);
	s2.PushFront(3);
	s2.PushFront(4);
	s2.PushFront(5);
	s2.PushFront(6);

	s2.Display();

	s2.PopFront();
	s2.PopFront();
	s2.PopFront();
	s2.PopFront();
	s2.Display();

	s2.PopFront();
	s2.PopFront();
	s2.PopFront();
	s2.PopFront();
	s2.PopFront();

	s2.Display();

}
void Test3()
{
	List s2;
	s2.PushFront(1);
	s2.PushFront(2);
	s2.PushFront(3);
	s2.PushFront(4);
	s2.PushFront(5);
	s2.PushFront(6);

	s2.Display();

	LinkNode* ret=s2.Find(6);
	s2.Erase(ret);
	s2.Display();

	/*ret = s2.Find(9);
	s2.Insert(ret, 9);*/


	s2.Clear();
	s2.PushBack(1);
	s2.Display();
}
int main()
{
	Test3();
	system("pause");
	return 0;
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1717909

带头节点的双向循环链表的增删查改

原文：http://10541556.blog.51cto.com/10531556/1717909