数据结构——循环链表

循环链表，故名思意，就是首尾相连的一个链表。

对于单链表来说，最后一个结点的指针不为nullptr，而是头指针，即存放头节点的地址。

对于双链表来说，头节点的prior指针指向最后一个结点，最后一个结点指针指向头节点。

我们分别对单链表和双链表进行讨论

（1）创建

单循环链表，初始时，头节点的指针存放头指针，即指向头节点自己。

template
LinkList::LinkList()
{
    head=new node(0,head);
}

同理，双循环链表的两个指针都存放头指针，指向自己。 

template
LinkList::LinkList()
{
    head=new node(0,head,head);
}

（2）移动函数

移动函数判断超出范围的条件改为p==head。

template
typename DLinkList::node* DLinkList::moveTo(int i)
{
	if (i < -1)
		return nullptr;
	node* p = head;
	for (int u = 0; u < i + 1; u++)
	{
		p = p->next;
		if (p==head)//防止越界
			return nullptr;
	}
	return p;
}

（3）插入

单循环链表的插入和单链表操作基本相同。

双循环链表的插入和双循环链表有些区别。

下面第二个if语句可以去掉，因为双循环链表里没有一个结点是nullptr。

template
bool DLinkList::insert(int i, const T& val)
{
	node* pre = moveTo(i - 1);
	if (!pre)
		return false;
	//这句话运行后其实对双链表没什么影响，但可以想象如果没有下面一句，再下面的两句话颠倒就会出错
	node* p = new node(val,pre,pre->next);
	//if (pre->next)//确保pre->next不为nullptr，这里是与单链表不同的地方
	pre->next->prior = p;
	pre->next = p;
	return false;
}

（4）删除

单循环链表的删除和单链表操作基本相同。

双循环链表的删除和双循环链表有些区别。

最后一个if语句可以去掉，因为双循环链表里没有一个结点是nullptr。

template
bool DLinkList::remove(int i)
{
	node* pre = moveTo(i - 1);
	if (!pre)
		return false;
	//其实传入length上面是不会出错的，但我们不能删除length下标的元素
	node* p = pre->next;
	if (!p)//防止出界
		return false;
	pre->next = p->next;
	//if(pre->next)
	pre->next->prior = pre;
	delete p;
}