首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

数据结构-静态链表及其插入删除操作

什么是静态链表 我们平常提及的链表一般指的是动态链表,是使用指针将一个一个的结点连起来,除了动态链表之外,还有静态链表,这种链表用数组来描述,主要为了解决没有指针或者不用指针的情况下具备链表插入删除操作便捷的特性...静态链表中有一些专属的概念,先贴上图: ?...至此,静态链表就构建完了。...静态链表插入操作 从上面的图可以看到,其实数组的最后一个元素的cur存的是一般都是1,因为在使用元素构建链表时从第二个元素开始顺序插入,而插入的位置在哪,其实是由cur决定的,都不是顺序存储中由位置决定...静态链表的删除操作 删除操作是一样的,在插入中,插入一个元素影响了使用链和备用链。那么删除一个元素的话也会同时影响这两个链。 ?

1.2K90

数据结构静态链表

数据结构静态链表 静态链表 用数组的方式实现的链表 优点 增,删操作不需要移动大量元素 缺点 不能随机存取 只能由头结点开始依次往后查找 容量固定不变 c代码实现 获取最后一个结点的下标以及获取第一个空闲节点的位置...size=i; break; } } } return size; } 初始化静态链表...next=-2只是为了做一个标记,代表该空间未被占用 //初始化一个静态链表 void initList(StaticList *list) { (*list)[0]=createStart(...这边对空节点进行标记,代表这些节点还未被使用 for(i; i<100; i++) { (*list)[i].next=-2; } } 在最后添加一个节点 //在最后添加数据...,Node; //创建一个头结点 Node createStart() { Node start; start.next=-1; return start; } //初始化一个静态链表

11810
您找到你想要的搜索结果了吗?
是的
没有找到

数据结构静态链表

数据域data用来存放数据元素,也就是通常我们要处理的数据;而游标cur相当于单链表中的next指针, 存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。...示例代码:(改编自《大话数据结构》) #include using namespace std; #define MAXSIZE 100 typedef int ElemType...; /* 线性表的静态链表存储结构 */ typedef struct Node {     ElemType data;     int cur; //为0时表示无指向 } StaticLinkList...    while(i)     {         i = array[i].cur;         ++j;     }     return j; } /*  在array中第pos个元素之前插入新的数据元素...静态链表插入和删除操作时不需要移动元素,只需要修改游标,从而改进了在顺序存储结构中插入和删除操作需要移动 大量元素的缺点;但并没有解决连续分配存储带来的表长难以确定的问题;并且失去了顺序存储结构随机存取的特性

65060

数据结构(4)双链表,循环链表静态链表

和单链表不同的操作在于插入和删除,不同点是双链表插入和删除需要同时修改两个方向的指针。...循环链表 循环单链表 表尾指向头结点 循环双链表 在什么的双链表插入和删除操作中,如果p是最后一个结点,那么p->next就是NULL ,但是使用循环链表的话就不会出现那种情况。...静态链表 链表的每个结点在内存中的分布是随机的,静态链表就是建立一个固定的区间,结点在这固定的区间内随机存储。...typedef struct { int data; int next;//下一个元素的数组下标 }SLinkList[MaxSize]; 初始化:把a[0]的next设为-1即可 关于静态链表的其他操作这里不写了...计划从明天开始栈和队列,静态链表这里先大概了解原理,具体实现之后再补。‍️

41640

数据结构(05)_链表01(单链表静态链表、单向循环链表

1.线性表的链式存储结构1.1.链式存储的定义:   为了表示每个数据元素与其直接后继之间的逻辑关系,数据元素除过存储本身的信息之外,还需要存储其后继元素的地址信息。   ...链式存储结构的逻辑结构:   1.2.单链表   单链表中的节点定义: 注意:这里的struct是用来定义一个类,与class的访问属性相反,默认为public单链表的内部结构:头节点在单链表中的意义是...:辅助数据元素的定位,方便插入和删除,因此,头节点不存储实际的数据。   ...1.3.单链表插入与删除:   插入:    node->value = e; node->next = current->next; Current->next = node...& e) { bool ret = true; index = index % (this->m_length + 1); // 可插入

24610

数据结构】单链表(Singly Linked List ) && 静态链表(Static list)

更多精彩尽在微信公众号【程序猿声】 [微信公众号] 数据结构-线性表|顺序表|链表(中) 本节纲要 预备知识 顺序表(Sequential List) 单链表(Singly Linked List )...#define status bool #define ERROR false #define OK true /* * 函数功能:指定位置后插 * 参数说明:phead链表头结点,IData插入数据...直接看具体代码: /* * 函数功能:指定位置后插 * 参数说明:phead链表头结点,IData插入数据,index索引 */ status InsertSListNodeBack(Node *...4.3 静态链表插入操作 前面我们讲动态链表的时候说过,增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。...写完了这个函数,我们来看看静态表中具体如何插入: //在链表的第i个位置插入元素e void SlistInsert(SLinkList space, int i, ElemType e) {

2K10

数据结构】链式家族的成员——循环链表静态链表

静态链表是通过数组来描述线性表的链式存储结构,链表中的结点结构与单链表一致,都是由数据域与指针与构成; 但是不同的是,静态链表中的结点的指针域存储的是结点的相对地址,也就是在数组中的下标,这里我们将它称为游标...在静态链表中,下标为0的元素被作为静态链表的头结点,它的数据域中可以不用存放信息,它的游标存放的是链表首元素的数组下标; 虽然静态链表是申请的一块连续的空间,但是表中的各个元素与单链表相同,不需要满足物理位置上相邻...; 2.2 静态链表的初始化 有看过【函数栈帧的创建与销毁】的朋友应该就会知道,我们在内存中申请空间时,申请的空间中会有一些初始的数据,这些初始数据如果我们将它们打印出来的会,会是一些随机的数据,因此为了避免我们创建的静态链表中存在这些随机值...; 2.3 小结 对于静态链表,我们需要掌握以下内容: 静态链表时通过数组实现的一个单链表; 在静态链表中,下标为0的首元素作为静态链表的头结点,数据域中不需要存放任何内容; 与静态顺序表一致,静态链表的大小是不可改变的...,我们需要对其初始化为-2; 静态链表插入与删除操作与单链表插入删除操作相同,只需要修改指针,不需要移动元素; 静态链表适用于一些不支持指针的高级语言(如:Basic); 静态链表还适用于数据元素数量固定不变的场景

24710

数据结构-单链表的读取,插入与删除

链表定义: struct ListNode { int value; ListNode *next; }; 单链表读取 在顺序存储结构中,比如数组中,想要获取某一个位置的数据是非常容易的一件事,...但是在链表中却要麻烦一些,因为链表的存储单元并不是连续的,而且我们只知道链表的头结点,也就是想知道第i个位置的数据,只能从头找下去,并没有什么其他的好方法。...p || j>i) { return nullptr; } return p; } 在上面的代码中,传入GetElem函数的是链表的头结点,这个代码和《大话数据结构...单链表插入 相比于顺序存储结构,链表的读取确实麻烦了些,但是好在插入和删除方便。比如要在链表的第三个结点之后插入一个结点。 ? 这里的1-6只是结点里面存的数据,不决定结点的顺序。...单链表删除 要删除一个链表中第三个结点后面的结点,逻辑与插入操作很类似,同样要考虑原链表断开后的情况: ?

1K70

数据结构】----链表--双向链表

文章目录 基本定义 初始化和定义 插入 删除 查找 销毁 双向循环链表 双向链表的应用场景和作用 基本定义 双向链表每个元素都是一个对象,每个对象包括一个数据域和两个指针域next和prev。...phead; } 定义两个指针分别指向前和后,并且定义一个数据域来存放数据 typedef int ElemType; typedef struct LTNode{ ElemType data...phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; } 在pos位置之后插入数据...//在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode...需要频繁在链表中间插入或删除节点的情况:双向链表可以在O(1)的时间复杂度内完成插入或删除操作,因此适合在需要频繁插入或删除节点的场景中使用。

5410

链表数据结构(单链表

链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表 单向链表,双向链表,环形链表 PHP的底层是C,当一个程序运行时,内存分成五个区(堆区,栈区...,全局区,常量区,代码区) 规定:基本数据类型,一般放在栈区 复合数据类型,比如对象,放在堆区 定义一个类Hero 定义成员属性排名 $no 定义成员属性姓名 $name 定义成员属性昵称 $nickname...定义成员属性 $next,是一个引用,指向下一个Hero对象 定义构造函数,传递参数:$no,$name,$nickname 创建一个头head,该head只是一个头,不放入数据 获取$head对象,...及时雨”) 连接两个对象,$head->next=$hero 获取第二个Hero对象$hero2,new Hero(2,”卢俊义”,”玉麒麟”) 连接两个对象,$hero->next=$hero2 遍历链表

54120

数据结构——链表

数据域和指针域两部分组成 - 数据域:存储元素数值数据 - 指针域:存储直接后继结点的存储位置 链表:n 个结点由指针链组成一个链表。...- 首尾相接的链表称为循环链表 头指针 - 指向链表中第一个结点的指针 首元结点 - 指链表中存储第一个数据元素a1的结点 头结点 - 在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息...链表的优缺点 优点 - 数据元素的个数可以自由扩充 - 插入、删除等操作不必移动数据,只需修改链接指针,修改效率较高 缺点 - 存储密度小 - 存取效率不高,必须采用顺序存取,即存取数据元素时...,时间复杂度为O(n) 不需移动元素,确定插入、删除位置后,时间复杂度为O(1) 适用情况 ① 表长变化不大,且能事先确定变化的范围 ② 很少进行插入或删除操作,经常按元素位置序号访问数据元素 ① 长度变化较大...; // 生成新结点*p cin >> p->data; // 输入元素赋值给新结点*p的数据域 p->next = L->next; L->next = p; // 将新结点*p插入到头结点之后

64585

数据结构——链表

链式存储结构 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻 有关术语 结点:数据元素的存储映像。...由数据域和指针域两部分组成 数据域:存储元素数值数据 指针域:存储直接后继结点的存储位置 链表:n 个结点由指针链组成一个链表。...首元结点 指链表中存储第一个数据元素a1的结点 头结点 在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息 设置头结点的好处 便于首元结点的处理 首元结点的地址保存在头结点的指针域中...链表的特点 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻 访问时只能通过头指针进入链表,并通过每个结点的指针域向后扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等...链表的优缺点 优点 数据元素的个数可以自由扩充 插入、删除等操作不必移动数据,只需修改链接指针,修改效率较高 缺点 存储密度小 存取效率不高,必须采用顺序存取,即存取数据元素时,只能按链表的顺序进行访问

45520

数据结构_链表

数据结构_LinkedList链表 前言: 此类笔记仅用于个人复习,内容主要在于记录和体现个人理解,详细还请结合bite课件、录播、板书和代码。...,在指针方面的理解也算是比较到位了 ---- [toc] ---- 为什么要使用链表(顺序表的局限性) 顺序表的优点: 连续物理空间,方便通过下标随机访问 缺点: 插入数据,空间不足时需要扩容,扩容有性能消耗...头部或中间位置插入或删除数据,需要挪动其他数据,效率较低 可能存在一定的空间占用,浪费空间;不能按需申请和释放空间 基于顺序表的局限性,就设计出了链表 链表 链表的概念 链表是一种在物理存储结构上非顺序非连续的存储结构...NULL) 节点/结点:在数据结构中,每一个数据节点/结点对应一个存储单元,节点/结点就是存储单元的地址(比如在链表里,结点就是链表结构体的地址) 注意: 从上图中可以看出,链式结构在逻辑上一定是连续的...更多情况下是作为其他数据结构的子结构,比如哈希桶、图的邻接表等。另外这种结构在面试题中出现的概率比较高。 带头双向循环链表:结构最复杂,一般用来单独存储数据用。

20510

数据结构链表

1.链表的定义: 链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。...在计算机科学中,链表作为一种基础的数据结构可以用来生成其它类型的数据结构。...链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的访问往往要在不同的排列顺序中转换。...而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。 链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。...链表通常可以衍生出循环链表静态链表,双链表等。对于链表使用,需要注意头结点的使用。 2. 示例分析: 2.1例子1: leet-code:25.

56920

数据结构链表

---- 数据结构链表:: SList.h #pragma once #include #include #include typedef...概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的....无头单向非循环链表: 结构简单,一般不会用来单独存数据,实际上更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等....带头双向循环链表: 结构最复杂,一般用来单独存储数据,实际中使用到的链表数据结构,都是带头双向循环链表,这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了....:只适合头插头删——O(1) 任意位置高效插入删除——双向链表 进阶:删除pos位置 要求是O(1) 替换法删除 缺陷:pos不能是尾结点 解决方法:将链表改成循环链表 进阶:在pos位置之前插入 要求是

29720

数据结构与算法(三)-线性表之静态链表

前言:前面介绍的线性表的顺序存储结构和链式存储结构中,都有对对象地引用或指向,也就是编程语言中有引用或者指针,那么在没有引用或指针的语言中,该怎么实现这个的数据结构呢?...一、简介 定义:用数组代替指针或引用来描述单链表,即用数组描述的链表叫做静态链表,这种描述方法叫做游标实现法; ?   ...上面的静态链表图有两个数组游标和数据,其中数据数组存储数据,而游标数组存储同下标为数据的下一个数据的下标值,简单模拟一下静态链表遍历的过程: 先查看下标为999的游标数组值:1; 根据游标数组值1,查找下标为...1的数据:A; 然后查看游标数组为1的值:2; 根据游标数组值为2查找对应的数据数组的值:C; 然后循环3->4,直至游标数组的值为0; 二、代码实现 静态链表的创建: 我们对数组的第一个和最后一个元素做特殊处理...cur则存放第一个有数值的元素的下标,相当于单链表中的头结点作用;   静态链表创建代码实现: public class StaticChain { //数据链 private

1.3K20

数据结构-链表

从我画的图中可以看出来,双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。...从结构上来看,双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,正是这样的特点,也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。...、双向链表】,支持增删操作 单链表反转链 表中环的检测 两个有序的链表合并 删除链表倒数第 n 个结点 求链表的中间结点 思考题:基于链表的 LRU 算法 LRU 思路一 如果此数据之前已经被缓存在链表中了...,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入链表的头部。...如果此数据没有在缓存链表中,又可以分为两种情况:undefined如果此时缓存未满,则将此结点直接插入链表的头部;undefined如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

39610

数据结构 - 链表

为什么需要链表 顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充(插入、删除)时又需要进行数据的搬迁,所以使用起来并不是很灵活。...链表的定义 链表(Linked list)是一种常见的基础数据结构,是一种 线性表的链式存储结构,存储地址空间不需要是连续的,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。...单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个数据域和一个链接域(地址域)。...L 指向链表的头节点(首节点)的位置,从 L 出发能找到表中的任意节点。 单向循环链表 ? 数据域 data 用来存放具体的数据。...有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作就统一了。 头结点不一定是链表必须要素。

47141

数据结构-链表

从我画的图中可以看出来,双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。...循环链表、双向链表】,支持增删操作 单链表反转链 表中环的检测 两个有序的链表合并 删除链表倒数第 n 个结点 求链表的中间结点 思考题:基于链表的 LRU 算法 LRU 思路一 如果此数据之前已经被缓存在链表中了...,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入链表的头部。...如果此数据没有在缓存链表中,又可以分为两种情况: 如果此时缓存未满,则将此结点直接插入链表的头部; 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。...https://time.geekbang.org/column/article/41149 algo: 数据结构和算法必知必会的50个代码实现 https://gitee.com/TheAlgorithms

38010
领券