双向循环链表的时间复杂度除了查找，都为O(1)。
首先创建出结构体
typedef struct ListNode { struct ListNode *next; struct ListNode *prev; LTDataType data; } ListNode;
LTDataType其实是int类型的别名，方便后期代码维护
typedef int LTDataType;
双向链表的内容:
1：初始化
2：销毁链表
3：头插
4：尾插
5：头删
6：尾删
7：查找
初始化
首先要写一个创建新节点的函数，将第一个节点设置为头节点
ListNode *CreNode(LTDataType x) { ListNode *newnode = (ListNode *)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
然后将节点的prev和next指向自己，形成循环，循环链表相比于单向链表的好处在于可以更加容易找到尾节点，增删改的时间复杂度小于单项链表。
ListNode* ListInit() { ListNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }
这里也可以使用void ListInit(ListNode** phead)二级指针来进行初始化
头插
void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = BuyListNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; }
头删
void ListPopFront(ListNode* phead) { assert(phead->next != phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; }
尾删
void ListPopBack(ListNode* phead) { assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; }
尾插
void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
全部代码
#include <stdio.h> #include <stdlib.h> #include <assert.h> //定义数据类型 typedef int LTDataType; //创建链表结构体 typedef struct ListNode { struct ListNode *next; struct ListNode *prev; LTDataType data; } ListNode; //创建新节点 ListNode *CreNode(LTDataType x) { ListNode *newnode = (ListNode *)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode *ListInit() { //初始化节点，全指向自己 ListNode *phead = CreNode(0); phead->next = phead; phead->prev = phead; return phead; } //头插 void ListPushFront(ListNode *phead, LTDataType x) { assert(phead); ListNode *newnode = CreNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; } //尾插 void ListPushBack(ListNode *phead, LTDataType x) { //创建新节点 ListNode *newnode = CreNode(x); ListNode *cur = phead->prev; cur->next = newnode; newnode->prev = cur; phead->prev = newnode; newnode->next = phead; } //打印 void print(ListNode *phead) { ListNode *cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //头删 void ListPopFront(ListNode *phead) { assert(phead->next != phead); ListNode *first = phead->next; ListNode *second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; } //尾删 void ListPopBack(ListNode *phead) { ListNode *cur = phead->prev; ListNode *last = cur->prev; last->next = phead; phead->prev = last; free(cur); cur = NULL; } ListNode *ListFind(ListNode *phead, LTDataType x) { ListNode *cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // pos位置之前插入x void ListInsert(ListNode *pos, LTDataType x) { ListNode *cur = pos->prev; ListNode *newnode = CreNode(x); cur->next = newnode; newnode->prev = cur; newnode->next = pos; pos->prev = newnode; } //删除pos位置的值 void ListErase(ListNode *pos) { ListNode *prev = pos->prev; ListNode *next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; } //计算链表长度 void ListSize(ListNode *phead) { ListNode *tail = phead->next; int cnt = 0; while (tail != phead) { cnt++; tail = tail->next; } printf("链表的长度为:%d", cnt); } int main(void) { ListNode *phead = ListInit(); //初始化，创建链表头节点 ListPushFront(phead, 1); ListPushFront(phead, 2); ListPushFront(phead, 3); print(phead); ListPushBack(phead, 4); ListPushBack(phead, 5); ListPushBack(phead, 6); print(phead); ListPopFront(phead); print(phead); ListPopBack(phead); print(phead); ListNode *pos = ListFind(phead, 5); ListInsert(pos, 30); print(phead); ListErase(pos); print(phead); ListSize(phead); return 0; }
