一篇解双链表（0基础看）（C语言）《数据结构与算法》

谁都不能阻挡你成为更优秀的人。

序言

首先本文是和上一篇单链表有关联哈，上篇文章已经详细说明了链表的概念和分类，这里就不过多赘述了，就简单说明一下哈，链接在下面。一篇解单链表（0基础看）（C语言）《数据结构与算法》_原来45的博客-CSDN博客

上文我们讲到了链表最重要的两个分类，一个是单向不带头不循环，本篇文章就讲另一个重要的带头双向循环链表哈，废话不多说，直接看代码。

对了，这里附上作者的qq：2777137742。要是有什么问题可以在qq上面问我哈，或者文章有错误的地方，期待和大家共同讨论，因为csdn的消息有可能会遗漏哈，最后感谢你的支持。

带头双向循环链表

1. 概念

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都

是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带

来很多优势，实现反而简单了，后面我们代码实现了就知道了。

这里我们来慢慢揭晓上文说到的实现更简单，以及单链表的缺点。缺点就直接说了，我们可以很直观得发现单链表的两个很大的缺点，一个是尾插尾删等都是需要遍历也就是说时间复杂度是O（N），但是双链表对应的都是O（1），效率之高。另一个缺点就是单链表不能找到自己的上一个节点，这都是很大的缺陷。然后我们接着看双链表实现的优势。

2. 效果展示图

3. 接口实现

还是老话，对于接口的实现我们首先是要知道要实现什么，本文是对于双链表的基本使用，所以就只实现顺序表的增删查改，还有特定位置前插入和删除特定位置值等当然代码也不一定要作者这么写，这里只是提供一种思路，废话不多说，看代码。

3.01. 本文章要实现的接口

3.02. 双链表的实现

这是命名是ListNode是与c++对应的，大家也可以和单链表SListNode对应取名DListnode，但是作者为了养成一个好的习惯就取名为了ListNode哈。

3.03. 双链表的初始化

注意这里初始化是自己指向自己，因为是循环，然后本篇文章不用二级指针（不用传地址），这里就用了一个返回值。

3.04. 打印链表

3.05. 动态申请一个节点

3.06. 头插

3.07. 尾插

3.08. 头删

3.09. 尾删

3.10. 查某个值，返回地址

3.11. 某个位置前插入数据

3.12. 删除某个位置数据

3.13. 改某个值

3.14. 销毁

总结

我们可以发现对于带头双向循环链表的实现不需要像单链表那样要去判断没有或者有一个节点的情况，结构非常之完美，可以利用头结点进行各种变化，实现也非常简单，而且也不用传地址。

这里要再解释一下为什么可以不传地址，因为我们的头没有改变，不需要改变头，这个改变指的是我们一开始传的参数plist，他是一直指向我们的头的，是指向没有变，内容可以改变，也就是说plist的前驱prev和后继next的指向和date是可以变的，这个理解很重要！

4. 源代码

test.c

#include"List.h"

int main()
{
    printf("初始化\n");
    ListNode* plist = ListInit();
    printf("头插 1 2 3 并打印\n");
    ListPushFront(plist, 1);
    ListPushFront(plist, 2);
    ListPushFront(plist, 3);
    ListPrint(plist);
    printf("尾插4 5 6 并打印\n");
    ListPushBack(plist, 4);
    ListPushBack(plist, 5);
    ListPushBack(plist, 6);
    ListPrint(plist);
    printf("头删并打印\n");
    ListPopFront(plist);
    ListPrint(plist);
    printf("尾删并打印\n");
    ListPopBack(plist);
    ListPrint(plist);
    printf("1前插入3并打印\n");
    ListNode* pos = ListFind(plist, 1);
    ListInsert(plist, pos, 3);
    ListPrint(plist);
    printf("2前插入8并打印\n");
    pos = ListFind(plist, 2);
    ListInsert(plist, pos, 8);
    ListPrint(plist);
    printf("删除4并打印\n");
    pos = ListFind(plist, 4);
    ListErase(plist, pos);
    ListPrint(plist);
    printf("把1改成9并打印\n");
    ListChange(plist, 1, 9);
    ListPrint(plist);
    printf("销毁链表\n");
    ListDestory(plist);
    return 0;
}

List.h

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

typedef int ListDateType;

typedef struct ListNode
{
    struct ListNode* prev;
    struct ListNode* next;
    ListDateType date;
}ListNode;

//增删查改

//初始化
ListNode* ListInit();
//销毁
void ListDestory(ListNode* phead);
//得到一个节点
ListNode* BuyListNode(ListDateType x);
//打印
void ListPrint(ListNode* phead);

//头插
void ListPushFront(ListNode* phead, ListDateType x);
//尾插
void ListPushBack(ListNode* phead, ListDateType x);
//头删
void ListPopFront(ListNode* phead);
//尾删
void ListPopBack(ListNode* phead);

//查某个值，返回地址
ListNode* ListFind(ListNode* phead, ListDateType x);
//改某个值
void ListChange(ListNode* phead, ListDateType source, ListDateType destination);

//某个位置前插入数据
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x);
//删除某个位置数据
void ListErase(ListNode* phead, ListNode* pos);

List.c

#include"List.h"

//初始化
ListNode* ListInit()
{
    ListNode* phead = BuyListNode(0);
    phead->prev = phead;
    phead->next = phead;
    phead->date = 0;
    return phead;
}

//得到一个节点
ListNode* BuyListNode(ListDateType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->prev = NULL;
    newnode->next = NULL;
    newnode->date = x;
    return newnode;
}

//头插
void ListPushFront(ListNode* phead, ListDateType x)
{
    assert(phead);
    ListNode* newnode = BuyListNode(x);
    ListNode* first = phead->next;

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

//尾插
void ListPushBack(ListNode* phead, ListDateType x)
{
    assert(phead);
    ListNode* tail = phead->prev;
    ListNode* newnode = BuyListNode(x);

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

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

//头删
void ListPopFront(ListNode* phead)
{
    assert(phead);
    //别把头删了
    assert(phead->next != phead);
    ListNode* first = phead->next;
    phead->next = first->next;
    first->next->prev = phead;

    free(first);
    first = NULL;
}

//尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    //别把头删了
    assert(phead->next != phead);
    ListNode* tail = phead->prev;
    ListNode* prev = tail->prev;

    prev->next = phead;
    phead->prev = prev;
    free(tail);
    tail = NULL;
}

//查某个值，返回地址
ListNode* ListFind(ListNode* phead, ListDateType x) 
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->date == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

//某个位置前插入数据   
void ListInsert(ListNode* phead, ListNode* pos, ListDateType x)
{
    assert(phead);
    ListNode* newnode = BuyListNode(x);
    ListNode* prev = pos->prev;
    
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

//删除某个位置数据
void ListErase(ListNode* phead, ListNode* pos)
{
    assert(phead);
    //别把头删了
    assert(phead->next != phead);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;

    prev->next = next;
    next->prev = prev;
    free(pos);
    pos = NULL;
}

//改某个值
void ListChange(ListNode* phead, ListDateType source, ListDateType destination)
{
    assert(phead);
    ListNode* pos = ListFind(phead, source);
    pos->date = destination;
}

//销毁
void ListDestory(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    ListNode* tail = cur->next;
    while (tail != phead)
    {
        free(cur);
        cur = NULL;
        cur = tail;
        tail = tail->next;
    }
    free(cur);
    cur = NULL;
    if (cur != tail)
    {
        free(tail);
        tail = NULL;
    }
}

今天的内容就到这里了哈！！！

要是认为作者有一点帮助你的话！

就来一个点赞加关注吧！！！当然订阅是更是求之不得！

赠人玫瑰，手有余香=。=！

最后的最后感谢大家的观看！！！

你们的支持是作者写作的最大动力！！！

下期见哈！！！