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

双向链表

前言

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

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

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

代码位置

[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.

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

链表与顺序表的比较

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

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