数据结构-数组与链表

文章结构概览

• 一、数组结构
  • 二、链表结构
  • 三、数组与链表的适用场景分析
  • 四、链表的常规操作及算法实现

一、数组

数组的特点

1. 数组在内存中所占据的区域是连续的
2. 在使用数组之前，必须预先申请其占用的内存空间大小。若无法准确预估所需空间，可能会造成内存资源的浪费，从而导致数组的空间利用率偏低
3. 在数组的起始位置进行数据插入或删除操作时，效率较低。当插入数据时，该位置之后的所有元素均需依次后移；而在删除数据时，该位置之后的所有元素同样需要向前移动
4. 数组具备高效的随机访问能力，属于一种随机存取结构，其时间复杂度可达到O(1)。由于数组在内存中存储方式为连续形式，因此访问任意元素时只需从首地址开始进行偏移即可完成
5. 当当前分配的空间无法满足需求时，需要对数组进行扩容操作。扩容过程中将涉及将原数组中的所有元素迁移至新数组的操作
6. 数组所占用的空间通常是从栈区分配获得

数组的优点
具有较强的随机访问能力，查找速度较快，并且时间复杂度为O(1)

数组的缺点

1. 在头部插入或删除数据的操作效率较低，其时间复杂度为O(N)
2. 空间利用率不高
3. 对内存空间的要求较高，需要有足够大的连续存储区域
4. 数组的空间大