数据结构-数组

数组概念:

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

关键词:

线性:顾名思义，线性表就是数据排成像一条线一样的数据结构。每个线性表上的数据最多只有前后两个方向。其实除了数组，链表，队列，栈等也是线性表结构

线性表结构

而与它相对立的概念就是非线性表，比如说二叉树，堆，图。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

第二个是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，随机访问对应的就是查询很快，但是当插入和删除的时候，为了保证连续性，需要对数据进行大量的迁移工作。

接下来我们来看下插入操作

数组长度为n,现在我们要将一个数据插入到数组中的第k个位置。为了把第k个位置空出来，就需要把k后面所有的数据依次往后面移动一位，如果我们是在数组开头插入数据，那么就需要把所有的数据都顺序往后面移动，这个时候时间复杂度就是O(n)，如果是在数组末尾插入一个数据，那么就不需要移动数据，时间复杂度就是O(1)，所以最坏情况下的时间复杂度是O(n)，

最好情况下的时间复杂度是O(1)，但是其实在真正的工作当中，出现这两种情况的几率很小，大多数都是在数组开头到结尾的位置插入数据，那么平均算下来时间复杂度就是O(n)。

我们再来看删除操作

跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为O(1)，如果删除开头的数据，则最坏情况时间复杂度为O(n)；平均情况时间复杂度也为O(n)。

实际上在某些特殊情况下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？

数组a[10]中存储了8个元素：a,b,c,d,e,f,g,h。现在我们要依次删除a,b,c三个元素

为了避免搬移三次数据，我们可以给这三个数据打上已删除的标示，当数组没有更多空间存储数据时，我们在触发一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

内容小结

我们今天学习了数组。它可以说是最基础，最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入，删除操作也因此变得比较低效，平均情况时间复杂度为O(n)。在平时的业务开发中，我们可以直接使用编程语言中提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。