概述
在做题之前,让我们现简单理一下顺序表,链表的概念和关系。
首先我们要知道的是顺序表和链表都属于线性表。
线性表:由n(n>=0)个相同类型数据元素组成,并且可以在任意位置进行插入和删除数据元素操作的有限序列。
顺序表:用一组地址连续的存储单元依次存储数据元素的线性结构。
单链表:它是一种链式存储的线性表,用一组地址任意的存储单元存放线性表的数据元素,称存储单元为一个节点。
其结构如下:
其中节点Node如下:
1 . 比较顺序表和链表的优缺点,说说它们分别在什么场景下使用?
要比较顺序表和链表的优缺点,首先我们要了解他们各自的特点:
顺序表:存储分配——静态分配;
存取方式——随机存取;
插入删除需移动元素个数——移动近一半元素。
链表: 存储分配——动态分配;
存取方式——顺序存取;
插入删除需移动元素个数——不移动元素,只修改指针。
a. 空间的开辟:
顺序表的实现一般是实现连续开辟一段空间(或根据需求动态连续开辟空间),然后在进行数据的增删查改(静态顺序表),所以顺序表一般是固定空间大小的;
单链表则是一次只开辟一个结点的空间,用来存储当前要保存的数据及指向下一个结点或NULL的指针,所以单链表的空间大小时动态变化的。
b. 空间的使用:
当我们不知道要存储多少数据时,用顺序表来开辟的空间如果太大,就会造成一定程度上的浪费。
用单链表是实现时,因为是每需要存储一个数据时,才开辟一个空间,虽然有非数据项的指针占空间,但相比顺序表来说,浪费不是那么明显。(因为链表每次都是开辟的位置都是随机的,那么可能会把这块空间搞得七零八碎,出现很多小的一般使用不到的碎片空间)
c. 对CPU高速缓存的影响:
顺序表的空间一般是连续开辟的,而且一次会开辟存储多个元素的空间,所以在使用顺序表时,可以一次把多个数据写入高速缓存,再写入主存,顺序表的CPU高速缓存效率更高,且CPU流水线也不会总是被打断;
单链表是每需要存储一个数据才开辟一次空间,所以每个数据存储时都要单独的写入高速缓存区,再写入主存,这样就造成了,单链表CPU高速缓存效率低,且CPU流水线会经常被打断。
由其特点可知,顺序表的优点是便于随机存储,缺点是不便于插入删除等操作,因为插入删除一个元素需要移动其后的所有元素,但是链表不存在这个问题,链表只要改变指针就行,时间复杂度小,所以链表于顺序表恰恰相反,优点是便于插入删除等操作,缺点是随机存储没有顺序表方便。
所以,当我们需要随机存取的时候,适合使用顺序表;当需要做频繁插入删除操作时,适合使用链表。
2 . 从尾到头打印单链表(逆序打印单链表)
运用递归方法打印
//逆序打印单链表
void ReversePrint(ListNode* pList)
{
ListNode* cur =
最后
以上就是跳跃学姐为你收集整理的链表的逆置、合并、排序以及插入删除的全部内容,希望文章能够帮你解决链表的逆置、合并、排序以及插入删除所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复