C语言实现带头双向循环链表的接口
C语言实现带头双向循环链表的接口
链表是一种常见的数据结构，是用于存储数据元素的一种线性结构。链表的特点是可以动态地添加和删除元素，相比于数组，链表的优势在于插入和删除元素的时间复杂度是O(1)，而数组的时间复杂度是O(n)。其中，循环链表是一种特殊的链表形式，其特点是链表的最后一个节点连接了 个节点，形成了一个环。而带头双向循环链表则是在链表头部增加了一个哨兵节点，同时每个节点都存储了前驱和后继节点的地址，因此可以很方便地实现双向遍历的功能。
下面是C语言实现带头双向循环链表的接口：
1.链表节点定义
typedef struct ListNode
{
int data; //节点数据
struct ListNode* prev; //前驱节点指针
struct ListNode* next; //后继节点指针
}ListNode, * PListNode;
2.初始化链表
void InitList(PListNode* pHead)
{
*pHead = (PListNode)malloc(sizeof(ListNode)); //创建头节点
(*pHead)->prev = (*pHead)->next = *pHead; //初始化头节点的前驱和后继节点
}
3.判断链表是否为空
int ListEmpty(PListNode pHead)
{
return pHead->next == pHead;
}
4.获取链表长度
int ListLength(PListNode pHead)
{
int len = 0;
PListNode pNode = pHead->next;
while (pNode != pHead)
{
len++;
pNode = pNode->next;
}
return len;
}
5.获取链表指定位置的节点
PListNode GetNode(PListNode pHead, int index)
{
PListNode pNode = pHead->next;
int i = 0;
while (pNode != pHead && i < index)
{
pNode = pNode->next;
i++;
}
return pNode;
}
6.获取链表指定节点的数据
int GetData(PListNode pNode)
{
return pNode->data;
}
7.在链表指定位置插入节点
void InsertNode(PListNode pHead, int index, int data)
{
PListNode pNode = GetNode(pHead, index - 1);
PListNode pNewNode = (PListNode)malloc(sizeof(ListNode));
pNewNode->data = data;
pNewNode->prev = pNode;
pNewNode->next = pNode->next;
pNode->next->prev = pNewNode;
pNode->next = pNewNode;
}
8.删除链表指定位置的节点
void DeleteNode(PListNode pHead, int index)
{
PListNode pNode = GetNode(pHead, index - 1);
PListNode pDeleteNode = pNode->next;
pNode->next = pDeleteNode->next;
pDeleteNode->next->prev = pNode;
free(pDeleteNode);
}
9.清空链表
void ClearList(PListNode pHead)
{
PListNode pNode = pHead->next;
PListNode pNext = NULL;
while (pNode != pHead)
{
pNext = pNode->next;
free(pNode);
pNode = pNext;
}
pHead->prev = pHead->next = pHead;
}
10.销毁链表
void DestroyList(PListNode* pHead)
{
ClearList(*pHead);
free(*pHead);
*pHead = NULL;
}
总结
带头双向循环链表在实际开发中应用广泛，尤其是在需要频繁进行前后节点遍历的情况下会有很好的性能表现。但是需要注意的是，在编写代码时尽量简洁明了，减少节点指针的引用次数和内存的申请和释放，避免内存泄漏和指针无法释放的问题。