备案控制台
开发者社区 云计算 文章 正文

数据结构——双向链表的实现

2023-11-22 53
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构——双向链表的实现

一、双向链表的结构


注意：双向链表又称带头双向循环链表

这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严

谨，但是为了同学们更好的理解就直接称为单链表的头节点。

带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨 的”

“哨兵位”存在的意义： 遍历循环链表避免死循环。

双向链表每个节点储存一个有效数据+前驱指针+后继指针


二、. 双向链表的实现

2.1 创建&初始化

2.2.1  List.h

#pragma once
typedef struct ListNode
{
  int val;
  struct ListNode* next;
  struct  ListNode* prev;
}LTNode; 
//初始化
LTNode* LTInit();

2.2.2  List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
LTNode* LTInit()//哨兵位初始化
{
  LTNode* head = (LTNode*)malloc(sizeof(LTNode));
  head->val = -1;
  head->next = head->prev =head;
  return head;
}

2.2.3 text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{
  LTNode* head;
  head=LTInit();
  return 0;
}

代码运行测试：


2.2尾插&头插

分析：


尾插
1.往d3节点的后面插入数据叫做尾插  

2.往哨兵位head之前插入数据也叫尾插

 

头插

在哨兵位和头节点之间插入


2.2.1  List.h

//尾插
//1.往d3节点的后面插入数据叫做尾插    2.往哨兵位head之前插入数据也叫尾插
void LTPushBack(LTNode* head, int x);
//打印
void LTPrint(LTNode* head);
//头插
void LTPushFront(LTNode* head, int x);

2.2.2  List.c

//创建新节点
LTNode* Listbuynode(int x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  node->val = x;
  node->next = node->prev = NULL;
  return node;
}
void LTPushBack(LTNode* head, int x)
{
  LTNode* node = Listbuynode(x);
  //对新节点进行操作
  node->next = head;
  node->prev = head->prev;
  //对原来的尾节点和哨兵位进行操作
  head->prev->next = node;
  head->prev = node;
}
void LTPrint(LTNode* head)
{
  assert(head);
  LTNode* pcur = head->next;
  while (pcur != head)
  {
    printf("%d->", pcur->val);
    pcur = pcur->next;
  }
  printf("\n");
}
void LTPushFront(LTNode* head, int x)
{
  LTNode* node = Listbuynode(x);
  //对新节点进行操作
  node->next = head->next;
  node->prev = head;
  //对哨兵位和头节点进行操作
  head->next->prev = node;
  head->next = node;
}

2.2.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{
  LTNode* head;
  head=LTInit();
  LTPushBack(head, 1);
  LTPushBack(head, 2);
    LTPushBack(head, 3);
    LTPushFront(head,4);//4->1->2->3
  LTPrint(head);
  return 0;
}


2.3  头删&尾删

2.3.1  List.h

//尾删
void LTPopBack(LTNode* head);
//头删
void LTPopFront(LTNode* head);

2.3.2  List.c

void LTPopBack(LTNode* head)
{
  //链表为空不能删除
  assert(head);
  assert(head->next != head);
  //将尾节点进行保存
  LTNode* del = head->prev;
  //连接次尾节点和哨兵位
  del->prev->next = head;
  head->prev = del->prev;
  free(del);
  del = NULL;
}
void LTPopFront(LTNode* head)
{
  //链表为空不能删除
  assert(head);
  assert(head->next != head);
  //将头节点进行保存
  LTNode* del = head->next;
  //连接哨兵位和次头节点
  head->next = del->next;
  del->next->prev = head;
  free(del);
    del = NULL;
}

2.3.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{
  LTNode* head;
  head=LTInit();
  LTPushBack(head, 1);
  LTPushBack(head, 2);
  LTPushBack(head, 3);
  LTPushFront(head, 4);
  LTPrint(head);//4->1->2->3
  LTPopFront(head);
  LTPrint(head);//1->2->3
  LTPopBack(head);
  LTPrint(head);1->2
  return 0;
}


2.4  查找数据&在pos节点后插入数据&删除pos节点

2.4.1  List.h

//在pos位置之后插入数据
void LTInsert(LTNode* pos, int x);
//删除pos节点
void LTErase(LTNode* pos);
//查找数据
LTNode* LTFind(LTNode* head, int x);

2.4.2  List.c

void LTInsert(LTNode* pos, int x)
{
  assert(pos);
  LTNode* node = Listbuynode(x);
  //先处理新节点
  node->prev = pos;
  node->next = pos->next;
  //在处理前后节点
  pos->next = node;
  node->next->prev = node;
}
LTNode* LTFind(LTNode* head, int x)
{
  assert(head);
  assert(head->next!=head);
  LTNode* pcur = head->next;
  while (pcur != head)
  {
    if (pcur->val == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
  pos = NULL;
}

2.4.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{
  LTNode* head;
  head=LTInit();
  LTPushBack(head, 1);
  LTPushBack(head, 2);
  LTPushBack(head, 3);
    LTPushBack(head, 4);
  //LTPopBack(head);
  //LTPrint(head);
  //LTPopBack(head);
  LTNode* find = LTFind(head, 4);
  LTInsert(find, 11);
    LTPrint(head);//1->2->3->4->11
  LTErase(find);//1->2->3->11
  LTPrint(head);
  return 0;
}


2.5  销毁


若销毁接口用二级指针接受，传哨兵位指针的地址，那么可以改变哨兵位（指针指向）,使哨兵位指向NULL;


若销毁接口用一级指针接受，传一级指针（哨兵位指针），传过去的形参（是指针存储的地址），不能够改变指针的指向，在对形参操作，可以释放哨兵位指向的地址空间（形参的值为空间地址），但是不能改变实参指针的指向（实参依然指向原来被释放的地址空间），需要手动将实参置为NULL.


简而言之，若需要改变一级指针指向，需要传二级指针。


前面都是用一级指针传参，为了保持接口的一致性，我们用一级指针传参


2.5.1  List.h

1. //销毁
2. void LTDestroy(LTNode* phead);

2.5.2  List.c

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

2.5.3  text.c 

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdio.h>
int main()
{
  LTNode* head;
  head=LTInit();
  LTPushBack(head, 1);
  LTPushBack(head, 2);
  LTPushBack(head, 3);
  LTPushFront(head, 4);
  /*LTPrint(head);
  LTPopFront(head);*/
  LTPrint(head);
  //LTPopBack(head);
  //LTPrint(head);
  //LTPopBack(head);
  LTNode* find = LTFind(head, 4);
  /*LTInsert(find, 11);*/
  LTErase(find);
  LTPrint(head);
  LTDestroy(head);
  head = NULL;
  return 0;
}


2.6  完整代码

2.6.1  List.h

#pragma once
typedef struct ListNode
{
  int val;
  struct ListNode* next;
  struct  ListNode* prev;
}LTNode; 
//初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//尾插
//1.往d3节点的后面插入数据叫做尾插    2.往哨兵位head之前插入数据也叫尾插
void LTPushBack(LTNode* head, int x);
//打印
void LTPrint(LTNode* head);
//头插
void LTPushFront(LTNode* head, int x);
//尾删
void LTPopBack(LTNode* head);
//头删
void LTPopFront(LTNode* head);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, int x);
//删除pos节点
void LTErase(LTNode* pos);
//查找数据
LTNode* LTFind(LTNode* head, int x);


2.6.2  List.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
LTNode* LTInit()//哨兵位初始化
{
  LTNode* head = (LTNode*)malloc(sizeof(LTNode));
  head->val = -1;
  head->next = head->prev =head;
  return head;
}
//创建新节点
LTNode* Listbuynode(int x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  node->val = x;
  node->next = node->prev = NULL;
  return node;
}
void LTPushBack(LTNode* head, int x)
{
  LTNode* node = Listbuynode(x);
  //对新节点进行操作
  node->next = head;
  node->prev = head->prev;
  //对原来的尾节点和哨兵位进行操作
  head->prev->next = node;
  head->prev = node;
}
void LTPrint(LTNode* head)
{
  assert(head);
  LTNode* pcur = head->next;
  while (pcur != head)
  {
    printf("%d->", pcur->val);
    pcur = pcur->next;
  }
  printf("\n");
}
void LTPushFront(LTNode* head, int x)
{
  LTNode* node = Listbuynode(x);
  //对新节点进行操作
  node->next = head->next;
  node->prev = head;
  //对哨兵位和头节点进行操作
  head->next->prev = node;
  head->next = node;
}
void LTPopBack(LTNode* head)
{
  //链表为空不能删除
  assert(head);
  assert(head->next != head);
  //将尾节点进行保存
  LTNode* del = head->prev;
  //连接次尾节点和哨兵位
  del->prev->next = head;
  head->prev = del->prev;
  free(del);
  del = NULL;
}
void LTPopFront(LTNode* head)
{
  //链表为空不能删除
  assert(head);
  assert(head->next != head);
  //将头节点进行保存
  LTNode* del = head->next;
  //连接哨兵位和次头节点
  head->next = del->next;
  del->next->prev = head;
  free(del);
    del = NULL;
}
void LTInsert(LTNode* pos, int x)
{
  assert(pos);
  LTNode* node = Listbuynode(x);
  //先处理新节点
  node->prev = pos;
  node->next = pos->next;
  //在处理前后节点
  pos->next = node;
  node->next->prev = node;
}
LTNode* LTFind(LTNode* head, int x)
{
  assert(head);
  assert(head->next!=head);
  LTNode* pcur = head->next;
  while (pcur != head)
  {
    if (pcur->val == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
  pos = NULL;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  LTNode* next = pcur->next;
  while (pcur != phead)
  {
    free(pcur);
    pcur = next;
    next = next->next;
  }
  free(phead);
  phead = NULL;
}

2.6.3  text.c

#define _CRT_SECURE_NO_WARNINGS
#include"List.h"
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
LTNode* LTInit()//哨兵位初始化
{
  LTNode* head = (LTNode*)malloc(sizeof(LTNode));
  head->val = -1;
  head->next = head->prev =head;
  return head;
}
//创建新节点
LTNode* Listbuynode(int x)
{
  LTNode* node = (LTNode*)malloc(sizeof(LTNode));
  node->val = x;
  node->next = node->prev = NULL;
  return node;
}
void LTPushBack(LTNode* head, int x)
{
  LTNode* node = Listbuynode(x);
  //对新节点进行操作
  node->next = head;
  node->prev = head->prev;
  //对原来的尾节点和哨兵位进行操作
  head->prev->next = node;
  head->prev = node;
}
void LTPrint(LTNode* head)
{
  assert(head);
  LTNode* pcur = head->next;
  while (pcur != head)
  {
    printf("%d->", pcur->val);
    pcur = pcur->next;
  }
  printf("\n");
}
void LTPushFront(LTNode* head, int x)
{
  LTNode* node = Listbuynode(x);
  //对新节点进行操作
  node->next = head->next;
  node->prev = head;
  //对哨兵位和头节点进行操作
  head->next->prev = node;
  head->next = node;
}
void LTPopBack(LTNode* head)
{
  //链表为空不能删除
  assert(head);
  assert(head->next != head);
  //将尾节点进行保存
  LTNode* del = head->prev;
  //连接次尾节点和哨兵位
  del->prev->next = head;
  head->prev = del->prev;
  free(del);
  del = NULL;
}
void LTPopFront(LTNode* head)
{
  //链表为空不能删除
  assert(head);
  assert(head->next != head);
  //将头节点进行保存
  LTNode* del = head->next;
  //连接哨兵位和次头节点
  head->next = del->next;
  del->next->prev = head;
  free(del);
    del = NULL;
}
void LTInsert(LTNode* pos, int x)
{
  assert(pos);
  LTNode* node = Listbuynode(x);
  //先处理新节点
  node->prev = pos;
  node->next = pos->next;
  //在处理前后节点
  pos->next = node;
  node->next->prev = node;
}
LTNode* LTFind(LTNode* head, int x)
{
  assert(head);
  assert(head->next!=head);
  LTNode* pcur = head->next;
  while (pcur != head)
  {
    if (pcur->val == x)
    {
      return pcur;
    }
    pcur = pcur->next;
  }
  return NULL;
}
void LTErase(LTNode* pos)
{
  assert(pos);
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  free(pos);
  pos = NULL;
}
void LTDestroy(LTNode* phead)
{
  assert(phead);
  LTNode* pcur = phead->next;
  LTNode* next = pcur->next;
  while (pcur != phead)
  {
    free(pcur);
    pcur = next;
    next = next->next;
  }
  free(phead);
  phead = NULL;
}


三、顺序表和双向链表的优缺点分析


不同点

 顺序表

链表（单链表）

存储空间上

 物理上一定连续

逻辑上连续，但物理上不⼀定连续

随机访问

⽀持O(1）

 不支持，O(n)

任意位置插⼊或者删除元素

可能需要搬移元素，效率低O(N)

只需修改指针指向
插入

动态顺序表，空间不够时需要扩容

没有容量的概念

应⽤场景

元素⾼效存储+频繁访问

任意位置插⼊和删除频繁
文章标签：
存储
关键词：
数据结构链表
数据结构双向链表
日刷百题
目录
相关文章
悲伤小伞
|
5天前
|
存储
数据结构链表详解(不仅顺序表可以，我链表也可以)
数据结构链表详解(不仅顺序表可以，我链表也可以)
悲伤小伞
12 0
老秦包你会
|
6天前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
老秦包你会
22 0
Bigcrab__
|
6天前
|
存储 算法 Java
数据结构与算法 数组和链表
数据结构与算法 数组和链表
Bigcrab__
12 0
菜菜的后端私房菜
|
6天前
|
存储 Java
深入浅出数据结构之链表
深入浅出数据结构之链表
菜菜的后端私房菜
9 0
天玑y
|
6天前
|
C++
数据结构（双链表
数据结构（双链表
天玑y
11 1
小蜗牛~向前冲
|
6天前
|
存储 缓存
[数据结构]~双向+循环链表从(0~1）
[数据结构]~双向+循环链表从(0~1）
小蜗牛~向前冲
18 2
老秦包你会
|
6天前
|
存储
数据结构第三课 -----线性表之双向链表
数据结构第三课 -----线性表之双向链表
老秦包你会
12 0
小谢在努力
|
6天前
|
存储 Java
数据结构奇妙旅程之顺序表和链表
数据结构奇妙旅程之顺序表和链表
小谢在努力
6 0
颦颦Admin@123
|
6天前
|
存储 C语言
数据结构基础：双链表结构、实现
数据结构基础：双链表结构、实现
颦颦Admin@123
16 0
颦颦Admin@123
|
6天前
|
存储
数据结构基础：一篇文章教你单链表（头插，尾插，查找，头删等的解析和代码）
数据结构基础：一篇文章教你单链表（头插，尾插，查找，头删等的解析和代码）
颦颦Admin@123
17 0