网站运营的案例,WordPress笑模板,微信制作小程序的软件,呼和浩特腾讯企业邮箱方向一#xff1a;分享一道你收藏的好题
小雅兰刚学数据结构与算法的时候#xff0c;学的真的是很吃力#xff0c;感觉链表真的特别的难#xff0c;在学习了后面的知识之后#xff0c;发现链表慢慢变得简单了#xff0c;若是放在现在#xff0c;小雅兰仍然觉得链表的知…方向一分享一道你收藏的好题
小雅兰刚学数据结构与算法的时候学的真的是很吃力感觉链表真的特别的难在学习了后面的知识之后发现链表慢慢变得简单了若是放在现在小雅兰仍然觉得链表的知识点以及OJ题是非常有意义的。
这是小雅兰写的和链表知识点有关的博客单链表——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客
双链表——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客
顺序表更新版——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 struct ListNode* reverseList(struct ListNode* head){if(headNULL){return NULL;}struct ListNode*n1NULL;struct ListNode*n2head;struct ListNode*n3n2-next;while(n2!NULL){n2-nextn1;//迭代n1n2;n2n3;if(n3!NULL){n3n3-next;}}return n1;} struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if (headA NULL || headB NULL) {return NULL;}struct ListNode *pA headA, *pB headB;while (pA ! pB) {pA pA NULL ? headB : pA-next;pB pB NULL ? headA : pB-next;}return pA;
} 这个题目用到的主要思想就是快慢指针的思想 bool hasCycle(struct ListNode* head) {if (head NULL || head-next NULL) {return false;}struct ListNode* slow head;struct ListNode* fast head-next;while (slow ! fast) {if (fast NULL || fast-next NULL) {return false;}slow slow-next;fast fast-next-next;}return true;
} 方向二分享一个你收藏的便捷技巧 链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构操作复杂。由于不必须按顺序存储链表在插入的时候可以达到O(1)的复杂度比另一种线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要O(n)的时间而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。 使用链表结构可以克服数组链表需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。但是链表失去了数组随机读取的优点同时链表由于增加了结点的指针域空间开销比较大。链表最明显的好处就是常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点但是不允许随机存取。链表有很多种不同的类型单向链表双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言如C,C和Java依靠易变工具来生成链表。 线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的。因此为了表示每个数据元素 与其直接后继数据元素之间的逻辑关系对数据元素来说除了存储其本身的信息之外还需存储一个指示其直接后继的信息即直接后继的存储位置。由这两部分信息组成一个结点表示线性表中一个数据元素。线性表的链式存储表示有一个缺点就是要找一个数必须要从头开始找起十分麻烦。 根据情况也可以自己设计链表的其它扩展。但是一般不会在边上附加数据因为链表的点和边基本上是一一对应的除了第一个或者最后一个节点但是也不会产生特殊情况。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向反向标记加在边上可能会更方便。 对于非线性的链表可以参见相关的其他数据结构例如树、图。另外有一种基于多个线性链表的数据结构跳表插入、删除和查找等基本操作的速度可以达到O(nlogn和平衡二叉树一样。 其中存储数据元素信息的域称作数据域设域名为data存储直接后继存储位置的域称为指针域设域名为next。指针域中存储的信息又称做指针或链。 由分别表示,…的N 个结点依次相链构成的链表称为线性表的链式存储表示由于此类链表的每个结点中只包含一个指针域故又称单链表或线性链表。 从结构上进行区分链表可以分为单向链表Singly Linked、双向链表Doubly Linked List和循环链表Circular List在一些资料里还会有块状链表或者多重链表Multiply Linked List绝大对数情况下我们只会用到下面三种链表。 单向链表Singly Linked 单向链表的存储结构比较简单在存储上它能够用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的。每个元素包含两个域其中存储数据元素信息的域称为数据域存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。如下图链接指向列表中下一个节点而最后一个节点则指向一个空值。 双向链表Doubly Linked List 双向链表的存储结构相对于单向链表更加复杂。在双向链表中每个节点中有两个指针域一个指向直接后继另一个指向直接前驱当连接为最后一个连接时指向空值或者空列表。如下图 循环链表Circular List 循环链表是另一种形式的链式存储结构。其特点是表中最后一个节点的指针域指向头节点整个链表形成一个环。由此从表中任意节点出发均可找到表中其他节点如下图 类似的双向链表也可以构建循环链表。循环链表有两个特点第一链表中没有 NULL 指针第二链表无须增加存储量。 存储单元可以是连续的也可以是不连续的每个节点包含两部分分别为数据元素域和指针域节点和节点之间通过指针域进行连接
方向三积灰这么久这个当时被你收藏的东西对现在的你还有用吗
链表的用途 实现文件系统链表可以被用来实现文件系统中的文件目录结构每个节点可以表示一个文件或者一个目录而整个文件系统可以看做一个包含多个节点的链表结构。排序链表可以用于实现排序算法例如归并排序和快速排序。这些算法通常需要在运行时动态创建和删除节点这正是链表的长处。管理动态数据链表是一种动态数据结构可以自由添加和删除节点因此它经常用于管理动态大小的数据集合例如文件系统、操作系统内存管理和网络协议。存储稀疏数据链表也可用于存储稀疏数据结构例如稀疏矩阵。由于链表可以有效地管理和存储无序的数据集合因此它是一种有效的方法来存储稀疏数据。实现各种数据结构表通常用于实现其他高效的数据结构例如队列、栈和哈希表。链表提供了高效的插入和删除操作可以在 O(1) 的时间内执行而数组等其他数据结构需要进行大量的数据搬迁。 可用链表实现的数据结构 线性数据结构链表可以用来实现栈、队列、链式队列等线性数据结构而且基于链表实现的栈和队列可以动态增长比基于数组的实现更灵活。哈希表哈希表使用链表可以解决哈希碰撞Hash Collision的问题链表可以用来构成哈希桶当出现哈希碰撞时将冲突的数据添加到链表的末尾。图和树链表可以用来描述和实现复杂的图和树数据结构每个节点可以使用链表来存储子节点或相邻的节点。 实现高效的内存分配器链表可以被用来实现文件系统中的文件目录结构每个节点可以表示一个文件或者一个目录而整个文件系统可以看做一个包含多个节点的链表结构。 链表主要是便于管理长度或数量不确定的数据相对于数组链表处理这种数据时比较节省内存。动态语言通常不大需要链表因为动态语言的解释器帮你管理内存但当你对空间效率或插入动作的效率有特殊要求时也可在动态语言中使用链表。
链表常用于在程序中临时存储一组不定长的线性数据。
具有这样的特点的数据可以用链表来保存
1数据是逐渐增加的
2数据是不定长的在存储第一个数据之前难以确定一个将来一共需要存储多少数据的上限或者虽然可以确定上限但这个上限又比通常大部分情况下数据可能达到的长度要大得多因而一次性按照上限把空间分配好是不划算的。而链表则可以在每次需要增加新数据时才为之申请内存不会造成浪费也不会因一次申请不足而使数据的数量受到限制。
3不需要按照序号对数据进行随机访问。
C STL 中提供了list容器就是链表。同时STL还提供了vector容器也可以用于处理具有上述特点的数据而且vector还支持随机访问即可以不考虑上述第3点要求。但vector在增加数据时如果原先分配的连续内存已经用完则需要重新分配内存并把原有数据复制过去这时它的插入数据的动作时间复杂度就不是O1了不是常量时间了。因而链表适于处理的数据除了具有上述特点外如果还有如下第4点特征则以链表为最佳选择了
4希望每次添加数据、删除数据的动作的时间复杂度都是O1的常量时间。 好啦小雅兰今天的分享就到这里啦还要继续加油噢
