目录

一、List.h

二、List.c

三、test.c

一、List.h

#pragma once#include // 带头双向循环链表
typedef int DataType;typedef struct ListNode
{DataType data;struct ListNode* prev;struct ListNode* next;
}ListNode, *LinkList;// 基本操作
ListNode* BuyLinkListNode(DataType e);  // 动态申请一个新节点// void LinkListInit(LinkList* pphead);  // 初始化（方法一）
ListNode* LinkListInit();  // 初始化（方法二）void LinkListPushBack(LinkList phead, DataType e);  // 尾插
void LinkListPopBack(LinkList phead);  // 尾删void LinkListPushFront(LinkList phead, DataType e);  // 头插
void LinkListPopFront(LinkList phead);  // 头删void LinkListInsert(ListNode* pos, DataType e);  // 在 pos 前面插入
void LinkListErase(ListNode* pos);  // 删除 pos 节点ListNode* LinkListFind(LinkList phead, DataType e);  // 查找void LinkListPrint(LinkList phead);  // 打印void LinkListDestroy(LinkList phead);  // 销毁

二、List.c

1. 动态申请一个新节点：

   ListNode* BuyLinkListNode(DataType e)
   {ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (NULL == newnode){perror("malloc failed!");exit(-1);}newnode->data = e;newnode->prev = NULL;newnode->next = NULL;return newnode;
   }

2. 初始化：

   法一：

   void LinkListInit(LinkList* pphead)
   {assert(pphead); ListNode* newnode = BuyLinkListNode(0);  // 生成一个新结点作为头结点newnode->prev = newnode;newnode->next = newnode;*pphead = newnode;  // 将头指针指向头结点
   }

   法一通过传址（头指针的地址）的方式在函数内部将头指针指向头结点。

   法二：

   ListNode* LinkListInit()
   {ListNode* newnode = BuyLinkListNode(0);  // 生成一个新结点作为头结点newnode->prev = newnode;newnode->next = newnode;return newnode;  // 返回头结点
   }

   法二则需要在函数调用结束后，在外部主动地将头指针指向头结点，即 LinkList phead = LinkListInit()。

3. 尾插：

   void LinkListPushBack(LinkList phead, DataType e)
   {assert(phead);ListNode* newnode = BuyLinkListNode(e);ListNode* tail = phead->prev;// 尾插phead->prev = newnode;newnode->next = phead;tail->next = newnode;newnode->prev = tail;
   }

4. 尾删：

   void LinkListPopBack(LinkList phead)
   {assert(phead);// 判断是否为空表if (phead->prev == phead){return;}// 尾删ListNode* tail = phead->prev;phead->prev = tail->prev;tail->prev->next = phead;free(tail);
   }

5. 头插：

   void LinkListPushFront(LinkList phead, DataType e)
   {assert(phead);ListNode* newnode = BuyLinkListNode(e);ListNode* first = phead->next;// 头插phead->next = newnode;newnode->prev = phead;first->prev = newnode;newnode->next = first;
   }

6. 头删：

   void LinkListPopFront(LinkList phead)
   {assert(phead);// 判断是否为空表if (phead->next == phead){return NULL;}// 头删ListNode* first = phead->next;phead->next = first->next;first->next->prev = phead;free(first);
   }

7. 在 pos 之前插入：

   void LinkListInsert(ListNode* pos, DataType e)
   {assert(pos);ListNode* newnode = BuyLinkListNode(e);ListNode* pre = pos->prev;// 在 pos 之前插入pre->next = newnode;newnode->prev = pre;pos->prev = newnode;newnode->next = pos;
   }

8. 删除 pos 节点：

   void LinkListErase(ListNode* pos)
   {assert(pos);// 删除 pos 节点pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
   }

9. 查找：

   ListNode* LinkListFind(LinkList phead, DataType e)
   {assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == e){return cur;}cur = cur->next;}return NULL;
   }

10. 打印：

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

11. 销毁：

    void LinkListDestroy(LinkList phead)
    {assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* tmp = cur;cur = cur->next;free(tmp);}free(phead);
    }

在 LinkListInsert 函数中，当 pos == phead 时，该函数就相当于尾插；当 pos == phead->next 时，该函数就相当于头插，因此可以分别对 LinkListPushBack 和 LinkListPushFront 函数做如下修改：

void LinkListPushBack(LinkList phead, DataType e)
{assert(phead);LinkListInsert(phead, e); 
}
​
void LinkListPushFront(LinkList phead, DataType e)
{assert(phead);LinkListInsert(phead->next, e);
}

在 LinkListErase 函数中，当 pos == phead->prev 时，该函数就相当于尾删；当 pos == phead->next 时，该函数就相当于头删，因此可以分别对 LinkListPopBack 和 LinkListPopFront 函数做如下修改：

void LinkListPopBack(LinkList phead)
{assert(phead);// 判断是否为空表if (phead->prev == phead){return;}// 尾删LinkListErase(phead->prev);
}
​
void LinkListPopFront(LinkList phead)
{assert(phead);// 判断是否为空表if (phead->next == phead){return NULL;}// 头删LinkListErase(phead->next);
}

三、test.c

#include "list.h"// 尾插和尾删
void test1()
{LinkList phead;  // 头指针// LinkListInit(&phead);  // 初始化（方法一）phead = LinkListInit();  // 初始化（写法二）// 尾插LinkListPushBack(phead, 1);LinkListPushBack(phead, 2);LinkListPushBack(phead, 3);LinkListPushBack(phead, 4); LinkListPrint(phead);  // <=>head<=><=>1<=><=>2<=><=>3<=><=>4<=>// 尾删LinkListPopBack(phead);LinkListPrint(phead);  // <=>head<=><=>1<=><=>2<=><=>3<=>LinkListPopBack(phead);LinkListPrint(phead);  // <=>head<=><=>1<=><=>2<=>LinkListPopBack(phead);LinkListPrint(phead);  // <=>head<=><=>1<=>LinkListPopBack(phead);LinkListPrint(phead);  // <=>head<=>// 销毁LinkListDestroy(phead);phead = NULL;
}// 头插和头删
void test2()
{LinkList phead = LinkListInit();  // 初始化// 头插LinkListPushFront(phead, 1);LinkListPushFront(phead, 2);LinkListPushFront(phead, 3);LinkListPushFront(phead, 4);LinkListPrint(phead);  // <=>head<=><=>4<=><=>3<=><=>2<=><=>1<=>// 头删LinkListPopFront(phead);LinkListPrint(phead);  // <=>head<=><=>3<=><=>2<=><=>1<=>LinkListPopFront(phead);LinkListPrint(phead);  // <=>head<=><=>2<=><=>1<=>LinkListPopFront(phead);LinkListPrint(phead);  // <=>head<=><=>1<=>LinkListPopFront(phead);LinkListPrint(phead);  // <=>head<=>// 销毁LinkListDestroy(phead);phead = NULL;
}int main()
{// test1();test2();return 0;
}