在计算机的世界中，数据可以有各种各样的组织形式，比如，模拟现实中排队取钱的队列，代表复杂的社交网络的图结构等，不同的数据结构各自适应不同的情况。学习数据结构，我们能够为我们要解决的问题，选择合适的数据结构进行数据存储，从而使得程序更加高效。
数组
数组，是数据结构中最简单，也最常用的一个数据结构。所谓数组，是有序的元素序列。若将有限个类型相同的变量>，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中，为了处理方便， 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。
查找元素
数组是一个顺序存储的数据结构，如图所示是一个长度为10的数组，它的特点是存取速度快。通过指定下标，我们可以很快的取值。比如a[0],a[5]等操作，都可以在O(1)时间内完成。然而，如果我们并不提前知道元素所在的位置的呢？假如我们要查找的元素为100，伪代码表示如下
for(int i=0;i<n;i++){
if(a[i]==100){
return i;//返回元素所在下标
}
}
return -1;//如果遍历完都没有找到，则返回-1.
最好情况下，100在a[0]的位置，一下子就能找到，最坏情况下，100在数组的最后面，甚至是不存在，则需要遍历整个数组。****所以在数组中查找元素的时间复杂度为O(n)。
插入元素
如果我们要在数组中插入一个新的元素，根据插入位置的不同，效率也有所不同。以上图为例，如果要插入的位置在a[5]，那么直接a[5]=x就好。如果要插入的位置在a[0]呢？就需要将所有的元素往后移动一格，再把a[0]赋值为x。把所有元素往后移动一格的时间复杂度为O(n)，所以在数组中插入新元素时，时间复杂度为O(n)。其伪代码如下：
for(i=n;i>=insert_index;i--){//从后往前遍历到插入位置之后，把前面的数赋值给后面的数
a[i]=a[i-1];
}
a[i]=x;//跳出循环后，i刚好位于插入位置，直接赋值新插入的元素。
a.length = a.length+1;
删除元素
除了新增，删除也是同理。如果要删除a[4]位置的99，直接把a.length减少1就好。在计算机中，通常删除一个东西，并不是真的要去删除它，而是不再去管理它，再也访问不到它，就当做删除了。而如果是删除a[1]处的90，除了将a.length减1之外，还需要将a[2]到a[4]的数据往前移一格，变为a[1]到a[3]，把插入位置后的所有元素前移一格的时间复杂度为O(n)。所以数组删除元素时，时间复杂度为O(n)。
for(i=delete_index-1;i<n-1;i++){//从删除位置开始，用后面一个位置的值覆盖前面的值。
a[i]=a[i+1];
}
a.length = a.length - 1;
总结
时间复杂度：访问元素O(1)，查找元素O(n)，插入元素O(n)，删除元素O(n)
优点****：连续存储，具有在O(1)时间内随机存取的特性。
缺点：没有用到的空间被浪费了。
公众号：萌凯的程序人生
一枚IT研究生，致力于分享自己的学习经历和总结！
喜欢的话请点赞关注，谢谢您！
