一、基本认知

什么是循环

链表的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。

什么是双链表

链表的结构体中存储了两个指针，一个指向前驱节点，另一个指向后继节点。

基本结构

如图所示，data是存储的数字，prev，next分别指向前驱节点和后继节点。

二、 实现

1，初始化

初始化就是创建一个头结点，并且返回该头结点。
由于是双链表，初始化就是创建这个头结点，就算只有一个头结点也要遵守规则，自己指向自己。这里我花了一个图方便大家理解。

只有一个头结点的情况
下面直接上代码！

LTNode* SLTInit()
 6	{
 7		LTNode* phead= (LTNode*)malloc(sizeof(LTNode));
 8		phead->next = phead;
 9		phead->prev = phead;
 10		return phead;
 11	}
 12	

2，头插法

首先创建一个新结点存储数据，这里调用「创建结点」函数，「创建结点」函数我放在最后面面了，不会的同学下去看。

这里把1头插到链表最前面。

void LTPushFront(LTNode* phead, LTDataType x)
 51	{
 52		assert(phead != NULL);
 53		LTNode* newnode = BuyLTNode(x);
 54		LTNode* next = phead->next;
 55	
 56	
 57	
 58		phead->next = newnode;
 59		newnode->next = next;
 60		newnode->prev = phead;
 61		next->prev = newnode;
 62	
 63	}
 64	

3，尾插法

void LTPhshBack(LTNode* phead, LTDataType x)
 21	{
 22		assert(phead != NULL);
 23		LTNode* newnode=BuyLTNode(x);
 24		LTNode* tail = phead->prev;
 25		
 26	
 27		tail->next = newnode;
 28		newnode->prev = tail;
 29	
 30		newnode->next = phead;
 31		phead->prev = newnode;
 32	
 33	}
 34	

4，头删法

void LTPopFront(LTNode* phead)
 81	{
 82		assert(phead != NULL);
 83		assert(phead->next != NULL);
 84	
 85		LTNode* next = phead->next;
 86		LTNode* nextNext= next->next;
 87		phead->next = nextNext;
 88		nextNext->prev = phead;
 89		free(next);
 90		next = NULL;
 91	
 92	}
 93	

4，尾删法

void LTPopBack(LTNode* phead) 
 66	{
 67		assert(phead != NULL);
 68		//不能删除哨兵位
 69		assert(phead->next != phead);
 70		LTNode* tail = phead->prev;
 71		LTNode* cur = tail->prev;
 72		cur->next = phead;
 73		phead->prev = cur;
 74		
 75		tail = NULL;
 76		free(tail);
 77	}
 78	

5，查找函数

LTNode* LTFind(LTNode* phead, LTDataType x)
 96	{
 97		assert(phead != NULL);
 98		LTNode* cur = phead->next;
 99		while (cur!=phead)
 100		{
 101			if (cur->data == x)
 102			{
 103				return cur;
 104			}
 105			cur = cur->next;
 106		}
 107		return NULL;
 108	}
 109	
 110	

6，在某位置插入一个数字

这个函数可以复用到头插法，尾插法。

void LTInsert(LTNode* pos, LTDataType x)
 113	{
 114		assert(pos != NULL);
 115		LTNode* newnode = BuyLTNode(x);
 116		LTNode* posPrev = pos->prev;
 117	
 118		posPrev->next = newnode;
 119		newnode->prev = posPrev;
 120	
 121		newnode->next = pos;
 122		pos->prev = newnode;
 123	
 124	}
 125	

7，删除某位置的数字

这个函数可以复用到头删法，尾删法。

void LTErease(LTNode* pos)
 127	{
 128		assert(pos != NULL);
 129		LTNode* posPrev = pos->prev;
 130		LTNode* posNext = pos->next;
 131	
 132		posPrev->next = posNext;
 133		posNext->prev = posPrev;
 134		free(pos);
 135		pos = NULL;
 136	
 137	

8，创建结点

LTNode* BuyLTNode(LTDataType x)
 13	{
 14		LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
 15		newnode->data = x;
 16	}
 17	

 

总结

插入或者删除的时候一定要记得断言，否则可能会出现错误，但是找不到哪里出错。
双链表是在顺序表的基础上更新的一种存储结构，他的优点是：在任意位置插入效率高，并且按需申请空间，不会造成空间浪费。