说一说数组和链表两种数据结构的优缺点？

数组和链表是两种常用的数据结构，它们各自有优缺点：

数组：

优点：

1. 查询元素的效率高，可以 O(1) 的时间复杂度访问元素。

2. 内存空间是连续的，所以对缓存友好，读取较快。

3. 适用于大小固定的数据集合。

缺点：

1. 插入和删除元素效率低，需要移动其它元素，时间复杂度为 O(n)。

2. 指定大小后不易改变，如果需要扩容会耗费大量时间。

3. 如果数组中有大量空元素浪费存储空间。

链表：

优点：

1. 插入和删除元素效率高，时间复杂度为 O(1)。

2. 链表中的内存空间不需要连续，可以利用零散的存储空间，节省内存。

3. 适用于大小不确定的数据集合，可以动态扩展。

缺点：

1. 查询元素效率低，需要 O(n) 的时间复杂度。

2. 存储指针增加了存储空间的开销。

3. 由于链表的存储方式，对缓存不友好，读取的效率较低。