首页 > 其他分享 >单双链表(数组模拟)笔记

单双链表(数组模拟)笔记

时间:2024-11-02 21:21:28浏览次数:4  
标签:right idx int 笔记 next 数组 双链 节点 left

单双链表(数组模拟)笔记

如题,我们要使用数组来模拟链表这个数据结构

区别于传统的结构体链表(动态链表):

struct node
{
	int value;
	struct node* next;//指向下一个节点的指针
}user_define_name;//调用链表的别称

数组模拟链表(静态链表)的速度更快,但是对于空间的优化不如动态链表

单链表的实现:

首先需要两个数组来存储节点的数据值和指向下一个节点的指针值,头节点head,以及一个计数器来记录总共的节点数

int head value[N],next[N],idx;//N表示链表的最大长度

然后定义init初始化函数:

void init() {
	head = -1;//初始化头节点指向-1
	idx = 0;
}

定义add_to_head添加节点到头节点后的函数:

void add_to_head(int x) {
	value[idx] = x;
	next[idx] = head;
	head = idx;
	idx++;
}

定义add在第k个节点后添加一个节点的函数:

void add(int k, int x) {
	value[idx] = x;
	next[idx] = next[k];
	next[k] = idx;
	idx++;
}

定义remove删除第k个节点后一个节点的函数:

void remove(int k) {
	next[k] = next[next[k]];
}

把第k个节点指向的下一个节点的值next[next[k]]赋给next[k]

即把第k个节点指向的下一个节点定位到下一个节点指向的下一个节点

形如:

a -> b -> c 变为 a -> c

定义inquire查找第k个节点后一个节点的值的函数:

int inquire(int k) {
	if (next[k] != -1) return value[next[k]];//当第k个节点不是尾节点时返回下一个节点的值
	else return -1;//是尾节点返回-1
}

缺点:单链表只能定位某个节点后的一个节点,无法做到双端查找,可以引入双链表解决该问题

改进到双链表的实现:

在单链表的基础上增加我们需要额外的一个数组来存储上一个节点的位置:

int value[N],left[N],right[N],idx;

init初始化函数的改进:

选用01节点作为头节点和尾节点,初始化时,两者相互引索

void init() {
	right[0] = 1;
	left[1] = 0;
	idx = 2;
}

add第k个节点后添加一个节点的函数的改进:

void add(int k, int x) {
	value[idx] = x;
	
	right[idx] = right[k];
	left[idx] = k;
	
	left[right[k]] = idx;
	right[k] = idx;
	
	idx++;
}

先把idx节点左右指针指向kright[k],即把idx插在中间

然后先让idx的右节点的左指针left[right[k]]指向idx,再把idx 的左节点的右指针right[k]指向idx

最后idx++

若是想在第k个节点前添加一个节点,把k改为传入left[k],即可实现

remove删除第k个节点后一个节点的函数的改进:

 void remove(int k) {
	right[k] = right[right[k]];
	left[right[right[k]]] = k;
}

可以看出这步操作非常的复杂,所以可以重新定义一个 p_remove删除指定节点的函数

void p_remove(int k) {
	right[left[k]] = right[k];
	left[right[k]] = left[k];
}

指定节点的右节点左指针指向指定节点的左节点指定节点的左节点右指针指向指定节点的右节点

  • 使用inquire函数查找指定节点的左右节点值,与add函数操作类似,这里不做赘述

标签:right,idx,int,笔记,next,数组,双链,节点,left
From: https://www.cnblogs.com/dianman/p/18522465

相关文章

  • 【复盘笔记】25国考一期_套题5
    目录一、言语理解1.选词填空2.片段阅读二、判断推理1.图形推理2.定义判断3.类比推理4.逻辑推理三、资料分析【笔记说明】:所用试卷为花s老师的套题班试卷,个别过于简单的题目未做解析。该笔记为个人学习自用,顺便分享,希望对您也有所帮助。若转载,请说明出处。一、言语......
  • 34. 在排序数组中查找元素的第一个位置和最后一个位置
    题目参考了y总讲的这题789.数的范围自己是这样写的;classSolution{public:vector<int>searchRange(vector<int>&nums,inttarget){vector<int>result(2,-1);intl=0,r=nums.size()-1;while(l<r){......
  • C++ 创建动态二维数组
    方法一:使用vector容器1.创建整数型二维数组先建列,再建行,先创建一个包含m个元素的向量a,再创建二维向量arr,通过push_back将一维向量作为行添加到二维向量中#include<iostream>#include<vector>usingnamespacestd;intmain(){ //创建一个包含m个元素,每个元素初始值为0......
  • Vue学习笔记(十七)
    4.路由4.1.【对路由的理解】4.2.【基本切换效果】Vue3中要使用vue-router的最新版本,目前是4版本。路由配置文件代码如下:import{createRouter,createWebHistory}from'vue-router'importHomefrom'@/pages/Home.vue'importNewsfrom'@/pages/News.vue'im......
  • Vue学习笔记(十八)
    4.8.【路由传参】query参数传递参数<!--跳转并携带query参数(to的字符串写法)--><router-linkto="/news/detail?a=1&b=2&content=欢迎你"> 跳转</router-link> <!--跳转并携带query参数(to的对象写法)--><RouterLink:to="{//name:'x......
  • Java 继承机制的笔记 1
    Java继承机制的笔记_1笔记的来源:CS61B-2024春季的课程课程主要内容:数据结构与算法分析课程运用语言:Java这个课有6个Homework,10个Lab,9个Project。其中第一个project是一个完整的2024游戏的实现,很有意思。此文章对应的是课程8-9节的内容。由于内容较多......
  • 统计学习方法笔记
    统计学习方法1.3统计学习方法的三要素1.3.1模型好,为什么要从1.3开始呢,因为看前面的课,我还没有用到这个软件。方法=模型+策略+算法模型有好多个,试试策略:按照什么样的准则去选取模型比如说看预测值和真实值有多大,或者损失函数最小等算法即怎样去实现去寻找这个模型决策......
  • 《程序员的修炼之道——从小工到专家》阅读笔记1
    这里面针对程序员,反复提到一个形容词,就是“注重实效”。根据书中所讲,结合我的理解,我认为注重时效这个词主要体现在责任上,对自己负责,对自己的代码负责,对自己的代码中的错误负责。“最大的弱点就是害怕暴露弱点”,我非常认同这句话,要坦然面对自己的错误其实并不是一件容易的事情,不仅......
  • 机器学习入门基础----白板推导笔记输出
    为了能够建立知识学习后输出体系,开设这个系列,旨在通过记录博客输出学习到的机器学习内容,笔者所学为B站upshuhuai008白板推导系列,记录可能比不上原创,也可能有没理解不严谨的地方,请善意指正。感兴趣的可以去看UP白板-------------------------------------------------------------......
  • 数组篇-代码随想录
    数组篇跳-二分查找-704-力扣classSolution{publicintsearch(int[]nums,inttarget){if(nums==null||nums.length==0)return-1;if(target<nums[0]||target>nums[nums.length-1])return-1;intleft=0,......