【数据结构和算法】使用数组的结构实现链表(单向或双向)

简介: 【数据结构和算法】使用数组的结构实现链表(单向或双向)

前言

你之前实现链表的形式,是不是这一种结构来实现

typedef struct ListNode {
  int data;
  struct ListNode* next;
}List;

但是我如果告诉你只需要这样两个数组就能模拟实现链表,你相信吗!!!

head  表示头节点
e[N]  表示存储结点数值的数组
ne[N] 表示结点的下一个结点的位置
idx   表示当前存储元素的位置   当前存储到哪里了就是

接下来我们来实现单链表,以及双向链表

一、用数组结构的好处

我们在日常学习的过程中,老师教授给我们的都是以结构体的形式实现的链表,但是呢,比如我们要创建100000个结点,这样的话, 用结构体的话,时间太长,空间太大,反观数组,就显得很有优势了。

1.在搞算法的时候,使用数组的形式去模拟链表,会使得运算速度变快,更加适合写算法,打比赛的小朋友。

2.在笔试的适合,会更快的创建实现链表的基础功能,进行插入删除元素,并根据下标直接找到所需元素等

我们在来了解一下数组和链表的优缺点吧

1.数组的优缺点

认识数组:

数组是一种线性结构,存储的空间是内存连续的(物理连续),每当创建一个数组的时候,就必须先申请好一段指定大小的空间。(一次申请即可指定大小的空间)

优点:

由于内存连续这一特征,数组的访问速度很快,直到索引下标之后,可以实现O(1)的时间复杂度的访问。

缺点:

1.在任意位置删除和插入操作的时候,就会涉及到部分元素的移动,这样的话我们对于数组的任意位置的删除和插入的操作的时间复杂度为O(n)。

比如:

1>在i点后面插入数据,那么就需要i+1位置以及之后的元素,整体后移一位(for循环操作),然后再将插入的数据放在i+1的位置上

2>在i点之后删除元素,那么就需要,将i+1以及之后的元素,整体前移一位,总元素个数减一

以上是数组的优缺点,可以快速访问,达到O(1),但是在任意删除和插入元素的时候,会耗时间,达到O(n)。

2.链表的优缺点

认识链表

1.链表也是一种线性结构,但是他存储空间是不连续的(物理不连续,逻辑连续),链表的长度是不确定且支持动态扩展的。每次插入元素的时候,都需要进行申请新节点,然后赋值,插入链表中。

优点:

在插入数据或者删除数据的时候,只需要改变指针的指向即可,不需要类似于数组那样部分整体移动,整个过程不涉及元素的迁移,因此链表的插入和删除操作,时间复杂度为O(1)

缺点:

在查找任意位置的结点的数值域的时候,需要遍历,时间复杂度为O(n)

但是我们在任意位置插入或者删除元素的时候,需要查找这个指定的元素的结点位置,所以综合起来,链表的插入和删除仍为O(n)。

3.总结

无论数组还是链表,查找的时间复杂度都是O(n),查找都要挨个遍历,直到找到满足的条件的数据为止,所以对于链表,如果没有给定,指针的地址,只是要插入删除第N位元素的时候,加上查找,综合起来时间复杂度为O(n)。

但是我们如果以数组的形式来实现链表,那么插入删除指定元素位置的时候,是不是就更加简便了呢,在第N位插入删除元素的时候,直接以O(1)的时间复杂度找到该位置结点,然后再由于链表的删除插入都是O(1)的,所以整个删除或插入操作,综合时间复杂度为O(1),比普通链表快很多。

二、用数组实现链表

1.认识构造、初始化

我们先由图示了解初始化的时候的准备工作

我们使用c++会更加方便理解,因为c++支持用变量来定义数组

初始化代码:

//使用c++更简单,先用c++的形式实现
const int N = 100010;
int head, e[N], ne[N], idx; //全局变量
void init() {
  head = -1;
  idx = 0;//进行初始化的操作,idx为当前链表中(数组)最后一个元素(末尾),下标位置
}

2.将x插入到头结点

就是所谓的链表中的头部插入

图示:

实际上和普通链表的头插一样,只是流程next指针换成了ne[N]数组的形式,记录的是下一结点的数值。

代码如下:

void add_to_head(int x) {
  e[idx] = x;//将x数值存入到e[]数组中
  ne[idx] = ne[head];//将idx新插入的结点的下一个位置存储到ne[idx]中  ,全局变量 ne以及n数组初始化为0
  head = idx;
  idx++;
}

3.将x插入到第k次插入数值之后的位置

图示:

我们要说明一个问题,ne[N]这个数组存放的数值,是不需要管的,因为不管是add还是remove,插入还是删除结点,都不会重复,实际上,e[ne[head]]是得到head结点下一个结点的数值,ne[]数组只作为,下标使用。

我们是在第k次插入的之后的位置插入x,但是与此同时 ,此时的idx成为新的第k次插入数据下标,也就是说,再次对第k次插入数值之后的位置插入的x,实际上是在上一次的新插入的结点之后进行插入

图示:

代码如下:

//在第k个插入的数字之后插入数据
void add(int k, int x) {
  e[idx] = x;
  ne[idx] = ne[k];
  ne[k] = idx;
  idx++;
}

4.删除第k次插入的结点

//将下标为k的点后面的点删掉
void remove(int k, int ne[]) {
  ne[k] = ne[ne[k]];//表示k的下一个位置(ne)为下一个位置的下一个位置,这样跳过了原来的ne[k]结点
}//使用的时候应该是  删除的是k之后的点

直接跳过即可,和链表类似

三、完整代码演示

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
const int N = 100010;
int n, e[N], ne[N], idx, head;
//初始化
void init() {
  head = -1;
  idx = 0;
}
//头插
void add_to_head(int x) {
  e[idx] = x;
  ne[idx] = head;
  head = idx;
  idx++;
}
//在第k个插入的数字之后插入数据
void add(int k, int x) {
  e[idx] = x;
  ne[idx] = ne[k];
  ne[k] = idx;
  idx++;
}
//删除第k的插入的数据
void remove(int k) {
  ne[k] = ne[ne[k]];
}
int main()
{
  init();
  add_to_head(1);
  add_to_head(2);
  add_to_head(3);
  add_to_head(4);
  add_to_head(5);
  add(2-1, 10);
  add(2-1, 2);
  add(2-1, 3);
  add(2-1, 4);
  add(2-1, 5);
  add_to_head(50);
  for (int i = head; i != -1; i=ne[i]) {
    printf("%d ", e[i]);
  }
  printf("\n");
  for (int i = head; i != -1; i = ne[i]) {
    printf("%d ", ne[i]);
  }
  return 0;
}

四、数组实现双向链表

1.初始化

//初始化
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
  //0表示为左端点,1表示为右端点
  r[0] = 1;
  l[1] = 0;
  idx = 2;//从2开始
}

我们设定,用e[N]数组来记录数据,在用 l[N] 、 r[N]数组表示结点的左右指针,一开始,0表示为左端点,1表示右端点,然后r、l两个数组记录,数值下标从2开始

e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点

2.在第k次插入的点的右边插入x

//在第k次插入的点的右边插入x;
void add(int k, int x) {
  e[idx] = x;//数值x给当前idx位置的e数组存储
  r[idx] = r[k];//将新节点的左右两端分别连接k的后一个结点r[k]和k本身
  l[idx] = k;
  l[r[k]] = idx;//然后将k的右端点的左端点连接idx
  r[k] = idx;//最后将k的右端点连接idx
}

3.删除第k个点

//删除第k个点
void remove(int k) {
  //就是将k的左端点和右端点相互连接
  l[r[k]] = l[k];
  r[l[k]] = r[k];
}

五、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<assert.h>
//使用数组的形式实现双向链表
//e[N]  表示存储结点的数值
//l[N]  表示当前结点的左结点位置
//r[N]  表示当前结点的右节点位置
//idx 表示当前结点存储的位置
//初始化
int m;
const int N = 100010;
int e[N], l[N], r[N], idx;
void init() {
  //0表示为左端点,1表示为右端点
  r[0] = 1;
  l[1] = 0;
  idx = 2;//从2开始
}
//在第k次插入的点的右边插入x;
void add(int k, int x) {
  e[idx] = x;//数值x给当前idx位置的e数组存储
  r[idx] = r[k];//将新节点的左右两端分别连接k的后一个结点r[k]和k本身
  l[idx] = k;
  l[r[k]] = idx;//然后将k的右端点的左端点连接idx
  r[k] = idx;//最后将k的右端点连接idx
}
//删除第k个点
void remove(int k) {
  //就是将k的左端点和右端点相互连接
  l[r[k]] = l[k];
  r[l[k]] = r[k];
}


目录
打赏
0
0
0
0
0
分享
相关文章
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
104 10
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
123 3
 算法系列之数据结构-Huffman树
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
76 0
|
4月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
112 22
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
145 30
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
207 25
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容展示了基于GA(遗传算法)优化的256QAM概率星座整形(PCS)技术的研究与实现。通过Matlab仿真,分析了优化前后星座图和误码率(BER)的变化。256QAM采用非均匀概率分布(Maxwell-Boltzman分布)降低外圈星座点出现频率,减小平均功率并增加最小欧氏距离,从而提升传输性能。GA算法以BER为适应度函数,搜索最优整形参数v,显著降低误码率。核心程序实现了GA优化过程,包括种群初始化、选择、交叉、变异等步骤,并绘制了优化曲线。此研究有助于提高频谱效率和传输灵活性,适用于不同信道环境。
49 10

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问