数据结构基础-数组

1、数组是一种线性表，使用一组连续的内存空间来存储一组具有相同类型的数据

2、数组中查找修改其中一个元素比较高效，因为根据连续地址计算元素地址位置
a[i]_address = base_address + I*data_type_size

3、数组中插入和删除其中一个元素比较低效：

  插入操作：

  有序数组，数组的长度为n，将一个数据插入到数组的第k个位置，为了把第k个位置腾出来，需                     要把第k之后的元素都顺序的往后挪一位，操作复杂O(n)。
  无序数组，直接把k位置的数据移到数组的最后面，把新元素插入到第k个位置。

  删除操作：

  跟插入数据类似，删除第k个位置的数据，为了内存的连续性，也需要搬移数据。
  在某些情况下，如果我们不要求数据必须是连续的，删除的时候可以假删除，只是把这个元素标记为已删除，当组空间不够用的时候，再触发一次真正的删除，这样就大大减少了删除操作导致的迁移操作。

4、静态数组与动态数组。

  OC中不可变数组NSArray指的是内存地址及内存大小不可变，注意重新赋值时相当于数组指针指向新的数组。
  NSMutableArray一般情况下内存地址不变（插入，删除时通过打印数组地址验证），内存大小可变。
 向NSMutableArray中插入元素时，当数组已开辟的内存不够时进行扩容，扩容过程中连续内存不够时，需要重新分配一块更大的空间，把原来的复制过去再插入新的元素。