带头双向链表的结构

看下面的图，就是我今天要给大家分享有结构——带头双向循环链表。这里的头是不存放任何数据的，就是一个哨兵卫的头结点。

用代码来表示每一个节点就是这样的：

• 数据域和指针域
• 两个指针，一个指向前驱结点，一个指向后继结点
• 给定两个构造函数，有参和无参，分别对结点的指针域和数据域进行初始化

template <class DateType>
struct LinkNode
{
      //数据域
      DateType data;
      //两个指针
      LinkNode<DateType>* prev;
      LinkNode<DateType>* next;
      LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next){}
      LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next){}
};

带头双向链表的接口实现

要实现的接口

LinkList();//构造函数，初始化头节点
LinkList(const LinkList<DateType>& list2);//拷贝构造，进行两个链表的拷贝
~LinkList();//析构函数，用来清除链表，释放结点空间
int Length();//求双向循环链表的长度
void CreateList(int n);//常见n个结点的双向循环链表
bool GetElem(int pos,DateType& data);//得到pos位置结点的元素值
LinkNode<DateType>* Locate(int i ,int back_pos);//定位元素，当back_pos=0的时候，从头节点向前查询第i个元素，back_pos！=0的时候，从头节点后查询第i个元素
bool Insert(int pos, const DateType& data, int back_pos);//在pos的位置插入元素，当back_pos！=0的时候，在pos位置后插入元素，当back_pos=0的时候，在pos位置前插入元素
void PrintList(int sign);//输出双向循环链表所有结点的元素值，当sign！=0时，正序打印元素值，当sign=0时，逆序打印
bool Delete(int pos, DateType& data,int back_pos);//删除pos位置的结点

双向链表的小框架

template<class DateType>
class LinkList
{
public:
private:
	LinkNode<DateType>* head;//头节点
};

初始化双向链表

在初始化双链表的过程中，我们要开好一个头节点，作为哨兵卫的头节点，然后返回这个节点的指针，接口外面只要用一个节点指针接受这个返回值就好了

//构造函数,初始化一个循环双链表
	LinkList()
	{
		head = new LinkNode<DateType>;
		if (head == NULL)
		{
			cout << "内存分配失败" << endl;
			exit(-1);
		}
		head->data = 0;
		head->next = head;
		head->prev = head;
	}

拷贝构造

在拷贝构造中，要注意一件事情，就是最后一个结点的next需要指向头节点，头节点的prev需要指向最后一个结点，形成双向循环链表

本站声明：
1. iCode9 技术分享网（下文简称本站）提供的所有内容，仅供技术学习、探讨和分享；

2. 关于本站的所有留言、评论、转载及引用，纯属内容发起人的个人观点，与本站观点和立场无关；

3. 关于本站的所有言论和文字，纯属内容发起人的个人观点，与本站观点和立场无关；

4. 本站文章均是网友提供，不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属；如您发现该文章侵犯了您的权益，可联系我们第一时间进行删除；

5. 本站为非盈利性的个人网站，所有内容不会用来进行牟利，也不会利用任何形式的广告来间接获益，纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。