# 数组

### 概念解释

**数组(Array)**大概是最简单，也是最常用的数据结构了。其他数据结构，比如栈和队列都是由数组衍生出来的。

下图展示了1个数组，它有4个元素：

[![](https://blog.fundebug.com/2018/08/27/code-interview-data-structure/array.png)](https://blog.fundebug.com/2018/08/27/code-interview-data-structure/array.png)

每一个数组元素的位置由数字编号，称为下标或者索引(index)。大多数编程语言的数组第一个元素的下标是0。

根据维度区分，有2种不同的数组：

* 一维数组(如上图所示)
* 多维数组(数组的元素为数组)

### **数组的基本操作**

* Insert - 在某个索引处插入元素
* Get - 读取某个索引处的元素
* Delete - 删除某个索引处的元素
* Size - 获取数组的长度

### **常见数组代码面试题**

* [查找数组中第二小的元素](https://www.geeksforgeeks.org/to-find-smallest-and-second-smallest-element-in-an-array/)
* [查找第一个没有重复的数组元素](https://www.geeksforgeeks.org/non-repeating-element/)
* [合并2个排序好的数组](https://www.geeksforgeeks.org/merge-two-sorted-arrays/)
* [重新排列数组中的正数和负数](https://www.geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/)

## 数组与链表的区别、优劣

![](https://3953159057-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-L_oS8XWzoA34pjHOQZS%2F-Lbaqhav8vs9GEsmMQuS%2F-Lbaqvp_JdXSxAj-voeC%2Fimage.png?alt=media\&token=b040412f-b7ab-400c-8576-d35b6a13417e)

需要存 储多项数据时，有两种基本方式——数组和链表。但它们并非都适用于所有的情形，因此知道它 们的差别很重要。接下来介绍数组和链表以及它们的优缺点。

### 读取

读取的时候用数组更好，因为只要知道那个位置的索引就行，但链表却不行，在需要读取链表的最后一个元素时，你不能直接读取，因为你不知道 它所处的地址，必须先访问元素#1，从中获取元素#2的地址，再访问元素#2并从中获取元素#3 的地址，以此类推，直到访问最后一个元素。需要同时读取所有元素时，链表的效率很高：你读 取第一个元素，根据其中的地址再读取第二个元素，以此类推。但如果你需要跳跃，链表的效率 真的很低。 

数组与此不同：你知道其中每个元素的地址。例如，假设有一个数组，它包含五个元素，起 始地址为00，那么元素#5的地址是多少呢？

只需执行简单的数学运算就知道：04。需要随机地读取元素时，数组的效率很高，因为可迅 速找到数组的任何元素。在链表中，元素并非靠在一起的，你无法迅速计算出第五个元素的内存 地址，而必须先访问第一个元素以获取第二个元素的地址，再访问第二个元素以获取第三个元素 的地址，以此类推，直到访问第五个元素

### 插入

这犹如寻宝游戏。你前往第一个地址，那里有一张纸条写着“下一个元素的地址为123”。因 此，你前往地址123，那里又有一张纸条，写着“下一个元素的地址为847”。

需要在中间插入元素时，数组和链表哪个更好呢？使用链表时，插入元素很简单，只需修改 它前面的那个元素指向的地址。而使用数组时，则必须将后面的元素都向后移。如果没有足够的空间，可能还得将整个数组复制到其他地方！因此，当需要在中间插入元素 时，链表是更好的选择。

### 删除

如果你要删除元素呢？链表也是更好的选择，因为只需修改前一个元素指向的地址即可。而 使用数组时，删除元素后，必须将后面的元素都向前移。