手搓带头双向循环链表（C语言）

本文主要是介绍手搓带头双向循环链表（C语言），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

List.h

List.c

ListTest.c

测试示例

带头双向循环链表优劣分析

List.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDataType data;
}ListNode;//创建节点
ListNode* BuyListNode(LTDataType x);
//初始化
ListNode* ListInit();
//打印链表
void ListPrint(ListNode* phead);
//尾插
void ListPushBack(ListNode* phead, LTDataType x);
//尾删
void ListPopBack(ListNode* phead);
//销毁
void ListDistroy(ListNode* phead);
//头插
void ListPushFront(ListNode* phead, LTDataType x);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, LTDataType x);
//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x);
//删除pos位置的值
void ListErase(ListNode* pos);

List.c

#include "List.h"//创建节点
ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));//申请空间失败if (node == NULL){perror("BuyListNode");exit(-1);}node->data = x;node->prev = NULL;node->next = NULL;return node;
}//初始化
ListNode* ListInit()
{ListNode* phead = BuyListNode(-1);phead->prev = phead;phead->next = phead;return phead;
}//打印链表
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}//尾插
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;
}//尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->prev != phead);ListNode* tailPrev = phead->prev->prev;free(phead->prev);tailPrev->next = phead;phead->prev = tailPrev;
}//销毁
void ListDistroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;ListNode* tmp = cur;while (cur != phead){cur = cur->next;free(tmp);tmp = cur;}phead->prev = phead;phead->next = phead;
}//头插
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);newnode->next = first;first->prev = newnode;newnode->prev = phead;phead->next = newnode;
}//头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* first = phead->next;ListNode* second = first->next;free(first);second->prev = phead;phead->next = second;
}//查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

头插尾插复用：

//在pos位置之前插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}//头插
void ListPushFront(ListNode* phead, LTDataType x)
{ListInsert(phead->next, x);
}//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{ListInsert(phead, x);
}

头删尾删复用：

//删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}//头删
void ListPopFront(ListNode* phead)
{assert(phead->next != phead);ListErase(phead->next);
}//尾删
void ListPopBack(ListNode* phead)
{assert(phead->prev != phead);ListErase(phead->prev);}

ListTest.c

#include "List.h"void test1()
{ListNode* phead = NULL;//初始化phead = ListInit();ListPrint(phead);//测试尾插ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPushBack(phead, 5);ListPrint(phead);//测试尾删ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);ListPrint(phead);/*ListPopBack(phead);ListPrint(phead);*/ListDistroy(phead);
}void test2()
{ListNode* phead = NULL;//初始化phead = ListInit();ListPrint(phead);//测试头插ListPushFront(phead, 1);ListPushFront(phead, 2);ListPushFront(phead, 3);ListPushFront(phead, 4);ListPushFront(phead, 5);ListPrint(phead);//测试头删ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);ListPrint(phead);/*ListPopFront(phead);ListPrint(phead);*/ListDistroy(phead);
}
void test3()
{ListNode* phead = NULL;//初始化phead = ListInit();ListPrint(phead);//测试在pos位置之前插入ListInsert(phead, 1);ListInsert(phead, 2);ListInsert(phead, 3);ListInsert(phead, 4);ListInsert(phead, 5);ListPrint(phead);ListInsert(phead->next, 6);ListInsert(phead->next, 7);ListInsert(phead->next, 8);ListInsert(phead->next, 9);ListInsert(phead->next, 10);ListPrint(phead);//测试删除pos位置的值ListNode* pos = ListFind(phead, 1);ListErase(pos);ListPrint(phead);pos = ListFind(phead, 5);ListErase(pos);ListPrint(phead);pos = ListFind(phead, 10);ListErase(pos);ListPrint(phead);ListDistroy(phead);
}
int main()
{//测试尾插尾删//test1();//测试头插头删//test2();//测试在pos位置插入删除test3();return 0;
}

测试示例

尾插尾删：

头插头删：

在pos位置插入删除:

带头双向循环链表优劣分析

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低