数组和链表的比较

[xszi]

数组和链表的比较

图片来源 知识来源

动图加载稍慢，稍等3秒哈！

• 数组
• 链表

数组的优点：

• 随机访问性强
• 查找速度快

数组的缺点：

• 插入和删除效率低
• 可能浪费内存
• 内存空间要求高，必须有足够的连续内存空间。
• 数组大小固定，不能动态拓展

链表的优点：

• 插入删除速度快
• 内存利用率高，不会浪费内存
• 大小没有固定，拓展很灵活。

链表的缺点：

• 不能随机查找，必须从第一个开始遍历，查找效率低

复杂度比较：

复杂度	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)