0
0

双向带头循环链表之重拳出击

目录

一、 链表的8种结构

1、不带头单向循环结构

2、不带头单向⾮循环结构
3、不带头双向循环结构
4、不带头双向⾮循环结构
5、带头单向循环结构
6、带头单向⾮循环结构
7、带头双向循环结构
8、带头双向⾮循环结构

但是其中我们最常用的就两种，一种是我之前说过的单链表 ，另一种就是我今天要说的双向带头循环链表。双向带头循环链表是非常实用的链表，它结构复杂但是操作简单，等你学完你也就瞧不上其他链表了。

** 双向带头循环链表的结构是这样的**：

好让我们上手写一下。

二、 双向带头循环链表的实现

**结构的创建和初始化 **

首先我们写一下我们所需要的头文件

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

其次我们在创建它的结构时要有一个前驱指针，还要有一个后继指针 

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

结构创建好了，那就实现功能了。

需要实现一下几个基本功能

//初始化
LTNode* ListInit();

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//打印
void ListPrint(LTNode* phead);

//头插
void ListPushFront(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

//头删
void ListPopFront(LTNode* phead);

//判空
bool ListEmpty(LTNode* phead);

//在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x);

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

//链表长度
int ListSize(LTNode* phead);

//销毁链表
void ListDestory(LTNode* phead);

申请结点

LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
}

初始化

初始化的话有两种方法可以用

方法一：二级指针

void ListInit(LTNode** pphead)
{
    *pphead = BuyListNode(-1);
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}

方法二：用结构体指针作为返回值** 申请结点**

LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
}

尾插

如果学习了单链表的话，这个对于你来说不就是小菜一碟嘛

当然跟单链表不同的是双向链表就不用像单链表那样遍历找尾了，因为它头结点的prev就指向了尾结点所以变得更简单了。

链接过程 ：

代码实现：

void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    newnode->prev = tail;
    tail->next = newnode;
    newnode->next = phead;
    phead->prev = newnode;
}

当链表为空时，这个代码（也包括我下面的代码）也同样可以运行，不信你就顺着这个代码的思路理一遍

打印

代码实现： 

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

** 注意**：可不是从头开始打印，而是头结点的下一个位置，别忘了我们可是设了哨兵位的。

头插

头插其实也很简单

代码实现： 

void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode= BuyListNode(x);
    LTNode* next = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;
}

当然你也可以不用像我这样定义一个next，但是你逻辑（链接的先后顺序）要捋顺，否则可是会出错的。

尾删

代码实现：

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(! ListEmpty(phead));
    assert(phead->next!=phead);
    LTNode* tail = phead->prev;
    LTNode* tailprev = tail->prev;
    free(tail);
    phead->prev = tailprev;
    tailprev->next = phead;
}

双向链表的尾删其实也不难，我们可以先用phead->prev找到尾结点，free点尾结点，之后再将新的尾结点和phead进行链接。

头删

代码实现：

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(!ListEmpty(phead));
    LTNode* head = phead->next;
    LTNode* headnext = head->next;
    free(head);
    phead->next = headnext;
    headnext->prev = phead;
}

思路和尾删的一样，phead->next找到头，free掉头结点，再将新的头和phead进行链接就完事了。

判空

上面的头删和尾删都离开不了判空。所以说判空其实挺重要的。

代码实现：

bool ListEmpty(LTNode* phead)
{
    assert(phead);
    return phead->next == phead;
}

两行代码就搞定了，是不是感觉有点不太相信。其实它真就值这两行代码。

链表长度

代码实现：

int  ListSize(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    int size = 0;
    while (cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

**得到链表的长度和打印链表的思路一致，我们要从头结点的下一个结点进行遍历，一直到cur==phead就结束，最后返回长度（size）就OK了。 **

销毁链表

代码实现：

void ListDestory(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    int size = 0;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        ListPopFront(cur);
        cur = next;
    }
    free(phead);
}

销毁的话和单链表是类似的，但是这里还要多一步，因为我们是带了哨兵位的头结点，我们要把这个哨兵位也删掉。

最精彩的部分当然要最后讲啦

曾经有个面试官面试的时候，叫人十分钟写出一个双链表，可别觉得面试官为难你，看了我下面讲的，你熟悉的话十分钟都不要就可以搞定。

在pos位置之前插入结点

代码实现：

void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* prev = pos->prev;
    LTNode* newnode = BuyListNode(x);
    //prev newnode pos
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

我们要先判断pos位置为不为空，然后找到pos位置的前一个，申请新节点，最后再将（pos、prev、newnode）进行链接就行了

删除pos位置的结点

代码实现：

void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode* posprev = pos->prev;
    LTNode* posnext = pos->next;
    posprev->next = posnext;
    posnext->prev = posprev;
    free(pos);
}

同样的我们先判断pos位置为不为空，然后我们在链接posprev和posnext,别忘了最后还要free掉pos结点。

**前面的头插、尾插、头删、尾删直接调用这两个函数就行了。 **

所以说十分钟写好一个双链表真的不是夸张。

三、完整代码

头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

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

//初始化
//void ListInit(LTNode** pphead);
LTNode* ListInit();

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//打印
void ListPrint(LTNode* phead);

//头插
void ListPushFront(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

//头删
void ListPopFront(LTNode* phead);

//判空
bool ListEmpty(LTNode* phead);

//在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x);

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

//链表长度
int ListSize(LTNode* phead);

//销毁链表
void ListDestory(LTNode* phead);

源文件：

#define _CRT_SECURE_NO_WARNINGS 1

#include "Dlist.h"

LTNode* BuyListNode(LTDataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    node->prev = NULL;
}

//void ListInit(LTNode** pphead)
//{
//    *pphead = BuyListNode(-1);
//    (*pphead)->next = *pphead;
//    (*pphead)->prev = *pphead;
//}
LTNode* ListInit()
{
    LTNode* phead= BuyListNode(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    /*LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    newnode->prev = tail;
    tail->next = newnode;
    newnode->next = phead;
    phead->prev = newnode;*/
    ListInsert(phead, x);
}
void ListPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void ListPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    //LTNode* newnode= BuyListNode(x);
    1
    //LTNode* next = phead->next;
    //phead->next = newnode;
    //newnode->prev = phead;
    //newnode->next = next;
    //next->prev = newnode;
    2
    //phead->next->prev = newnode;
    //newnode->next = phead->next;
    //phead->next = newnode;
    //newnode->prev = phead;
    ListInsert(phead->next, x);
}

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(! ListEmpty(phead));
    /*assert(phead->next!=phead);
    LTNode* tail = phead->prev;
    LTNode* tailprev = tail->prev;
    free(tail);
    phead->prev = tailprev;
    tailprev->next = phead;*/
    ListErase(phead->prev);
}

void ListPopFront(LTNode* phead)
{
    assert(phead);
    assert(!ListEmpty(phead));
    /*LTNode* head = phead->next;
    LTNode* headnext = head->next;
    free(head);
    phead->next = headnext;
    headnext->prev = phead;*/
    ListErase(phead->next);
}

bool ListEmpty(LTNode* phead)
{
    assert(phead);
    return phead->next == phead;
}

void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* prev = pos->prev;
    LTNode* newnode = BuyListNode(x);
    //prev newnode pos
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
    assert(pos);
    LTNode* posprev = pos->prev;
    LTNode* posnext = pos->next;
    posprev->next = posnext;
    posnext->prev = posprev;
    free(pos);
}

int  ListSize(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    int size = 0;
    while (cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

void ListDestory(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    int size = 0;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        ListErase(cur);
        cur = next;
    }
    free(phead);
}

总结：

双链表****的功能十分强大，虽然说结构可能复杂了一点但是插入删除的效率是非常的高，十分的好用。

觉得内容有用的话，就给博主三连吧

标签： 链表 数据结构 散列表
本文转载自: https://blog.csdn.net/m0_62537611/article/details/125028346
版权归原作者 代码干就完了 所有， 如有侵权，请联系我们删除。
登录后发布评论

“双向带头循环链表之重拳出击”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

C#与C++交互开发系列（二十）：跨进程通信之共享内存（Shared Memory）

hadoop技术实验- 第4章 HBase 开发：使用Java操作HBase

智能对话微信前端小程序设计与开发

前端配置开发环境：新电脑配置前端开发环境，Vue开发环境配置的详细过程

SpringBoot集成MQTT服务器和客户端并通过WebSocket将消息实时发送到前端（本地搭建MQTT服务器）

idea | 搭建 SpringBoot 项目之配置 Maven

Python毕业设计选题：基于django+vue的全国民宿信息管理系统

文章导航