数据结构--数组、单向链表、双向链表
线性表:
顺序线性表和链表
顺序线性表:
- 就是数组(c语言),初始化固定数组的大小,申请连续的内存分配。
- 可能面临的问题有:数组边界溢出,不够存,需要重新申请新的连续的内存空间,造成内存浪费,性能下降,拓展性差。
- 数组实际大小可能没有等于初始化定义的,也造成内存浪费。
- 但是相对链表来说,数组的优点是通过数组下标可以快速找到数据的内存地址,查找效率高(o(1)),但是相反,插入和删除数据,后面的数据都要进行移动,效率低(o(n))。
链表:
- 分为单向链表、双向链表、循环链表等。
- 跟数组最大的不同的是,链表是不连续的内存,其利用的是整合碎片内存空间起来组成一个链表,合理利用和节约了内存空间,提高性能。
- 数据变动不会受到类似数组边界等限制,动态能力比较高,拓展性好。
- 单向链表查找数据的效率需要从表头一步一步的往下找,查找效率低(o(n))。
- 双向链表就是为了解决查找效率问题而诞生的,其可以从链表的任何一个位置从两边开始寻找,使用二分法查找的效率明显提高了,查找效率最高的还是数组。
- 双向链表比单向链表多了一个属性,来指向上一个节点的地址,其查找效率是用过牺牲空间换时间的做法。
- 链表的插入和删除效率(o(1))比数组高,因为它不涉及到后面整组数据的变动,只需要前或者前后的指向属性做修改就可以了。
单向链表结构图:
用面向对象的思想就是有两个属性,一个是值,一个是指向。末尾的指针指向空值
双向链表结构图:
有三个属性,一个是值,一个是前一个节点的指针 ,一个是下一个节点的指针,前后的指针指向空值
总结:
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: