开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构之带头结点的循环双向链表详细图片+文字讲解 -> 正文阅读

[数据结构与算法]数据结构之带头结点的循环双向链表详细图片+文字讲解

双向循环链表

前言

在开始讲解带头双向循环链表之前，我们先来看一个带哨兵位的头结点的单链表和不带哨兵位的头结点的单链表的区别：

不带哨兵位的头结点

不带哨兵位的头结点，在链表的系列操作函数中可能会修改到指向存储有效数据的第一个结点的指针plist，对在第一元素结点前插入结点和删除第一结点时，其操作与其他结点的操作不统一，我们需要在这系列操作中分别考虑不同情况

带哨兵位的头结点

这个结点不存储有效数据，链表的系列操作函数永远不会修改到指向存储有效数据的第一个结点的指针plist，因为拥有这个带哨兵位的头节点，对在第一元素结点前插入结点和删除第一结点时，其操作与其他结点的操作就统一了。这个带哨兵位的头节点看起来简单一点，为什么我们的单链表不设计这个结构呢？这个头节点的结构在实际中很少出现，包括哈希桶、邻接表做子结构都是不带头，其次就是OJ中给的链表基本都是不带头的，都有先入为主思维，我们直接写带头，容易对后面的学习产生误导。

我们链表的结构有很多，但是实际中我们最常用的还是下面两种结构：

无头单向非循环链表

结构简单，一般不会单独用来存数据，实际中更多的是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中会出现很多，因为他有很多的可考之处。

带头双向循环链表

结构很复杂，一般单独用来存数据，实际中使用的链表数据结构都是带头双向循环链表，这个结构虽然很复杂，但是代码实现它的一系列增删查改等会很简单，下面我们就实现带头双向循环链表的一系列操作。

下面我们就来看带头双向循环链表的基本操作：

文件的创建

首先我们先创建三个文件：

List.h对相关头文件的包含，以及实现双向链表的结构和函数的声明

List.c对实现双向链表增删查改等操作的函数进行定义

test.c文件进行双向链表相关函数和双向链表功能的测试

双向链表结构的定义

了解了带头双向循环链表的结构，我们先定义这样的一个结构体：

typedef struct ListNode
{
	int data;
    struct ListNode* prev;
    struct ListNode* next;
}LTNode;

和我们前面讲过的顺序表和单链表一样，我们为了方便我们数据类型的变化，我们进行类型重定义，在想要换我们的双向链表的数据类型时，直接在typedef这里修改就可以了，如下：

typedef int LTDataType;
typedef struct ListNode
{
	int data;
    struct ListNode* prev;
    struct ListNode* next;
}LTNode;

我们定义好结构之后，首先在测试文件中创建一个头结点phead，先赋值为NULL：

void Test1()
{
	LTNode* phead = NULL;
}
int main()
{
	Test1();
	return 0;
}

接下来我们对下面的带头双向链表操作进行讲解：

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(LTNode* plist);
// 双向链表打印
void ListPrint(LTNode* plist);
// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(LTNode* plist);
// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(LTNode* plist);
// 双向链表查找
ListNode* ListFind(LTNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);

我们写的双向链表是带头的，所以我们首先需要创建头结点：

创建返回链表的头结点

值传递时：

// 创建返回链表的头结点.
LTNode* ListCreate(LTNode* plist)
{
    plist = (LTNode*)malloc(sizeof(LTNode));
    if (plist == NULL)
    {
        perror("malloc plist");
        return NULL;
    }
    plist->next = plist;
    plist->prev = plist;
    return plist;
}

我们malloc一个结点，这个结点不存储数据，初始化时我们将plist的next指向它自己，plist的prev指向它自己，因为plist出函数会销毁，并且里面的形参的改变不会影响实参的改变，所以我们在值传递时需要将plist返回

地址传递：

// 创建返回链表的头结点.
LTNode* ListCreate(LTNode** plist)
{
    assert(plist);
    *plist = (LTNode*)malloc(sizeof(LTNode));
    if (*plist == NULL)
    {
        perror("malloc plist");
        return NULL;
    }
    (*plist)->next = *plist;
    (*plist)->prev = *plist;
}

为了代码的统一性，我们这里就使用值传递，因为后面的函数我们都会使用值传递，因为有了哨兵位的头结点我们不会改变phead的指向。

有双向链表的创建那就有双向链表的销毁：

双向链表的销毁

// 双向链表销毁
void ListDestory(LTNode* plist)
{
    assert(plist);//链表不为NULL，为NULL那还销毁啥
    LTNode* cur = plist->next;
    while (cur!= plist)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(plist);
    plist = NULL;//这句代码无意义，因为传值时函数里面无法改变外面的实参
}

在销毁时需要注意：

链表不为NULL，为NULL那还销毁啥，所以我们前面断言一下我们的这个链表时循环链表，如果循环的判断为cur是不是NULL，那么这个循环成死循环了，因为cur永远都不可能为NULL，所以我们判断进入循环的语句应该是cur!=plist

接下来我们来看双向链表的打印：

双向链表的打印

void ListPrint(LTNode* plist)
{
    LTNode* cur = plist->next;
    while (cur != plist)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

和前面一样，我们在遍历链表时，需要注意循环进行的条件需要是cur不等于plist。只有条件是cur不等于plist时，我们才刚好遍历了一遍链表。

接下来我们来看如何开辟一个新结点：

开辟一个新结点

//开辟一个新结点
LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc Node");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;

    return newnode;
}

我们malloc一个结点，然后将结点的data初始化，然后将next域和prev域置NULL，然后将该节点返回

接下来我们进入双向链表操作函数的主题，首先我们来看双向链表的尾插：

双向链表的尾插

// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x)
{
    LTNode* tail = plist->prev;
    LTNode* newnode = BuyListNode(x);
    tail->next = newnode;//1
    plist->prev = newnode;//2
    newnode->prev = tail;//3
    newnode->next = plist;//4
}

双向链表尾插的图解

有没有觉得比单链表的操作简单了很多，单链表我们还需要先找尾，还需要考虑没有结点时的情况，而我们的这个结构的双向链表操作尾插时间复杂度O(1)，简单了很多

我们在测试文件中测试：

下面我们来看头插：

双向链表的头插

// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x)
{
    LTNode* next = plist->next;
    LTNode* newnode = BuyListNode(x);
    newnode->next = next;
    newnode->prev=plist;
    next->prev = newnode;
    plist->next = newnode;
}

双向链表的头插图解

我们在测试文件中测试：

接下来我们来看双向链表的尾删

双向链表的尾删

//双向链表的尾删
void ListPopBack(LTNode* plist)
{
    assert(plist->next);//链表不能为空
    LTNode* tail = plist->prev;
    tail->prev->next = plist;//1
    plist->prev = tail->prev;//2
    free(tail);
    tail = NULL;
}

双向链表的尾删图解

我们在测试文件中测试：

接下来我们来看双向链表的头删

双向链表的头删

// 双向链表头删
void ListPopFront(LTNode* plist)
{
    assert(plist->next);//链表不能为空
    LTNode* next = plist->next;
    plist->next = next->next;//1
    next->next->prev = plist;//2
    free(next);
    next = NULL;
}

双向链表的头删图解

我们在测试文件中测试：

接下来我们来看双向链表查找

双向链表查找

// 双向链表查找
LTNode* ListFind(LTNode* plist, LTDataType x)
{
    assert(plist->next);
    LTNode* cur = plist->next;
    while (cur != plist)
    {
        if (cur->data == x)
        {
            return cur;//找到了，返回结点
        }
        cur = cur->next;
    }
    return NULL;//找不到
}

和前面一样，我们在遍历链表时，需要注意循环进行的条件需要是cur不等于plist。只有条件是cur不等于plist时，我们才刚好遍历了一遍链表。找到返回结点，找不到返回NULL

我们在测试文件中测试：

下面我们来看双向链表在pos的前面进行插入：

双向链表在pos的前面进行插入

// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);//pos位置不能为NULL
    LTNode* pre = pos->prev;
    LTNode* newnode = BuyListNode(x);
    pre->next = newnode;//1
    newnode->prev = pre;//2
    newnode->next = pos;//3
    pos->prev = newnode;//4
}

双向链表在pos的前面插入图解

我们在测试文件中测试：

下面我们来看双向链表删除pos位置的节点：

双向链表删除pos位置的结点

// 双向链表删除pos位置的节点
void ListErase(LTNode* pos)
{
    assert(pos);//pos位置不能为NULL
    LTNode* pre = pos->prev;
    LTNode* next = pos->next;
    pre->next = next;//1
    next->prev = pre;//2
    free(pos);
    pos = NULL;
}

双向链表删除pos位置结点图解

我们在测试文件中测试：

注意：因为我们销毁链表函数是值传递，所以我们需要在外面将phead置为NULL，我们在销毁时，要在调用函数后面一行将phead置空，不然phead就为野指针了。

ListDestory(phead);
phead=NULL;

带头结点的双向循环链表的操作我们就讲到这里，下面附上源代码：

源代码

List.h(双向链表结构及其函数的声明)

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
    int data;
    struct ListNode* prev;
    struct ListNode* next;
}LTNode;

//值传递创建头结点
LTNode* ListCreate(LTNode* phead);

//地址传递创建头结点
//LTNode* ListCreate(LTNode** phead);

// 双向链表销毁
void ListDestory(LTNode* plist);

//双向链表的打印
void ListPrint(LTNode* plist);

//开辟一个新结点
LTNode* BuyListNode(LTDataType x);

// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x);

// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x);

//双向链表的尾删
void ListPopBack(LTNode* plist);

// 双向链表头删
void ListPopFront(LTNode* plist);

// 双向链表查找
LTNode* ListFind(LTNode* plist, LTDataType x);

// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void ListErase(LTNode* pos);

List.c(双向链表函数的实现)

#include"List.h"

// 创建返回链表的头结点
//值传递创建头结点
LTNode* ListCreate(LTNode* plist)
{
    plist = (LTNode*)malloc(sizeof(LTNode));
    if (plist == NULL)
    {
        perror("malloc plist");
        return NULL;
    }
    plist->next = plist;
    plist->prev = plist;
    return plist;
}
//地址传递创建头结点
//LTNode* ListCreate(LTNode** plist)
//{
//    assert(plist);
//    *plist = (LTNode*)malloc(sizeof(LTNode));
//    if (*plist == NULL)
//    {
//        perror("malloc plist");
//        return NULL;
//    }
//    (*plist)->next = *plist;
//    (*plist)->prev = *plist;
//}

// 双向链表销毁
void ListDestory(LTNode* plist)
{
    assert(plist);//链表不为NULL，为NULL那还销毁啥
    LTNode* cur = plist->next;
    while (cur!= plist)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(plist);
    plist = NULL;//这句代码无意义，因为传值时函数里面无法改变外面的实参
}

// 双向链表打印
void ListPrint(LTNode* plist)
{
    LTNode* cur = plist->next;
    while (cur != plist)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("\n");
}


//开辟一个新结点
LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc Node");
        return NULL;
    }
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;

    return newnode;
}

// 双向链表尾插
void ListPushBack(LTNode* plist, LTDataType x)
{
    LTNode* tail = plist->prev;
    LTNode* newnode = BuyListNode(x);
    tail->next = newnode;
    plist->prev = newnode;
    newnode->prev = tail;
    newnode->next = plist;
}

// 双向链表头插
void ListPushFront(LTNode* plist, LTDataType x)
{
    LTNode* next = plist->next;
    LTNode* newnode = BuyListNode(x);
    newnode->next = next;
    newnode->prev = plist;
    next->prev = newnode;
    plist->next = newnode;
}

//双向链表的尾删
void ListPopBack(LTNode* plist)
{
    assert(plist->next);//链表不能为空
    LTNode* tail = plist->prev;
    tail->prev->next = plist;
    plist->prev = tail->prev;
    free(tail);
    tail = NULL;
}

// 双向链表头删
void ListPopFront(LTNode* plist)
{
    assert(plist->next);//链表不能为空
    LTNode* next = plist->next;
    plist->next = next->next;
    next->next->prev = plist;
    free(next);
    next = NULL;
}

// 双向链表查找
LTNode* ListFind(LTNode* plist, LTDataType x)
{
    assert(plist->next);
    LTNode* cur = plist->next;
    while (cur != plist)
    {
        if (cur->data == x)
        {
            return cur;//找到了，返回结点
        }
        cur = cur->next;
    }
    return NULL;//找不到
}

// 双向链表在pos的前面进行插入
void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* pre = pos->prev;
    LTNode* newnode = BuyListNode(x);
    pre->next = newnode;
    newnode->prev = pre;
    newnode->next = pos;
    pos->prev = newnode;
}

// 双向链表删除pos位置的节点
void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode* pre = pos->prev;
    LTNode* next = pos->next;
    pre->next = next;
    next->prev = pre;
    free(pos);
    pos = NULL;
}

test.c(双向链表函数功能的测试)

#include"List.h"
void Test1()
{
	LTNode* phead = NULL;
	phead = ListCreate(phead);
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);

	ListPushFront(phead, 5);
	ListPushFront(phead, 6);
	ListPrint(phead);

	ListPopBack(phead);
	ListPrint(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPrint(phead);

	LTNode* pos= ListFind(phead, 2);
	printf("%d\n", pos->data);

	LTNode* pos1 = ListFind(phead, 2);
	ListInsert(pos1, 10);
	ListPrint(phead);

	LTNode* pos2 = ListFind(phead, 10);
	ListErase(pos2);
	ListPrint(phead);

	ListDestory(phead);
	phead = NULL;
}
int main()
{
	Test1();
	return 0;
}