【数据结构】【链表】双向循环带头链表-增-删-查(C语言)

xuanxuan

2021-06-01

我的小站——半生瓜のblog——同步更新

单链表存在的缺陷：

不能从后往前走,

找不到他的前驱,

指定位置删除增加尾删都要找前一个，时间复杂度都是O(n)

针对上面的这些缺陷的解决方案——双向链表。

@TOC

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向、双向
带头、不带头——带哨兵位的头结点，这个结点不存储有效数据，好处是什么？尾插的判断更方便简单，带头就不需要二级指针了，（带头结点，不需要改变穿过来的指针，也就是意味着不需要传二级指针了。）
循环、非循环

无头单向非循环：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等，另外这种数据结构在笔试面试中出现很多。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头循环双向链表，另外，这个结构虽然复杂，但是使用代码代码实现的以后会发现结构带来许多优势，实现反而简单了。

带头双向循环链表

在这里插入图片描述

结构体创建

typedef int LSTNodeData;
typedef struct ListNode
{
    LSTNodeData data;
    struct ListNode* next;
    struct ListNode* prev;
}LSTNode;

创建结点

DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
    DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

初始化

有个小哨兵位的头结点，并且是一个循环状态。

DBLSTNode* DBLSTInit()
{
    //用一个返回值可以 替代二级指针
    DBLSTNode* phead = DBLSTCreat(0);
    //循环
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

销毁

void DBLSTDestory(DBLSTNode* phead)
{
    //找到第一个结点
    DBLSTNode* cur = phead->next;
    while (cur !=phead)
    {
        //保存下一个结点
        DBLSTNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    free(phead);
}

画图有利于双向链表的理解。在这里插入图片描述

打印

void DBLSTPrint(DBLSTNode* phead)
{
    //如果链表是空的会发生错误吗?
    //不会。因为phead->next还是自己。
    DBLSTNode* cur = phead->next;//这里我容易忘记指向next
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

尾插

双向带头循环链表，结构虽然复杂了，但是更容易操作了。

这就是结构设计的优势。

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
    //创建新结点
    DBLSTNode* newnode = DBLSTCreat(x);
    //找到尾结点
    DBLSTNode* tail = phead->prev;
    //插入-链接
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

头插

如果插入的时候链表是空的同样不会有影响。

有first这几个指针先动谁都行，没有first也可以，就是会有顺序要求。

示例：

在这里插入图片描述

newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
    //创建新结点
    DBLSTNode* newnode = DBLSTCreat(x);
    //拿到第一个结点
    DBLSTNode* first = phead->next;
    //插入-链接
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;
}

头删

void DBLSTPopFront(DBLSTNode* phead)
{
    //保存第一个和第二个结点
    DBLSTNode* first = phead->next;
    DBLSTNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;
}

尾删

void DBLSTPopBack(DBLSTNode* phead)
{
    //找到最后的一个结点
    DBLSTNode* tail = phead->prev;
    //找到最后一个结点的前一个结点
    DBLSTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
}

查找位置

DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
    //从第一个结点开始往下寻找，找到返回结点
    DBLSTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

使用：

DBLSTNode* pos = DBLSTFind(phead,x);
if(pos)
{
    printf("找到了");
}
else
{
    printf("没找到");
}

删除pos位置的值

void DBLSTErase(DBLSTNode* pos)
{
    //找到pos的前一个
    DBLSTNode* posPrev = pos->prev;
    //找到pos的后一个
    DBLSTNode* posNext = pos->next;
    //链接pos的前一个和pos的后一个
    posPrev->next = posNext;
    posNext->prev = posPrev;
    //释放pos
    free(pos);
    pos = NULL;
}

在pos前插入x

void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
    //知道pos前的一个结点
    DBLSTNode* posPrev = pos->prev;
    //创建新的结点
    DBLSTNode* newnode = DBLSTCreat(x);
    //将新的结点插入
    newnode->data = x;
    newnode->prev = posPrev;
    posPrev->next = newnode;
    newnode->next = pos;
    pos->prev = newnode;
}

返回链表的结点数量

int DBLSTSize(DBLSTNode* phead)
{
    //其实就是遍历一遍，找一个计数的
    int count = 0;
    DBLSTNode* cur = phead->next;
    while (cur != phead)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

判断链表是否为空

bool DBLSTEmpty(DBLSTNode* phead)
{
    //定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
    DBLSTNode* cur = phead->next;
    if (phead == cur)
    {
        //空
        return true;
    }
    else
    {
        //不为空
        return false;
    }
}

优化

为了更快的实现一个双向循环的带头链表，我们可以直接利用Insert和Erase。

如果Erase的pos位置是第一个结点，那就代表着头删，如图：

在这里插入图片描述所以头删还可以这样写：

void DBLSTPopFront(DBLSTNode* phead)
{
    DBLSTErase(phead->next);
}

尾删同理：

void DBLSTPopBack(DBLSTNode* phead)
{
    DBLSTErase(phead->prev);
}

头插：

void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
    DBLSTInsert(phead->next,x);
}

尾插：

其实就是插到头结点phead的前面。在这里插入图片描述

void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
    DBLSTInsert(phead, x);
}

总结

带头双向循环链表，任意位置插入和删除数据，时间复杂度都是O(1)。

查找最优的结构不是这个，查找就得遍历，时间复杂度还是O(N)。

查找的最优结构有三种：

平衡搜索树（AVL树和红黑树）
哈希表
B树 & B+树系列 (数据库底层核心引擎)

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DoubleListDataType;
typedef struct DoubleListNode
{
    DoubleListDataType data;
    struct DoubleListNode* next;
    struct DoubleListNode* prev;
}DBLSTNode;
//创建结点
DBLSTNode* DBLSTCreat(DoubleListDataType x)
{
    DBLSTNode* newnode = (DBLSTNode*)malloc(sizeof(DBLSTNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}
//初始化
DBLSTNode* DBLSTInit()
{
    //用一个返回值可以 替代二级指针
    DBLSTNode* phead = DBLSTCreat(0);
    //循环
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
//销毁链表
void DBLSTDestory(DBLSTNode* phead)
{
    //找到第一个结点
    DBLSTNode* cur = phead->next;
    while (cur !=phead)
    {
        //保存下一个结点
        DBLSTNode* curNext = cur->next;
        free(cur);
        cur = curNext;
    }
    free(phead);
}
//打印结点
void DBLSTPrint(DBLSTNode* phead)
{
    //如果链表是空的会发生错误吗?
    //不会。因为phead->next还是自己。
    DBLSTNode* cur = phead->next;//这里我容易忘记指向next
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
//尾插
void DBLSTPushBack(DBLSTNode* phead, DoubleListDataType x)
{
    //创建新结点
    DBLSTNode* newnode = DBLSTCreat(x);
    //找到尾结点
    DBLSTNode* tail = phead->prev;
    //插入-链接
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
    //或者
    //DBLSTInsert(phead, x);
}
//头插
void DBLSTPushFront(DBLSTNode* phead,DoubleListDataType x)
{
    //创建新结点
    DBLSTNode* newnode = DBLSTCreat(x);
    //拿到第一个结点
    DBLSTNode* first = phead->next;
    //插入-链接
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;
    //或者
    //DBLSTInsert(phead->next,x);
}
//头删
void DBLSTPopFront(DBLSTNode* phead)
{
    //保存第一个和第二个结点
    DBLSTNode* first = phead->next;
    DBLSTNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;
    /////////或者
    //DBLSTErase(phead->next);
}
//尾删
void DBLSTPopBack(DBLSTNode* phead)
{
    //找到最后的一个结点
    DBLSTNode* tail = phead->prev;
    //找到最后一个结点的前一个结点
    DBLSTNode* tailPrev = tail->prev;
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
    tail = NULL;
    //或者
    //DBLSTErase(phead->prev);
}
//查找位置
DBLSTNode* DBLSTFind(DBLSTNode* phead,DoubleListDataType x)
{
    //从第一个结点开始往下寻找，找到返回结点
    DBLSTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}
//删除pos位置的值
void DBLSTErase(DBLSTNode* pos)
{
    //找到pos的前一个
    DBLSTNode* posPrev = pos->prev;
    //找到pos的后一个
    DBLSTNode* posNext = pos->next;
    //链接pos的前一个和pos的后一个
    posPrev->next = posNext;
    posNext->prev = posPrev;
    //释放pos
    free(pos);
    pos = NULL;
}
//在pos前插入x
void DBLSTInsert(DBLSTNode* pos, DoubleListDataType x)
{
    //知道pos前的一个结点
    DBLSTNode* posPrev = pos->prev;
    //创建新的结点
    DBLSTNode* newnode = DBLSTCreat(x);
    //将新的结点插入
    newnode->data = x;
    newnode->prev = posPrev;
    posPrev->next = newnode;
    newnode->next = pos;
    pos->prev = newnode;
}
//返回链表的结点数量
int DBLSTSize(DBLSTNode* phead)
{
    //其实就是遍历一遍，找一个计数的
    int count = 0;
    DBLSTNode* cur = phead->next;
    while (cur != phead)
    {
        count++;
        cur = cur->next;
    }
    return count;
}
//判断链表是否为空
bool DBLSTEmpty(DBLSTNode* phead)
{
    //定义一个cur指向第一个结点，如果第一个结点就是phead,说明链表为空
    DBLSTNode* cur = phead->next;
    if (phead == cur)
    {
        //空
        return true;
    }
    else
    {
        //不为空
        return false;
    }
}
void Test1()
{
    DBLSTNode* phead = DBLSTInit();
    DBLSTPushBack(phead, 1);
    DBLSTPushBack(phead, 2);
    DBLSTPushBack(phead, 3);
    DBLSTPushBack(phead, 4);
    DBLSTPushFront(phead, 0);
    DBLSTPrint(phead);
    //DBLSTNode* pos = DBLSTFind(phead, 3);
    //if (pos)
    //{
    //  DBLSTErase(pos);
    //}
    DBLSTPrint(phead);
    int Count = DBLSTSize(phead);
    printf("%d", Count);
    DBLSTEmpty(phead);
    if (DBLSTEmpty(phead) == 0)
    {
        printf("不为空\n");
    }
}

int main(void)
{
    Test1();
    return 0;
}