荣成市信用建设官方网站新东方烹饪培训学校
1、链表种类大全
1、链表严格来说可能用2*2*2=8种结构，从是否带头，是否循环，是否双向三个角度区分。
2、无头单向循环链表一般不会在实际运用中直接存储数据，而会作为某些更复杂结构的一个子结构，毕竟它只在头插、头删时具有效率上的优势。
3、带哨兵卫的头有利于解决尾插时多种讨论的复杂情况。
双向有利于insert、erase的实现，这两个函数涉及到对pos位置结点的前一个结点的操作，而双向链表由于存放了prev指针，可以轻松找到前一个结点（不用为了找前一个结点而再次遍历），从而完成相关功能。
循环有利于直接通过phead->prev找到tail，不用遍历，提高尾部操作的效率。
2、接口函数
//打印
void LTPrint(LTNode* phead);
//初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPustFront(LTNode* phead,LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找链表中某个值的位置
LTNode* LTFind(LTNode* phead,LTDataType x);
//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);
//pos位置删除
void LTErase(LTNode* pos);结点的创建
typedef int LTDataType;typedef struct LTNode
{struct LTNode* prev;struct LTNode* next;LTDataType data;}LTNode;与之前相同，以int类型作为链表存储的数据类型。
3、初始化
在之前的无头单向非循环链表中，我们用一个plist指针指向链表，创建时只需要将plist置空即可，操作简单，不需要通过函数实现。
在顺序表的实现中，要考虑到sz（顺序表当前存储的数据个数），capacity（顺序表当前容量），还有一个指向顺序表的初始指针（避免使用数组导致的一些缺点），过程较复杂需要通过函数。
在带头双向循环链表中，由于需要创建一个哨兵卫的头结点，且为循环结构，next，prev都指向tail，无元素时tail为自己，可以通过init函数来实现。 
//初始化
LTNode* LTInit()
{//初始化时创建一个哨兵卫头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (NULL == phead){perror("malloc fail");return NULL;}phead->next = phead->prev = phead;phead->data = -1;return phead;}phead的data暂且设置一个-1，其它值也可以。
4、打印
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<head>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}phead一定不为NULL，因此可以assert(phead)防止使用者误传入NULL。
phead头结点不为实际值，因此从phead->next开始遍历，cur只要不为phead的都要进入循环完成打印。
5、尾部操作
1、创建新结点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (NULL == newnode){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode;}插入操作前，需要malloc一个新结点。为防止野指针，在创建过程中就将其next和prev置为空
2、判断链表是否为空
删除操作前，需要判断链表是否为空。
//判断链表原来是否为空的函数
bool IsEmpty(LTNode* phead)
{return phead->next == phead;
}这里采用bool值，返回值为true（非0），和false（0）两种，需要包含stdbool.h头文件，这里的phead->next如果等于phead，即链表中只有哨兵卫头结点，即为空，返回为1（非0），代表链表的状态为空
3、尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);if (NULL == newnode){perror("BuyLTNode fail");return;}//按照之前的思路，尾插需要先找尾// 这里phead的prev直接找尾 需要4步指针操作LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;phead->prev = newnode;newnode->next = phead;}先利用phead->prev找到原来的尾结点tail，然后创建新的尾结点，随后通过4步指针操作建立newnode与tail和phead的联系。（不用遍历找尾，提高了效率）
带哨兵卫的头结点的优势，不用讨论原链表为空的情况。
4、尾删
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//先判断原来是否为空assert(!IsEmpty(phead));LTNode* tail = phead->prev;LTNode* prev = tail->prev;free(tail);tail = NULL;phead->prev = prev;prev->next = phead; }assert内为！IsEmpty，即为空时报错。
分别用tail和prev标记要删除的尾结点以及前一个结点，free掉tail，利用两个指针建立prev与phead的联系，使其成为新尾。
多删除时assert报错
6、头部操作
1、头插
//头插
void LTPustFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);if (NULL == newnode){perror("BuyLTNode fail");return;}newnode->next = phead->next;phead->next->prev = newnode;newnode->prev = phead;phead->next = newnode;}通过4个指针建立newnode与phead、phead->next的联系，要注意顺序，先建立与phead->next
的，否则其会被改变无法找到。
当然，在开始时新建立一个next指针指向phead->next的结点也可以。
2、头删
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!IsEmpty(phead));LTNode* first = phead->next;phead->next = first->next;first->next->prev = phead;free(first);first = NULL;}先利用first标记要删除的头结点，然后用两个指针建立phead与first的next结点之间的关系，最后free掉first。
头部操作本身就是链表的优势，因此仍不需要遍历
7、查找及指定位置pos操作
1、查找函数
//查找链表中某个值的位置
LTNode* LTFind(LTNode* phead,LTDataType x)
{assert(phead);assert(!IsEmpty(phead));LTNode* pos = phead->next;while (pos != phead){if (pos->data == x){return pos;}pos = pos->next;}printf("没找到\n");exit(0);
}
从phead->next的位置开始遍历，找到了则用pos返回该结点的地址，使用者可以用一个ret指针在外部接收，找不到则终止程序。查找前先确认链表不为空。
通过调试观察到，ret拿到了值为3的结点的地址
还可以继续展开，观察带头双向循环链表的内部结构，是怎样完成循环的。
2、insert指定位置前插入
//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prevptr = pos->prev;prevptr->next = newnode;newnode->next = pos;newnode->prev = prevptr;pos->prev = newnode;}先用prevptr找到pos的前一个结点，然后利用4个指针建立newnode与这两个结点的关系，完成中间位置插入。
可以用pos->prev指针直接找到前一个结点，不需要查找外的额外遍历，提高了效率。
3、erase指定位置删除
//pos位置删除
void LTErase(LTNode* pos)
{assert(pos);//LTNode* prevpos = pos->prev;//LTNode* nextpos = pos->next;//prevpos->next = nextpos;//nextpos->prev = prevpos;//free(pos);//pos = NULL;pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}同样找到pos前一个位置的结点，连接pos前一个与后一个结点，然后free掉pos
4、优化头尾操作
只要有了insert和erase两个函数，就可以轻易完成头尾的4个操作函数，只需要复用上述两个即可
例如在pos前插入一个节点，实际效果为尾插。
insert(pos->next)效果为头插
erase(phead->next)为头删
erase(phead->prev)为尾删
8、链表的销毁
//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);printf("销毁成功\n");
}
从phead->next位置开始遍历销毁即可，最后使用者在外部对创建的链表手动置空
掌握了以上操作，20分钟写一个链表不是难事
目录
1、链表种类大全
2、接口函数
3、初始化
4、打印
5、尾部操作
1、创建新结点
2、判断链表是否为空
3、尾插
4、尾删
6、头部操作
1、头插
2、头删
7、查找及指定位置pos操作
1、查找函数
2、insert指定位置前插入
3、erase指定位置删除
4、优化头尾操作
8、链表的销毁