详解C语言如何实现双向带头循环链表-C/C++开发

目录一、双向循环链表与顺序表的区别二、List.h三、List.c1、带头双向循环链表的初始化2、带头双向循环链表的销毁3、带头双向循环链表的打印4、动态开辟一个节点5、带头双向循环链表的判空6、带头...

1、带头双向循环链表的初始化
2、带头双向循环链表的销毁
3、带头双向循环链表的打印
4、动态开辟一个节点
5、带头双向循环链表的判空
6、带头双向循环链表的尾插、尾删
7、带头双向循环链表的头插、头删
8、带头双向循环链表的长度
9、带头双向循环链表的查找、任意位置插入、删除

一、双向循环链表与顺序表的区别

不同点	顺序表	双向带头循环链表
在内存中的存储方式	连续存储	不一定连续
随机访问	支持随机访问	不支持随访问
任意元素插入或删除	尾插O(1)，其他O(N)，可能需要挪动元素	通过修改指针指向即可
应用场景	元素高效存储、频繁访问	任意位置插入删除频繁
三级缓存命中率	高	低

链表的打印

void PrintList(ListNode* phead)//打印
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d<=>", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

从头结点的next开始，遍历打印

4、动态开辟一个节点

ListNode* BuyNode(ListDateType x)//动态开辟一个节点
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("BuyNode:\n");
        exit(-1);
    }
    newnode->date = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

将值放入这个节点，并将两个指针置空

5、带头双向循环链表的判空

bool ListEmpty(ListNode* phead)//判断链表是否只有头节点
{
    assert(phead);
    return phead->next == phead;
}

只有哨兵位这一个头结点即为空

6、带头双向循环链表的尾插、尾删

void ListPushBack(ListNode* phead, ListDateType x)//尾插
{
    assert(phead);
    ListNode* tail = phead->prev;
    ListNode* newnode = BuyNode(x);
    newnode->next = phead;
    newnode->prev = tail;
    tail->next = newnode;
    phead->prev = newnode;
}
void ListPopback(ListNode* phead)//尾删
{
    assert(phead);
    assert(!ListEmpty(phead));
    ListNode* tail = phead->prev;
    ListNode* prev = tail->prev;
    free(tail);
    prev->next = phead;
    phead->prev = prev;
}

注意尾删前需要判空

7、带头双向循环链表的头插、头删

void ListPushFront(ListNode* phead, ListDateType x)//头插
{
    assert(phead);
    ListNode* cur = phead->next;
    ListNode* newnode = BuyNode(x);
    newnode->next = cur;
    newnode->prev = phead;
    cur->prev = newnode;
    phead->next = newnode;
}
void ListPopFront(ListNode* phead)//头删
{
    assert(phead);
    assert(!ListEmpty(phead));
    ListNode* cur = phead->next;
    ListNode* next = cur->next;
    free(cur);
    phead->next = next;
    next->prev = phead;
}

注意头删前需要判空

8、带头双向循环链表的长度

size_t ListSize(ListNode* phead)//有效节点个数
{
    assert(phead);
    ListNode* cur = phead->next;
    size_t count = 0;
    while (cur != phead)
    {
        cur = cur->next;
        ++count;
    }
    return count;
}

循环计数即可，哨兵位不算

9、带头双向循环链表的查找、任意位置插入、删除

ListNode* ListFind(ListNode* phead, ListDateType x)//查找（可用于修改）
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur!=phead)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
void ListInsert(ListNode* pos, ListDateType x)//pos位置之前插入
{
    assert(pos);
    ListNode* newnode = BuyNode(x);
    ListNode* prev = pos->prev;
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}
void ListErase(ListNode* pos)//删除pos位置
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    free(pos);
    prev->next = next;
    next->prev = prev;
}

查找：遍历链表，返回第一个date==x的节点指针，查找通常配合下面两个接口使用

任意位置插入、删除：使用pos位置进行插入删除操作。

头插、头删、尾插、尾删接口可以复用上面三个接口

到此这篇关于详解C语言如何实现双向带头循环链表的文章就介绍到这了,更多相关C语言双向带头循环链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！