0、前要

如果您是初步认识链表，或是不能完全“手撕”一个简单的单链表，可以看看我的上一篇有关“无头单向非循环链表”的实现，再来看这一篇文章

1、“有头双向有循环链表”的实现

（0）首先阐述两个节点的区别

头节点： 是一个实际节点，实际存储数据的结构体， 它用于标识链表的起始位置， 头结点通常不存储有效数据，可以作为链表初始状态时的默认前驱节点

哨兵节点： 是一个辅助节点，它不存储任何有效数据， 仅仅是作为“哨兵”站在链表的某个位置上， 没有任何的业务信息，仅仅只是为了方便对链表的操作而引入的辅助节点。 哨兵节点可以用来简化链表操作的实现，进而提高代码效率。 哨兵节点通常不计入链表节点数量，也就是说，它本身并不属于链表的一部分

（1）“带头有循环双向链表”结构体

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;

（2）申请节点空间

ListNode* BuyListNode(LTDataType x)
{ListNode* cache = (ListNode*)malloc(sizeof(ListNode));//申请一个节点的空间if (!cache){perror("malloc fail!");return NULL;}cache->data = x;cache->next = NULL;cache->prev = NULL;return cache;
}

（3）初始化链表（创建一个“链表的头节点”）

ListNode* ListInit(void)
{ListNode* cache = BuyListNode(0);if (!cache) exit(-1);cache->next = cache;cache->prev = cache;return cache;
}

（4）链表销毁

void ListDestory(ListNode* plist)
{//1.防止空指针解引用assert(plist);ListNode* cur = plist->next;//循环变量//2.先释放掉循环的链表while (cur != plist){ListNode* next = cur->next;free(cur);cur = next;}//3.再释放掉头节点free(plist);plist = NULL;
}

（5）链表打印

void ListPrint(ListNode* plist)
{assert(plist);ListNode* cur = plist->next;//得到起始结点，而非头节点while (cur != plist){printf("[%d]<->", cur->data);cur = cur->next;}printf("[循环到头结点]\\n");
}

（6）链表尾插

void ListPushBack(ListNode* plist, LTDataType x)
{assert(plist);ListNode* cache = BuyListNode(x);//申请节点空间if (!cache) exit(-1);plist->prev->next = cache;//找到指向尾节点的指针cache->prev = plist->prev;cache->next = plist;plist->prev = cache;
}

（7）链表尾删

void ListPopBack(ListNode* plist)
{assert(plist);//保证不会发生空指针解引用assert(plist->next != plist);//保证链表不会只剩下头节点//1.先找到这个尾节点，单独隔离出来这个地址ListNode* tail = plist->prev;//2.更新链表的新尾节点tail->prev->next = plist;plist->prev = tail->prev;//3.释放被隔离的旧尾节点free(tail);tail = NULL;
}

（8）链表头插

void ListPushFront(ListNode* plist, LTDataType x)
{assert(plist);ListNode* cache = BuyListNode(x);//申请节点空间if (!cache) exit(-1);ListNode* p = plist->next;plist->next = cache;cache->next = p;cache->prev = plist;p->prev = cache;
}

（9）链表头删

void ListPopFront(ListNode* plist)
{assert(plist);//保证不会发生空指针解引用assert(plist->next != plist);//保证链表不会只剩下头节点ListNode* first = plist->next;//先找到这个首节点，单独隔离出来plist->next = first->next;first->prev = plist;free(first);first = NULL;
}

（10）链表查找（返回找到的数据对应结构体的地址）

ListNode* ListFind(ListNode* plist, LTDataType x)
{assert(plist);//避免解引用空指针assert(plist->next != plist);//避免查找空链表ListNode* cur = plist->next;//找到第一个节点while (cur != plist){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

（11）链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);//避免解引用空指针ListNode* cache = BuyListNode(x);//购买新节点ListNode* p = pos->prev;pos->prev = cache;cache->next = pos;cache->prev = p;p->next = cache;
}

（12）链表删除pos位置的结点

void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}

（13）测试用例

void test()
{ListNode* pl = ListInit();//创建一个头节点//根据这个头结点进行“增删查改”ListPushBack(pl, 1);//尾插ListPushBack(pl, 2);//尾插ListPushBack(pl, 3);//尾插ListPushBack(pl, 4);//尾插ListPrint(pl);//打印链表ListPopBack(pl);//尾删ListPopBack(pl);//尾删ListPrint(pl);//打印链表ListPopBack(pl);//尾删ListPrint(pl);//打印链表ListPopBack(pl);//尾删ListPrint(pl);//打印链表//ListPopFront(pl);//尾删（非法）//ListPrint(pl);//打印链表ListPushBack(pl, 1);//尾插ListPushBack(pl, 2);//尾插ListPushBack(pl, 3);//尾插ListPushBack(pl, 4);//尾插ListPopBack(pl);//尾删ListPrint(pl);//打印链表printf("%p\\n", ListFind(pl, 1));//查找数据为1的节点，并且打印地址printf("%d\\n", ListFind(pl, 1)->data);//查找数据为1的节点，并且打印出指针指向的数据printf("%p\\n", ListFind(pl, 2));//查找数据为2的节点，并且打印地址printf("%d\\n", ListFind(pl, 2)->data);//查找数据为2的节点，并且打印出指针指向的数据printf("%p\\n", ListFind(pl, 3));//查找数据为3的节点，并且打印地址printf("%d\\n", ListFind(pl, 3)->data);//查找数据为3的节点，并且打印出指针指向的数据printf("%p\\n", ListFind(pl, 0));//查找数据为1的节点，并且打印地址ListPushFront(pl, 0);//头插ListPushFront(pl, -1);//头插ListPushFront(pl, -2);//头插ListPopBack(pl);//尾删ListPopBack(pl);//尾删ListPopBack(pl);//尾删ListPrint(pl);//打印链表ListPopBack(pl);//尾删ListPopBack(pl);//尾删ListPopBack(pl);//尾删ListPushFront(pl, -2);//头插ListPrint(pl);//打印链表ListPopBack(pl);//尾删ListPushFront(pl, 10);//头插ListPushFront(pl, 100);//头插ListPushFront(pl, 1000);//头插ListPrint(pl);//打印链表ListPopFront(pl);//头删ListPopFront(pl);//头删ListPopFront(pl);//头删ListPrint(pl);//打印链表//ListPopFront(pl);//头删（非法）//ListPrint(pl);//打印链表ListPushFront(pl, 10);//头插ListPushFront(pl, 100);//头插ListPushFront(pl, 1000);//头插ListPrint(pl);//打印链表ListInsert(ListFind(pl, 10), -1);//任意插入ListInsert(ListFind(pl, 100), -1);//任意插入ListInsert(ListFind(pl, 1000), -1);//任意插入ListPrint(pl);//打印链表//ListInsert(ListFind(pl, 1), -1);//任意插入（非法）//ListPrint(pl);//打印链表ListPopFront(pl);//头删ListPopFront(pl);//头删ListPopFront(pl);//头删ListPopFront(pl);//头删ListPopFront(pl);//头删ListPopFront(pl);//头删ListPushFront(pl, 10);//头插ListPrint(pl);//打印链表ListInsert(ListFind(pl, 10), -1);//任意插入ListPrint(pl);//打印链表ListPopFront(pl);//头删ListPopFront(pl);//头删ListPrint(pl);//打印链表ListPushFront(pl, 10);//头插ListPushFront(pl, 100);//头插ListPushFront(pl, 1000);//头插ListPrint(pl);//打印链表ListErase(ListFind(pl, 10));//任意删除ListPrint(pl);//打印链表ListErase(ListFind(pl, 100));//任意删除ListPrint(pl);//打印链表ListErase(ListFind(pl, 1000));//任意删除ListPrint(pl);//打印链表//ListErase(ListFind(pl, 1000));//任意删除（非法）//ListPrint(pl);//打印链表ListDestory(pl);//销毁链表
}

2、其他类型的链表

在我的博文中我写了有关链表的两种结构，一种是结构最简单的“无头单向非循环链表”，另外一种是结构最复杂的“有头双向有循环链表”。在以后我还会写其他类型的链表，但是您会发现，只要掌握了”最简单“和”最复杂“的，那么其他类型的链表也都是类似的写法