数据结构「数组」

开篇第一说的，大家都会先聊数组，这是个很基础的数据类型，也是学其他数据结构的基础。学其他的数据结构也都会往数组里面做比较和延伸。文章末尾会有具体实现的github的地址，当前为java实现，后续会增加python和C的实现。

那什么又是数组呢，定义上可以理解为，有相同类型的，一定长度的数据，存放在连续的内存中。我们可以提炼下3个要素

1. 连续的内存空间(连续性)
2. 相同的数据类型
3. 一定长度

做一些简单的解释，因为这会牵涉到另外一个大的学科，计算机组成的内容中去。其实计算机程序对于CPU等这类单元的话，就是不同的指定集合和数据集合，除了CPU宝贵的数据寄存器外，我们可以简单理解为，内存就是提供程序运行时数据和指令存放的地方。而且可以理解为内存是连续的区块来构成的。而且每个数据存储单元，都会有自己的专属地址。可能会问那内存是多大呢，市面上有的比如2G,4G,8G,16G这种。光有这些是不够的，这只是硬件数据，其中还牵涉到操作系统的寻址能力的。这块很深入的东西，大家可以搜这方面的相关文章。

那回答单纯的数据结构中来，我们来用现实的一个例子来说明这套数据模式的一个特点。

我们先假设，在现实场景中有很多个大小相同的箱子且有序排列,箱子里面需要放5种颜色的颜料,恰好一种颜色的颜料可以被一个箱子装满。下面提供2种不同的装配方案。
第一种是按顺序把5种颜色的颜料放进以次的箱子中

第二种是很无序的把颜料放到不同的箱子里

这两种方案的优劣,应该一眼就能看出来,我们的场景是放置5种不同的颜色。第一种方案是按顺序的,所以很容易就能通过箱子的编号找到对应的箱子。即使不知道箱子的序号，只知道颜色，因为按顺序，一个一个的去看，也最多看5个。反观下面的排列方式，你可能最多要看9个箱子。

那回到我们计算机的世界当中来,我们会认为我们存放的不是颜料，而是数据，其实就是0和1。基础的二进制大家可以自行搜索，我们存的位置不是箱子，而是内存。内存同样的也会用16进制的编码方式按顺序提供很多个可以存放的空间(具体多少个,和操作系统的位数相关)。内存本身的逻辑也很复杂，也有分页,有虚拟地址，但是不管怎么说，我们当前认为内存能提供连续的存储空间即可。

上述的图片,即为数组放置数据的结构。我们可以把索引理解为是一种别名的逻辑,数值就是我们要存储的数据

下面，我们来看下数组这种数据结构的算法时间复杂度，其实也就是优劣。分析的逻辑就是数据的常用4大操作，增删改查。

1. 首先我们可以看下关于查的逻辑
   ①如果只能索引，或是理解偏移量，可以直接定位到需要的数据。这也是数组最为杀手级性能的地方。时间复杂度为O(1)
   ②如果我们不知道具体的索引的话，单个去找的话，时间复杂度即为O(n)。

//伪代码  e为需要查找的值
func findIndexData(e){
    for(i = 0; i < size; i++){
         if(data[i] == e)
              return i;
    }
}

2. 再看下修改的逻辑，这个和查询的逻辑类似
   ①如果知道索引，则直接修改数据即可。时间复杂度为O(1)
   ②如果不知道具体的索引的话，需要先查找，然后再更新，时间复杂度为O(n)

3. 新增，指定的索引位置，放入对应的数据。下方有个插入的步骤图，方便理解

   
   
   

   ①图例为在索引为3的位置放入指定的元素，我们能看的出来，需要做的事情为要把代插入索引的后面数据，往后各移动一位
   ②然后移动完所有后续的逻辑后，写入需要写入的数据，时间复杂度为O(n)

//伪代码(data为已定好的数组)
func add(index, e){
   for (i = size -1; i <= index; i--){
       //数组从插入位置整体向后移位
       data[i+1] = data[i];
    }
    data[index] = e;
}

4. 删除指定索引的数据，下方有个删除的对应的步骤图

   
   
   

   ①删除的逻辑为要把从索引开始的数据向前移动一位
   ②移动所有的位置后，剩余的位置可以置空，也可以不置空，可以定义一位偏移量也可

//伪代码
func remove(index){
   //删除即为数据搬移的操作
   for (i = index +1; i <= size;i++){
        data[i-1] = data[i];
   }
}

数组实现github