九、顺序表和单链表的对比分析 (2)

自定义类类型:非常复杂的类类型,涉及深拷贝的类类型,采用顺序表来存储,但凡到插入和删除一个对象,就要进行很多次大数据对象的复制,还是深拷贝对象的复制,这个大数据对象占用的空间可能会很大,此时顺序表的插入和删除,效率极低;如果采用单链表来存储的话,就只涉及指针操作,效率和具体的数据对象类型是无关的

数据访问

顺序表:随机访问,可直接定位数据对象,内部实现是用原生数组来做的,定位的时候基本不耗时,时间复杂度是常量

单链表:顺序访问,必须从头访问数据对象,无法直接定位

工程开发中的选择:

顺序表:

数据元素的类型想对简单,不涉及深拷贝

数据元素相对稳定,访问操作远多于插入和删除操作

单链表:

数据元素的类型相对复杂,复制操作相对耗时

数据元素不稳定,需要经常插入和删除,访问操作比较少

3、小结

线性表中元素的查找依赖于相等比较符==

顺序表适用于访问需求量较大的场合(随机访问)

单链表适用于数据元素频繁插入删除的场合(顺序访问)

当数据类型相对简单时,顺序表和单链表的效率不相上下

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wppwjx.html