数组

概念解释

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

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

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

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

• 一维数组(如上图所示)

• 多维数组(数组的元素为数组)

数组的基本操作

• Insert - 在某个索引处插入元素

• Get - 读取某个索引处的元素

• Delete - 删除某个索引处的元素

• Size - 获取数组的长度

常见数组代码面试题

• 查找数组中第二小的元素

• 查找第一个没有重复的数组元素

• 合并2个排序好的数组

• 重新排列数组中的正数和负数

数组与链表的区别、优劣

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

读取

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

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

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

插入

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

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

删除

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