数据结构与算法: 数组

数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组有两个最大的特点：

• 线性表数据结构 ：线性表（Linear List）就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。数组，链表、队列、栈 都是线性表结构。与之对应的是非线性表数据结构，如二叉树、堆、图等。
• 连续的内存空间和相同类型的数据 。

线性表 vs. 非线性表

复杂度分析

数组具有如下特性：

• 非常高效的“随机访问”：通过下标访问只需一次操作即可获取到数据
• 低效的“插入”和“删除”：插入和删除后，需要同时移动数组中的其它数据

对应的时间复杂度如下：

• Access: O(1)
• Insert: 最小 O(1)，最大 O(n)，平均 O(n)
• Delete: 最小 O(1)，最大 O(n)，平均 O(n)

注意：数组的查询操作并非为 O(1)，即便是排好序的数组，采用二分查找，时间复杂度也是 O(logn)。