1、防止单链表是空的而设的.当链表为空的时候,带头结点的头指针就指向头结点.如果当链表为空的时候,头结点的指针域的数值为NULL.

2、是为了方便单链表的特殊操作,插入在表头或者删除第一个结点.这样就保持了单链表操作的统一性!

3、单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会??。

循环链表的优点

1.循环链表中没有NULL指针；

2.循环链表无须增加存储量。循环链表中没有NULL指针优点在于仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针。

双向链表

双向链表的概念

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

双向循环链表：双向循环链表将双向链表的头结点和尾结点链接起来也能构成循环链表，其称为双向循环链表

typedef int SLTDaTaType;//更方便以后我们更换需要的数据类型

typedef struct ListNode
{

	SLTDaTaType data;
	struct SListNode* next;//指向下一个结构体的地址
	struct SListNode* prev;
}ListNode;

?双向循环链表的初始化

初始化双向循环链表，创建一个节点，不储存数据，方便判断链表的一次遍历结束，

ListNode* BuyListNode1()
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	return node;
}

ListNode* ListInit()
{
	ListNode* phead = BuyListNode1();
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

双向循环链表的插入

void ListpushBack(ListNode* phead, SLTDaTaType x)
{
	assert(phead);

	ListNode* tail = phead->prev;//先把phead指向的前一个指针保存下来
	ListNode* newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->next = phead;
	newnode->prev = tail;
	phead->prev = newnode;
}

void ListpushFront(ListNode* phead, SLTDaTaType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
}

双向循环链表的删除

void ListpopFront(ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	ListNode* pop = phead->next;
	phead->next = pop->next;
	free(pop);	
}
void ListpopBack(ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	ListNode* pop = phead->prev;
	ListNode* popp = pop->prev;
	popp->next = phead;
	phead->prev = popp;
	free(pop);
}

双向循环链表的查找

ListNode* ListFind(ListNode* phead, SLTDaTaType x)
{
	ListNode* cur = phead->next;
	while (cur!=phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
		return NULL;
}

双向循环链表的修改

//指定位置插入
void ListInsret(ListNode* p, SLTDaTaType x)
{
	ListNode* sert = BuyListNode(x);
	ListNode *pprev = p->prev;
	sert->next = p;
	sert->prev = p->prev;
	p->prev = sert;
	pprev->next = sert;
}
//删除当前位置
void ListEarse(ListNode* p)
{
	assert(p);
	ListNode* pprev = p->prev;
	ListNode* pnext = p->next;
	
	pprev->next = pnext;
	pnext->prev = pprev;
	free(p);
}

双向循环链表的打印

void Listprint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

双向循环链表的销毁

void ListDestory(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur!=phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

}

?运行结果比对

#include "List.h"

void test()
{
	ListNode* plist = ListInit();
	ListpushBack(plist, 1);
	ListpushBack(plist, 2);
	ListpushBack(plist, 3);
	ListpushBack(plist, 4);
	ListpushBack(plist, 5);
	ListpushFront(plist, 0);
	ListpushFront(plist, -1);

	Listprint(plist);

	ListpopBack(plist);
	ListpopFront(plist);

	Listprint(plist);

	ListNode*p=ListFind(plist, 3);
	if (p)
	{
		ListInsret(p, 20);
	}
	Listprint(plist);

	ListEarse(p);
	Listprint(plist);

	printf("%d\n", ListSize(plist));


	ListDestory(plist);
	plist = NULL;


}
int main()
{
	test();

	return 0;
}