当前位置： 首页 > web >正文

双向链表的实现

web 2025/7/4 8:11:26

目录

一、双向链表的结构

二、双向链表的实现

2.1 双向链表的初始化LTInit

2.2 双向链表的打印LTPrint

2.3 双向链表的判空LTEmpty

2.4 尾插LTPushBack

2.5 尾删LTPopBack

2.6 头插LTPushFront

2.7 头删LTPopFront

2.8 查找LTFind

2.9 插入LTInsert

2.10 删除LTErase

2.11 销毁LTDestroy

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

四、代码

4.1 ListNode.h

4.2 ListNode.c

4.3 test.c

一、双向链表的结构

双向链表的结构如下图所示：

二、双向链表的实现

2.1 双向链表的初始化LTInit

实现代码如下：

LTNode* BuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->next = newnode;newnode->prev = newnode;newnode->data = x;return newnode;
}
LTNode* LTInit() {return BuyNode(0);
}

2.2 双向链表的打印LTPrint

实现代码如下：

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

2.3 双向链表的判空LTEmpty

实现代码如下：

bool LTEmpty(LTNode* phead) {if (phead->next == phead) {return true;}else {return false;}
}

2.4 尾插LTPushBack

实现代码如下：

LTNode* BuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->next = newnode;newnode->prev = newnode;newnode->data = x;return newnode;
}
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = BuyNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

2.5 尾删LTPopBack

实现代码如下：

void LTPopBack(LTNode* phead)
{assert(phead);assert(LTEmpty(phead) != true);LTNode* tail = phead->prev;LTNode* pretail = tail->prev;pretail->next = phead;phead->prev = pretail;free(tail);
}

2.6 头插LTPushFront

实现代码如下：

LTNode* BuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->next = newnode;newnode->prev = newnode;newnode->data = x;return newnode;
}
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = BuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next = newnode;newnode->next->prev = newnode;
}

2.7 头删LTPopFront

实现代码如下：

void LTPopFront(LTNode* phead) {assert(phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);
}

2.8 查找LTFind

实现代码如下：

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

2.9 插入LTInsert

实现代码如下：

void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* newnode = BuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next = newnode;newnode->next->prev = newnode;}

2.10 删除LTErase

实现代码如下：

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

2.11 销毁LTDestroy

实现代码如下：

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

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

不同点顺序表链表（单链表）
存储空间上物理上⼀定连续逻辑上连续，但物理上不⼀定连续
随机访问⽀持O(1)不⽀持：O(N)
任意位置插⼊或者删除元素可能需要搬移元素，效率低O(N)
只需修改指针指向
插⼊
动态顺序表，空间不够时需要扩容
没有容量的概念
应⽤场景元素⾼效存储+频繁访问任意位置插⼊和删除频繁

四、代码

4.1 ListNode.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;LTDataType data;struct ListNode* next;
}LTNode;//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
LTNode* LTFind(LTNode* phead, LTDataType x);

4.2 ListNode.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"ListNode.h"
LTNode* BuyNode(LTDataType x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL) {perror("BuyNode()::malloc");exit(1);}newnode->next = newnode;newnode->prev = newnode;newnode->data = x;return newnode;
}
LTNode* LTInit() {return BuyNode(0);
}
void LTDestroy(LTNode* phead) {assert(phead);LTNode* cur = phead->next;while (cur!=phead) {LTNode* next = cur->next;free(cur);cur = next;}phead->next = phead;phead->prev = phead;
}
void LTPrint(LTNode* phead) {assert(phead);LTNode* cur = phead->next;while (cur != phead) {printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}
bool LTEmpty(LTNode* phead) {if (phead->next == phead) {return true;}else {return false;}
}void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = BuyNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}
void LTPopBack(LTNode* phead)
{assert(phead);assert(LTEmpty(phead) != true);LTNode* tail = phead->prev;LTNode* pretail = tail->prev;pretail->next = phead;phead->prev = pretail;free(tail);
}void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode = BuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next = newnode;newnode->next->prev = newnode;
}
void LTPopFront(LTNode* phead) {assert(phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);
}
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* cur = phead->next;while (cur != phead) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* newnode = BuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next = newnode;newnode->next->prev = newnode;}
void LTErase(LTNode* pos) {assert(pos);LTNode* next = pos->next;LTNode* prev = pos->prev;next->prev = prev;prev->next = next;free(pos);
}

4.3 test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"ListNode.h"
void test01()//测试尾插
{LTNode* phead = LTInit();LTPushBack(phead, 1);LTPushBack(phead, 2);LTPushBack(phead, 3);LTPushBack(phead, 4);LTPrint(phead);LTDestroy(phead);
}
void test02()//测试尾删
{LTNode* phead = LTInit();LTPushBack(phead, 1);LTPushBack(phead, 2);LTPushBack(phead, 3);LTPushBack(phead, 4);LTPrint(phead);//1 2 3 4LTPopBack(phead);LTPrint(phead);//1 2 3LTPopBack(phead);LTPrint(phead);//1 2LTPopBack(phead);LTPrint(phead);//1LTPopBack(phead);LTPrint(phead);//NULLLTDestroy(phead);}
void test03()//测试头插
{LTNode* phead = LTInit();LTPushFront(phead, 1);LTPushFront(phead, 2);LTPushFront(phead, 3);LTPushFront(phead, 4);LTPrint(phead);//4 3 2 1}
void test04()//测试头删
{LTNode* phead = LTInit();LTPushFront(phead, 1);LTPushFront(phead, 2);LTPushFront(phead, 3);LTPushFront(phead, 4);LTPrint(phead);//4 3 2 1LTPopFront(phead);LTPrint(phead);LTPopFront(phead);LTPrint(phead);LTPopFront(phead);LTPrint(phead);LTPopFront(phead);LTPrint(phead);
}
void tect05()//测试查找
{LTNode* phead = LTInit();LTPushFront(phead, 1);LTPushFront(phead, 2);LTPushFront(phead, 3);LTPushFront(phead, 4);LTNode* ret = LTFind(phead, 4);if (ret == NULL) {printf("找不到\n");}else {printf("找到了\n");}ret = LTFind(phead, 9);if (ret == NULL) {printf("找不到\n");}else {printf("找到了\n");}}
void test06()//测试插入
{LTNode* phead = LTInit();LTPushFront(phead, 1);LTPushFront(phead, 2);LTPushFront(phead, 3);LTPushFront(phead, 4);LTNode* ret = LTFind(phead, 4);LTInsert(ret, 99);LTPrint(phead);ret = LTFind(phead, 1);LTInsert(ret, 88);LTPrint(phead);ret = LTFind(phead, 3);LTInsert(ret, 77);LTPrint(phead);}
void test07()//测试删除
{LTNode* phead = LTInit();LTPushFront(phead, 1);LTPushFront(phead, 2);LTPushFront(phead, 3);LTPushFront(phead, 4);LTNode* ret = LTFind(phead, 4);LTErase(ret);LTPrint(phead);ret = LTFind(phead, 3);LTErase(ret);LTPrint(phead);ret = LTFind(phead, 2);LTErase(ret);LTPrint(phead);ret = LTFind(phead, 1);LTErase(ret);LTPrint(phead);}
int main() {//test01();//测试尾插//test02();//测试尾删//test03();//测试头插//test04();//测试头删//tect05();//测试查找、//test06();//测试插入//test07();//测试删除return 0;
}

http://www.xdnf.cn/news/14894.html

相关文章：

  • 深度剖析数据降维，PCA、LDA、NMF、LLE主流数据降维算法原理与代码实践
  • 分布式部署下如何做接口防抖---使用分布式锁
  • 站在 Java 程序员的角度如何学习和使用 AI？从 MVC 到智能体，范式变了！
  • 清除浮动/避开margin折叠：前端CSS中BFC的特点与限制
  • springMvc的简单使用:要求在浏览器发起请求，由springMVC接受请求并响应，将个人简历信息展示到浏览器
  • pdf 合并 python实现（已解决）
  • springboot切面编程
  • 【Java面试】RocketMQ的设计原理
  • 【数字后端】- tcbn28hpcplusbwp30p140，标准单元库命名含义
  • 按月设置索引名的完整指南：Elasticsearch日期索引实践
  • 嵌入式软件面经（四）Q：请说明在 ILP32、LP64 与 LLP64 三种数据模型下，常见基本类型及指针的 sizeof 值差异，并简要解释其原因
  • 提示技术系列——程序辅助语言模型
  • HCIA-实现VLAN间通信
  • 智能物流革命：Spring Boot+AI实现最优配送路径规划
  • 红黑树：高效平衡的秘密
  • Spring生态在Java开发
  • Android Native 之 init初始化selinux机制
  • 【Note】《深入理解Linux内核》 Chapter 5 ：内存地址的表示——Linux虚拟内存体系结构详解
  • 【RHCSA-Linux考试题目笔记（自用）】servera的题目
  • mac Maven配置报错The JAVA_HOME environment variable is not defined correctly的解决方法
  • 「ECG信号处理——（20）基于心电和呼吸的因果分析模型」2025年7月2日
  • 【Python】Python / PyCharm 虚拟环境详搭建与使用详解
  • U+平台配置免密登录、安装Hadoop配置集群、Spark配置
  • FIRST携手Fortinet推出全新CORE计划，致力于提升全球网络能力
  • jQuery EasyUI 安装使用教程
  • [Python 基础课程]数字
  • 【学习笔记】Python中主函数调用的方式
  • AngularJS 安装使用教程
  • kubernetes pod调度基础
  • Ubuntu系统开发板借助windows中转上网