本文共 687 字,大约阅读时间需要 2 分钟。
数组是申请的一块连续的内存空间,并且在编译阶段就要确定空间大小的,同时运行阶段是不允许改变的,意味着所有待办事项在内存中都是相连的(紧靠在一起的)。
链表是动态申请的内存空间,现用现申,比数组灵活。
当同时读取所有元素时,链表的效率高,读第一个,读第二个。
当你需要跳跃,链表的效率就很低了。
数组是连续的内存,对于访问数据,可以通过下标直接读取,时间复杂度为O(1),而添加删除数据就比较麻烦,需要移动操作数所在位置后的所有数据,时间复杂度为O(N)。
链表是物理上非连续的内存空间,对于访问数据,需要从头便利整个链表直到找到要访问的数据,没有数组有效,但是在添加和删除数据方面,只需要知道操作位置的指针,很方便可以实现增删,教数组比较灵活有效率。
| 数组 | 链表 |
读取 | O(1) | O(n) |
插入 | O(n) | O(1) |
删除 | O(n) | O(1) |
插入多,读取少。用链表。
插入少,读取多。用数组。从中间插入数据多使用链表,只需要修改它前面的那个元素指向的地址就行了,而数组,必须将后面的元素都向后移动,如果空间不足,还要重新复制新的空间。
不同点:
从逻辑结构看
从内存上看
综上,对于快速访问数据,不经常增删的时候选择数组,对经常增删的数据选择链表。
转载地址:http://srqai.baihongyu.com/