一、什么是线性表
线性表是由零个或多个数据元素组成的有限序列。
- 性表是有限的
- 线性表第一个元素无前驱，最后一个元素无后继，中间元素只有一个前驱和后继元素
- 线性表可以是空表
二、常见线性表
image.png
常见的线性表数据结构有：数组，链表，队列，栈；与线性表相对的是稍稍复杂的数据结构，比如：树，图等。
三、什么是数组
数组是一种线性表，具有连续的内存空间，并且只能存储相同数据类型
四、数据有什么特性
- 数组支持随机访问，根据下标具有高效的查询性能
计算机会为内存单元分配内存地址，当要访问数组中第n个元素时，计算机根据寻址公式，可以快速定位第n个元素的内存地址，从而实现数组中元素的随机访问。
a[n]_address = a[0]_address + data_type_sizen
试想，我们怎样定义一个数组，int[] array = new int[10];
这里会得到一个变量名，这个变量名其实就是指向数组第一个元素地址的指针！当我们利用数组的引用变量去获取数组中的某个元素时，例如array[1]，这时就会根据寻址公式得到array[1]的地址（假设首地址是1001）：
array[1].address = 1001 + 41 = 1005 - 数组随机插入数据，随机删除数据性能较差
得益于连续的内存空间，数组随机访问某个元素的时间复杂度是O(1)，也因为要保持数组的这个特性（连续内存空间存储数据），数组的随机插入数据和随机删除数据都必须在操作完成后，做大量的数据搬移。
这里实现了一个数组的增删改查案例：
package algorithm;
import java.util.Arrays;
/**
* 数组增删改查测试
*
* @author zab
* @date 2019/5/23 8:54
*/
public class ArrayTest {
/**
* 数组初始容量大小
*/
private Integer init;
/**
* 数组定义
*/
private Integer[] array;
/**
* 数组当前下标，表示最后一个存值的元素下一个位置
*/
private int currentIndex;
public ArrayTest() {
init = 10;
array = new Integer[init];
}
public ArrayTest(int init) {
this.init = init;
array = new Integer[init];
}
/**
* 增,在数组末尾
*/
public Integer[] add(Integer i) {
if (currentIndex >= array.length * 0.8) {
//扩容
this.expansion();
}
array[currentIndex++] = i;
return array;
}
/**
* 增，指定位置
*/
public Integer[] add(Integer index, Integer value) {
//边界判断
if (index < 0 || index > array.length - 1) {
return null;
}
if (currentIndex >= array.length * 0.8) {
//扩容
this.expansion();
}
for (int i = currentIndex; i > index; i--) {
array[i + 1] = array[i];
if (i == index + 1) {
array[i] = array[i - 1];
array[index] = value;
currentIndex++;
break;
}
}
return array;
}
private Integer[] expansion() {
Integer[] arrayNew = new Integer[init << 1];
for (int i = 0, length = array.length; i < length; i++) {
arrayNew[i] = array[i];
}
this.init = arrayNew.length;
array = arrayNew;
//释放
arrayNew = null;
return array;
}
private Integer[] cutdown() {
if (init == 10) {
return null;
}
Integer[] arrayNew = new Integer[init >> 1];
arrayNew = Arrays.copyOf(array, arrayNew.length);
this.init = arrayNew.length;
array = arrayNew;
arrayNew = null;
return array;
}
/**
* 删，指定下标
*/
public Integer delete(Integer index) {
if (index < 0 || index > array.length - 1) {
return -1;
}
for (int i = 0, length = currentIndex; i < length - 1; i++) {
if (i >= index) {
array[i] = array[i + 1];
}
}
array[currentIndex-- - 1] = null;
if (currentIndex < (array.length >> 1) * 0.8) {
//缩容
cutdown();
}
return 1;
}
/**
* 设置值，指定下标
*/
public Integer set(Integer index, Integer value) {
if (index < 0 || index > array.length - 1) {
return -1;
}
array[index] = value;
return 1;
}
/**
* 查，指定下标
*/
public Integer get(Integer index) {
if (index < 0 || index > array.length - 1) {
return null;
}
return array[index];
}
@Override
public String toString() {
return "ArrayTest{" +
"init=" + init +
", array=" + Arrays.toString(array) +
'}';
}
}
可以看出，数组要实现随机删除一个元素，随机增加一个元素，需要循环做数据搬移，其时间复杂度为O(n) 。而不加先决条件笼统说数组增加删除的效率低是有问题的，数组在往最后增加删除数据的时间复杂度是O(1)。
而对于修改操作的时间复杂度分析同样需要分不同情况
（1）、如果知道数组中要修改元素的下标，修改时间复杂度为O(1)，例如修改下标为1的数据为value，则直接根据下标：
array[index] = value
二、如果仅仅知道要修改的元素值，而不知道元素在数组中的位置，则需要遍历数组，找到给定元素值的下标，再根据下标修改成想要的值，时间复杂度为O(n)。例如将数组中的元素oldValue，设置为newValue，其最简写法应该是：
public void set(Integer oldValue, Integer newValue){
for(int i = 0,j = array.length;i < j; i++){
if(array[i] = oldValue){
array[i] = newValue;
break;
}
}
}
