“花自飘零水自流，一种相思,两处闲愁。”
“此情无计可消除，才下眉头，却上心头”
目录
前言
在实际生活中最常用的就是这两种链表。无头单向非循环链表。和带头双向循环链表。
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
1. 创建结构体
注意：typedef起作用是在第7行哦。所以第5,6还需要写struct ListNode类型。
typedef int LNDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LNDataType val; }LN;
2.malloc新节点
注意：需判断新开辟的节点是否为空。
//申请一个新节点 LN* BuynewNode(LNDataType x) { LN* newNode = (LN*)malloc(sizeof(LN)); if (newNode == NULL) { printf("malloc fail"); exit(-1); } newNode->next = NULL; newNode->prev = NULL; newNode->val = x; return newNode; }
3.创建哨兵位节点
注意：这里因为需要改变plist指针的内容，也就是改变plist指针的指向，所以需要传递plist的地址。
一句话就是：需要改变谁的内容，就传谁的地址。
这里有一点非常巧非常妙，就是phead的后继和前驱都是指向自己（phead），这里是模仿C++STL库里的哨兵位节点。
只能佩服想出来这些东西的大神。这样设计哨兵位节点的话，后续尾插，尾删，都特别的巧妙。
test.c
LN* plist = NULL; ListNodeInit(&plist);
List.h
//初始化节点 void ListNodeInit(LN** pphead) { LN* newNode = BuynewNode(0); *pphead = newNode; (*pphead)->next = *pphead; (*pphead)->prev = *pphead; }
4.尾插
注意：需要断言的原因是因为，即使链表没有一个节点，那链表至少还有个头，所以phead肯定不为空。
这里没有传地址的原因是因为，你不需要改变plist的指向，你改变的是plist指向的结构体里面的值。
多个节点尾插的情况如图。
一个节点的尾插。
//尾插 void ListNodePushBack(LN* phead, LNDataType x) { assert(phead); LN* newNode = BuynewNode(x); LN* tail = phead->prev; tail->next = newNode; newNode->prev = tail; newNode->next = phead; phead->prev = newNode; }
5.打印
注意：因为带个头，所以cur从第二个位置开始。
//打印 void ListNodePrint(LN* phead) { LN* cur = phead->next; while (cur != phead) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
6.尾删
注意不能删掉头结点，free掉头结点的话会造成野指针，再次访问时会造成非法访问。
所以要用assert断言不为首节点。
//尾删 void ListNodePopBack(LN* phead) { assert(phead); assert(phead->next != phead); LN* tail = phead->prev; LN* tailPrev = tail->prev; free(tail); tail = NULL; phead->prev = tailPrev; tailPrev->next = phead; }
7.头插
最好用next记录下一个节点。这样方便，思路清晰
//头插 void ListNodePushFront(LN* phead, LNDataType x) { assert(phead); LN* newNode = BuynewNode(x); LN* next = phead->next; phead->next = newNode; newNode->prev = phead; newNode->next = next; next->prev = newNode; }
8.在指定位置pos的前面进行插入
一般情况
只有一个节点时。
两种情况都适用以下代码。
//指定位置前插入，极限是头插 void ListNodeInsert(LN* pos, LNDataType x) { if (pos == NULL) { printf("没有找到这个数\n"); return; } LN* newNode = BuynewNode(x); LN* tailPrev = pos->prev; tailPrev->next = newNode; newNode->prev = tailPrev; newNode->next = pos; pos->prev = newNode; }
9. 删除指定位置pos节点
正常情况
极限尾删
两种情况都适用以下代码。
//指定位置删除 void ListNodeErease(LN* phead, LN* pos) { if (pos == phead || pos == NULL) { printf("pos指向头，或为空\n"); return; } LN* posPrev = pos->prev; LN* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos = NULL; }
10.销毁链表
注意：这里相当于malloc用完之后的free。否则会造成内存泄漏。
cur可以置空，但用处不大，因为cur是形参，形参是实参的一份临时拷贝，形参置空并不能改变实参。外部的实参还是依旧能非法访问到cur所指向的空间。
//链表销毁 void ListNodeDestroy(LN* phead) { assert(phead); LN* cur = phead->next; LN* next = cur->next; while (cur != phead) { next = cur->next; free(cur); cur = NULL; cur = next; } free(phead); phead = NULL; }
