【数据结构】双向链表的增删查改（C 代码实现）-阿里云开发者社区

前言

引入双向链表：关于单链表的问题与讨论

单链表存在的毛病：

因为单链表只能单向遍历链表，
对于前插这个操作，单链表必须得找到所需前插节点位置的前一个，那么这时就得从头指针重新遍历一次链表，会造成时间复杂度大大增加。
没有头节点（哨兵位）无法删除首节点

这些都大大提高了时间复杂度 [ 关于算法的时间复杂度与空间复杂度这一专题，我在之前写的一篇专题中有详细的讲解，有需要的可以点击链接了解一下算法的时间复杂度与空间复杂度 ]

【注意：不要下意识觉得链表就一定有哨兵位，可以有，也可以没有！】

正是因为单链表只能 单向遍历 这一特性所带来各种的麻烦，前人设计出了双向链表。

一、双向链表的特性简概

特性：

双向
循环

正是因为有这两个特性，促成了双向链表很多优势：

不需要像单链表那样从 头节点完整遍历一边链表，才能找到尾节点。
双向链表：直接 phead->prev 找到尾节点（双向、循环 的特性）。
且找到需要处理的节点，还需要从头节点再遍历一次链表，只为找到该节点的前一个节点，才能对该节点进行处理。
双向链表：pos->prev前一节点

双向链表逻辑样例图

代码实现

//类型声明 
typedef int LTDataType;      //数据类型重命名
typedef struct ListNode      //结构体类型声明
{                            //两头的指针变量 储存双向两旁结构体的地址
  struct ListNode* prev;   //保存前一个节点的指针
  LTDataType data;
  struct ListNode* next;   //保存后一个节点的指针
}ListNode;

二、双链表的增删查改【C 代码实现】

（一）创建文件

List.h （双向链表双向链表的类型定义、接口函数声明、引用的头文件)

List.c （双向链表接口函数的实现）

test.c （主函数、测试顺序表各个接口功能）

(二)List.h

1. 头文件声明

#pragma once  //防止头文件重复包含
//头文件
#include<stdio.h> 
#include<stdlib.h>
#include<assert.h>

2. 双向结构体类型声明

//类型声明 
typedef int LTDataType;      //数据类型重命名
typedef struct ListNode      //结构体类型声明
{   
  struct ListNode* prev;   //两头的指针变量 储存双向两旁结构体的地址
  LTDataType data;
  struct ListNode* next;
}ListNode;

（三）List.c

1.创建返回双向链表的头结点.

图解

phead 的含义 = pointer to head

// 创建返回链表的头结点.
ListNode* ListCreate() {
  ListNode* phead = (ListNode*)malloc(sizeof(ListNode));  
    //结构体指针phead 存的是malloc为新结构体开辟内存后 的返回的该新节点的指针 
  assert(malloc);
  return phead; //phead传的是phead指针的内容=head地址 =>返回结构体地址 
}

2. 双向链表的初始化

// 双向链表的初始化
void ListInit(ListNode* phead) {       //也用phead接受传过来的head的地址
  assert(phead);
  phead->prev = phead->next;
  phead->data = 0;                  //加深对指针的理解
  phead->next = phead->prev;    //直接用head【记住：1. **名 直接用的是内容** 明白这点 对于指针的理解就轻松很多】
                              //2. -> 只能对指针使用 且不支持二级指针解引用*后得到一级指针的形式
                                // （如：ListNode** pphead  **pphead->data (x)好像不行 去试一下 ） 
                                 【关于指针注意的点的讲解】
}

【关于指针注意的点的讲解】：加深对指针的理解

直接用head => 名直接用的是内容 明白这点对于指针的理解就轻松很多

-> 只能对指针使用且不支持二级指针解引用后得到一级指针的形式
（如：ListNode* pphead
**pphead->data (x) 好像不行去试一下）

3.创建返回新节点

// 创建返回新节点
ListNode* BuynewNode(x) {
  ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
  newNode->data = x;
  return newNode;
}

4.双向链表尾插

// 双向链表尾插
void ListPushBack(ListNode* phead,LTDataType x) {
  ListNode* newNode = BuynewNode(x);             //1M的空间可创建出一千多万个指针变量
  ListNode* tail = phead->prev;                  //多创建指针变量 自己也标的看的清楚 增加代码的可读性
  tail->next = newNode;
  newNode->prev = tail;
  newNode->next = phead;
  phead->prev = newNode;
}

5.双向链表头插

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x) { 
  ListNode* newNode = BuynewNode(x);
  ListNode* first = phead->next;        //第一个节点
  newNode->next = first;
  first->prev = newNode;
  phead->next = newNode;
  newNode->prev = phead;
}

6.双向链表尾删

// 双向链表尾删
void ListPopBack(ListNode* phead) {
  assert(phead);
  assert(phead->next != phead);        //确保链表不为空，有东西可删，及时报错
  ListNode* tailPrev = phead->prev->prev;
  ListNode* tail = phead->prev;
  free(tail);
  tail = NULL;
  tailPrev->next = phead;
  phead->prev = tailPrev;
}

7.双向链表头删

// 双向链表头删
void ListPopFront(ListNode* phead) {
  assert(phead);
  assert(phead->next != phead);    
  ListNode* newNext = phead->next->next;
  ListNode* Next = phead->next;          //新建指针变量 保存好要free掉的节点的地址
  free(Next);                            //就不用怕后续改变各节点之间的指针关系时把该节点的地址弄丢了
  Next = NULL;
  phead->next = newNext;
  newNext->prev = phead;
}

8.双向链表查找

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) {
  ListNode* Head = phead->next;         //设置两个指针变量，一个从头开始遍历，一个从后遍历
  ListNode* Back = phead->prev;
  while (Head!=Back) {
    if (Head->data = x)
      return Head;
    else if (Back->data = x)
      return Back;
    Head = Head->next;
    Back = Back->prev;
  }
  return NULL;
}

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

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
  ListNode* posPrev = pos->prev;
  ListNode* newNode = BuynewNode(x);
  posPrev->next = newNode;
  newNode->prev = posPrev;
  newNode->next = pos;
  pos->prev = newNode;
}

★10. 双向链表删除pos位置的节点

// 双向链表删除pos位置的节点                 //若传过来的pos=phead->next  =>作头删作用
void ListErase(ListNode* pos) { 
  ListNode* posPrev = pos->prev;        //若传过来的pos=phead（由于双向链表具有循环的特性） =>作尾删作用
  ListNode* posNext = pos->next;
                                        //也正是由于双向链表具有循环的特性，即使链表中只有一个节点也能很好的运行
  posPrev->next = posNext;              //图解
  posNext->prev = posPrev;
  free(pos);
  pos = NULL;
}

Erase函数以后头删和尾删也可以这样写

10.1 双向链表尾删【ListErase版本】

void ListPopBack(ListNode* phead) {
  assert(phead);
  assert(phead->next != phead);     //确保链表不为空，有东西可删，及时报错
  ListErase(phead);
  }

10.2 双向链表头删【ListErase版本】

// 双向链表头删【ListErase版本】
void ListPopFront(ListNode* phead) {
  assert(phead);
  assert(phead->next != phead);     //确保链表不为空，有东西可删，及时报错
  ListErase(phead->next);
}

11.双向链表打印

11.1 递归实现

// 双向链表打印  递归实现
void ListPrint(ListNode* phead) {
  assert(phead);
    ListNode* cur = phead->next;
  while (cur!=phead) {
  printf("%d <=>", cur->data);
  cur = cur->next;
  ListPrint(cur);
  }
  printf("\n");
}

11.2 非递归实现

// 双向链表打印  非递归实现
void ListPrint(ListNode* phead) {
  assert(phead);
  ListNode* cur = phead->next;
  while (cur!=phead) {
  cur = phead->next;
  printf("%d <=>", cur->data);
  }
}

12. 双向链表销毁

// 双向链表销毁
void ListDestory(ListNode* phead) {
  ListNode* cur = phead->next;
  while (cur!=phead) {
  ListNode* curNext = cur->next;
  free(cur);
  cur = curNext;
  }
  free(phead);
  phead = NULL;
}

三、完整代码

码源我已上传至gitee 有需要的可点击后方链接双向链表的增删查改码源

1.List.h

#pragma once         //防止头文件重复包含
#include<stdio.h>    //头文件
#include<stdlib.h>
#include<assert.h>
// 带头+双向+循环链表增删查改实现
//类型声明 
typedef int LTDataType;      //数据类型重命名
typedef struct ListNode      //结构体类型声明
{
  struct ListNode* prev;   //两头的指针变量 储存双向两旁结构体的地址
  LTDataType data;
  struct ListNode* next;
}ListNode;
// 创建返回双向链表的头结点.
ListNode* ListCreate();
// 双向链表的初始化
void ListInit(ListNode* phead);
// 创建返回新节点
ListNode* BuynewNode(LTDataType x);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表销毁
void ListDestory(ListNode* phead);

2.List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
// 创建返回链表的头结点.
ListNode* ListCreate() {
  ListNode* phead = (ListNode*)malloc(sizeof(ListNode));  //结构体指针phead 存的是malloc为新结构体开辟内存后 的返回的该新节点的指针 
  assert(malloc);
  return phead; //phead传的是phead指针的内容=head地址 =>返回结构体地址 
}
// 双向链表的初始化
void ListInit(ListNode* phead) {            //也用phead接受传过来的head的地址
  assert(phead);
  phead->prev = phead->next;
  phead->data = 0;                                             //加深对指针的理解
  phead->next = phead->prev;                                   //直接用head【记住：1. 名 直接用的是内容 明白这点 对于指针的理解就轻松很多】
                                   //2. -> 只能对指针使用 且不支持二级指针解引用*后得到一级指针的形式
                                     // （如：ListNode** pphead  **pphead->data (x)好像不行 去试一下 ） 【关于指针注意的点的讲解】
}
// 创建返回新节点
ListNode* BuynewNode(x) {
  ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
  newNode->data = x;
  return newNode;
}
// 双向链表尾插
void ListPushBack(ListNode* phead,LTDataType x) {
  ListNode* newNode = BuynewNode(x);             //1M的空间可创建出一千多万个指针变量
  ListNode* tail = phead->prev;                  //多创建指针变量 自己也标的看的清楚 增加代码的可读性
  tail->next = newNode;
  newNode->prev = tail;
  newNode->next = phead;
  phead->prev = newNode;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x) { 
  ListNode* newNode = BuynewNode(x);
  ListNode* first = phead->next;        //第一个节点
  newNode->next = first;
  first->prev = newNode;
  phead->next = newNode;
  newNode->prev = phead;
}
// 双向链表尾删
void ListPopBack(ListNode* phead) {
  assert(phead);
  assert(phead->next != phead);        //确保链表不为空，有东西可删，及时报错
  ListNode* tailPrev = phead->prev->prev;
  ListNode* tail = phead->prev;
  free(tail);
  tail = NULL;
  tailPrev->next = phead;
  phead->prev = tailPrev;
}
// 双向链表头删
void ListPopFront(ListNode* phead) {
  assert(phead);
  assert(phead->next != phead);    
  ListNode* newNext = phead->next->next;
  ListNode* Next = phead->next;           //新建指针变量 保存好要free掉的节点的地址
  free(Next);                             //就不用怕后续改变各节点之间的指针关系时把该节点的地址弄丢了
  Next = NULL;
  phead->next = newNext;
  newNext->prev = phead;
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) {
  ListNode* Head = phead->next;                       //设置两个指针变量，一个从头开始遍历，一个从后遍历
  ListNode* Back = phead->prev;
  while (Head!=Back) {
    if (Head->data = x)
      return Head;
    else if (Back->data = x)
      return Back;
    Head = Head->next;
    Back = Back->prev;
  }
  return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
  ListNode* posPrev = pos->prev;
  ListNode* newNode = BuynewNode(x);
  posPrev->next = newNode;
  newNode->prev = posPrev;
  newNode->next = pos;
  pos->prev = newNode;
}
// 双向链表删除pos位置的节点                 //若传过来的pos=phead->next  =>作头删作用
void ListErase(ListNode* pos) { 
  ListNode* posPrev = pos->prev;        //若传过来的pos=phead（由于双向链表具有循环的特性） =>作尾删作用
  ListNode* posNext = pos->next;
                                        //也正是由于双向链表具有循环的特性，即使链表中只有一个节点也能很好的运行
  posPrev->next = posNext;              //图解
  posNext->prev = posPrev;
  free(pos);
  pos = NULL;
}
//Erase函数以后 头删和尾删也可以这样写
// 双向链表尾删【ListErase版本】
void ListPopBack(ListNode* phead) {
  //assert(phead);
  //assert(phead->next != phead);
  //ListNode* tailPrev = phead->prev->prev;
  //ListNode* tail = phead->prev;
  //free(tail);
  //tail = NULL;
  //tailPrev->next = phead;
  //phead->prev = tailPrev;
  assert(phead);
  assert(phead->next != phead);     //确保链表不为空，有东西可删，及时报错
  ListErase(phead);
}
// 双向链表头删【ListErase版本】
void ListPopFront(ListNode* phead) {
  //assert(phead);
  //assert(phead->next != phead);
  //ListNode* newNext = phead->next->next;
  //ListNode* Next = phead->next;
  //free(Next);                             
  //Next = NULL;
  //phead->next = newNext;
  //newNext->prev = phead;
  assert(phead);
  assert(phead->next != phead);     //确保链表不为空，有东西可删，及时报错
  ListErase(phead->next);
}
// 双向链表打印  递归实现
void ListPrint(ListNode* phead) {
  assert(phead);
    ListNode* cur = phead->next;
  while (cur!=phead) {
  printf("%d <=>", cur->data);
  cur = cur->next;
  ListPrint(cur);
  }
  printf("\n");
}
// 双向链表打印  非递归实现
void ListPrint(ListNode* phead) {
  assert(phead);
  ListNode* cur = phead->next;
  while (cur!=phead) {
  cur = phead->next;
  printf("%d <=>", cur->data);
  }
}
// 双向链表销毁
void ListDestory(ListNode* phead) {
  ListNode* cur = phead->next;
  while (cur!=phead) {
  ListNode* curNext = cur->next;
  free(cur);
  cur = curNext;
  }
  free(phead);
  phead = NULL;
}

3.test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//测试ListPushBack 、ListPrint 的功能
void test1() {
  ListNode* phead = ListCreate();  //返回head的地址
  ListInit(phead);
  ListPushBack(phead,1);   //测试ListPushBack
  ListPushBack(phead, 2);
  ListPushBack(phead, 3);
  ListPrint(phead);   //测试ListPrint
}
void test2() {
  ListNode* phead = ListCreate();    //返回head的地址
  ListInit(phead);
  ListPushBack(phead, 1);
  ListPushBack(phead, 2);
  ListPushBack(phead, 3);
  ListPushBack(phead, 4);
  ListPushBack(phead, 5);
  ListPushBack(phead, 6);
  ListPrint(phead);
  ListNode* pos = ListFind(phead,3);    //测试ListFind
  ListErase(pos);     //测试ListErase
  ListPopFront(phead);   //测试ListPopFront
  ListPopBack(phead);   //测试ListPopBack
  ListPrint(phead);
  pos = ListFind(phead, 2);
  ListInsert(pos,8);
  ListPrint(phead);
}
//测试ListDestory
void test3() {
  ListNode* phead = ListCreate();    //返回head的地址
  ListInit(phead);
  ListPushBack(phead, 1);
  ListPushBack(phead, 2);
  ListPushBack(phead, 3);
  ListPushBack(phead, 4);
  ListPushBack(phead, 5);
  ListPushBack(phead, 6);
  ListPrint(phead);
  ListNode* pos = ListFind(phead, 3); 
  ListErase(pos);     
  ListPopFront(phead);   
  ListPopBack(phead);   
  ListPrint(phead);
  pos = ListFind(phead, 2);
  ListInsert(pos, 8);
  ListPrint(phead);
  ListDestory(phead);
}
int main() {
  test1();//测试ListPushBack 、ListPrint
  test2();//测试
  test3();//测试ListDestory
}```

【数据结构】双向链表的增删查改（C 代码实现）

前言