【初阶数据结构篇】双向链表的实现（赋源码）-阿里云开发者社区

双向链表

前言

在上一篇博客中介绍了单链表（不带头单向不循环链表）的实现方法，本篇将介绍双向链表（带头双向循环链表）的实现方法。

虽然双向链表在结构上比单向链表复杂，每个结点都多了一个指向上一个结点的前驱指针，但在实现上比单链表简单很多~~

读者大大一一往下看就明白了

代码位置

[Gitee](List/List · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))

双向链表的实现

双向链表的初始化和打印及销毁

List.h(其中方法会一一讲到)

定义链表结构
将存储数据类型重命名(方便之后替换->例如我们要求单链表内存储char类型数据，只用改一行代码即可)
函数的声明，声明的时候参数只需要类型就可以了，名字加不加都一样

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

//打印链表
void Print(LTNode*);
//初始化
void LTInit(LTNode**);


//插入数据
void LTPushBack(LTNode*,LTDataType);
void LTPushFront(LTNode*,LTDataType);


//删除
//判空
bool LTEmpty(LTNode*);

void LTPopBack(LTNode*);
void LTPopFront(LTNode*);


//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在指定位置之前或之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
void LTInsertBefore(LTNode* pos, LTDataType x);


//删除指定位置的节点
void LTErase(LTNode* pos);

//销毁
void LTDestroy(LTNode**);

//为了保持接口的一致性,优化代码
//将初始化和销毁函数传递的参数统一为一级指针
void LTDestroy2(LTNode*);
LTNode* LTInit2();

test.c

用来测试我们写的函数(函数的调用)
这一部分就是自己写的时候用的测试用例，随便什么都行

养成好习惯，写一个方法测试一次，不然找错误的时候会很痛苦😜

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void ListTest01()
{
  //LTNode* plist = NULL;
  //LTInit(&plist);//初始化,只有一个哨兵位,为空链表
   
  
  //保持接口一致性使用一级指针
  LTNode* plist = LTInit2();


  //测验尾插
  LTPushBack(plist, 4);
  //LTPushBack(plist, 3);
  //LTPushBack(plist, 4);
  //LTPushBack(plist, 5);

  //测验头插
  LTPushFront(plist, 1);
  LTPushFront(plist, 2);
  LTPushFront(plist, 3);
  //LTNode* pos=LTFind(plist, 2);
  //if (pos == NULL)
//  printf("没有找到\n");
//else
//  printf("找到了\n");


  //在指定位置之后插入数据;
  //LTInsert(pos, 6);
  //在指定位置之前插入数据
  //LTInsertBefore(pos, 7);

  //删除指定位置数据
  //LTErase(pos);
  

  //测验尾删
  //LTPopBack(plist);
  //LTPopBack(plist);
  //LTPopBack(plist);
  //LTPopBack(plist);
  // 测验头删
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPopFront(plist);
  //LTPopFront(plist);
   
  //LTDestroy(&plist);

  //保持接口一致性使用一级指针
  LTDestroy2(plist);//记得把plist置为NULL
  plist = NULL;
  Print(plist);
}
int main()
{
  ListTest01();
  return 0;
}

双向链表的初始化

双向链表的头结点只是拿来保存第一个节点的地址的，不用来存储有效数据，双向链表为空的时候就是只有头结点，所以双向链表初始化就是申请一个头结点，并让plist指向头结点即可

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

注意：这里在申请新节点的时候，我们让它的next指针和prev指针都指向自己（否则只有一个头结点时就不叫循环链表了）

我们可以和单链表一样，将plist的地址传过去，然后进行初始化

void LTInit(LTNode** pphead)
{
  //创建头结点(哨兵位)
  *pphead = LTBuyNode(-1);
}

为了保持接口的一致性（在之后的方法我们都是传一级指针），此处也采用一级指针更好

LTNode* LTInit2()
{
  return LTBuyNode(-1);
}

通过函数的返回值我们就让plist指向了新申请的头结点

双向链表的打印

void Print(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d ", pcur->data);
    pcur = pcur->next;
  }
}

基本思想还是定义一个pcur指针来遍历，与单链表相同
不同的是结束条件，因为尾节点的next指针指向的是头结点，当pcur指向到头结点时结束遍历
开始时让pcur指向头结点下个结点，头结点只是拿来存放地址的，不存放有效数据，不要打印里面的数据

双向链表的销毁

和单链表一样，传二级指针
最后别忘了销毁头结点

//销毁链表
void LTDestroy(LTNode** pphead)
{
  assert(pphead&&*pphead);
  LTNode* pcur, * next;
  pcur = (*pphead)->next;
  while (pcur != *pphead)
  {
    next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //销毁头结点
  free(*pphead);
  *pphead = NULL;
  pcur = NULL;
}

同样的，也是为了保持接口的一致性，建议使用一级指针

void LTDestroy2(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  free(phead);
  phead=pcur = NULL;
}

在main函数中调用完这个函数后，别忘了把plist置为空！！！

双向链表的插入

只要是插入都先改newnode的两个指针（否则可能会导致找不到下一个或上一个结点了）
再根据插入方式改变受到影响的两个节点的prev或是next指针即可

双向链表头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  LTNode* newnode = LTBuyNode(x);
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}

双向链表尾插

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  LTNode* newnode = LTBuyNode(x);
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}

双向链表在指定位置之后插入数据

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  newnode->prev = pos;
  newnode->next = pos->next;
  //pos->next = newnode;
  //newnode->next->prev = newnode;
  pos->next->prev = newnode;
  pos->next = newnode;
}

双向链表的删除

删除都别忘了判空
只有一个头结点为空

//判空
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}

将要删除的节点保存，然后更改前后结点的next指针或prev指针，最后释放

双向链表的头删

//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* del = phead->next;
  del->next->prev = phead;
  phead->next = del->next;
  free(del);
  del = NULL;
}

双向链表的尾删

//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* del = phead->prev;
  phead->prev = del->prev;
  del->prev->next = phead;
  free(del);
  del = NULL;

}

双向链表在指定位置删除数据

//删除指定位置节点
void LTErase(LTNode* pos)
{
  LTNode* del = pos;
  del->prev->next = pos->next;
  del->next->prev = del->prev;
  free(pos);
  pos = NULL;
}

双向链表查找指定位置节点

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}

找到就返回指向节点的指针，否则返回空

List.c(完整版)

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//打印链表
void Print(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    printf("%d ", pcur->data);
    pcur = pcur->next;
  }
}

//申请新节点
LTNode* LTBuyNode(LTDataType x)
{
  LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
  if (newnode == NULL)
  {
    perror("malloc fail!");
    exit(1);
  }
  newnode->data = x;
  newnode->next = newnode->prev = newnode;
  return newnode;
}


//初始化链表
void LTInit(LTNode** pphead)
{
  //创建头结点(哨兵位)
  *pphead = LTBuyNode(-1);
}


//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
  LTNode* newnode = LTBuyNode(x);
  newnode->next = phead;
  newnode->prev = phead->prev;
  phead->prev->next = newnode;
  phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
  LTNode* newnode = LTBuyNode(x);
  newnode->next = phead->next;
  newnode->prev = phead;
  phead->next->prev = newnode;
  phead->next = newnode;
}

//判空
bool LTEmpty(LTNode* phead)
{
  assert(phead);
  return phead->next == phead;
}


//尾删
void LTPopBack(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* del = phead->prev;
  phead->prev = del->prev;
  del->prev->next = phead;
  free(del);
  del = NULL;

}


//头删
void LTPopFront(LTNode* phead)
{
  assert(phead);
  assert(!LTEmpty(phead));
  LTNode* del = phead->next;
  del->next->prev = phead;
  phead->next = del->next;
  free(del);
  del = NULL;
}




//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    if (pcur->data == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}



//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  newnode->prev = pos;
  newnode->next = pos->next;
  //pos->next = newnode;
  //newnode->next->prev = newnode;
  pos->next->prev = newnode;
  pos->next = newnode;
}


//在指定位置之前插入数据
void LTInsertBefore(LTNode* pos, LTDataType x)
{
  assert(pos);
  LTNode* newnode = LTBuyNode(x);
  newnode->next = pos;
  newnode->prev = pos->prev;
  pos->prev = newnode;
  newnode->prev->next = newnode;
}

//删除指定位置节点
void LTErase(LTNode* pos)
{
  LTNode* del = pos;
  del->prev->next = pos->next;
  del->next->prev = del->prev;
  free(pos);
  pos = NULL;
}


//销毁链表
void LTDestroy(LTNode** pphead)
{
  assert(pphead&&*pphead);
  LTNode* pcur, * next;
  pcur = (*pphead)->next;
  while (pcur != *pphead)
  {
    next = pcur->next;
    free(pcur);
    pcur = next;
  }
  //销毁头结点
  free(*pphead);
  *pphead = NULL;
  pcur = NULL;
}


void LTDestroy2(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  while (pcur != phead)
  {
    LTNode* next = pcur->next;
    free(pcur);
    pcur = next;
  }
  free(phead);
  phead=pcur = NULL;
}


LTNode* LTInit2()
{
  return LTBuyNode(-1);
}

在双向链表的实现方法中，有几点总结心得

因为头结点的存在，plist指针始终指向头结点，不会改变。所以在插入删除等操作时不必像单链表一样分情况讨论，同时在接口上也只需传一级指针即可，对此在初始化和销毁方法上进行了优化

双向链表在遍历时如果一直沿着next或prev指针遍历会陷入死循环，所以结束条件是pcur!=phead.

总之，可以发现虽然双向链表比单链表多了一个前驱指针，但在实现方法上比单链表简单很多

链表与顺序表的比较

最后，介绍完链表与顺序表后，将二者进行总结比较

【初阶数据结构篇】双向链表的实现（赋源码）

双向链表

前言

代码位置

双向链表的实现

双向链表的初始化和打印及销毁

双向链表的初始化

双向链表的打印

双向链表的销毁

双向链表的插入

双向链表头插

双向链表尾插

双向链表在指定位置之后插入数据

双向链表的删除

双向链表的头删

双向链表的尾删

双向链表在指定位置删除数据

双向链表查找指定位置节点

链表与顺序表的比较

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【初阶数据结构篇】双向链表的实现（赋源码）

前言

代码位置

双向链表的实现

双向链表的初始化和打印及销毁

双向链表的初始化

双向链表的打印

双向链表的销毁

双向链表的插入

双向链表头插

双向链表尾插

双向链表在指定位置之后插入数据

双向链表的删除

双向链表的头删

双向链表的尾删

双向链表在指定位置删除数据

双向链表查找指定位置节点

链表与顺序表的比较

热门文章

最新文章

相关课程

相关电子书