数据结构-数组

为什么要学习数据结构？

因为计算机专业必学，数据结构就是研究数据如何在计算机进行组织和存储，使我们高效的操作数据。今天聊一聊线性结构中的数组。

总体来说可划分为以下三种

线性结构：数组，栈，队列，链表，哈希表
树结构：二叉树，二分搜索树，AVL，红黑树，堆，K-D树，哈夫曼树，Trie等等
图结构：邻接矩阵，邻接表

数组的数据结构

索引：数组是通过索引来操作数据的，索引从0开始
数组名：通过数组名[索引]可以操作索引对应的数据，scores[2]

动态数组实践

首先一个数据结构，离不开数据的增删改查，那么就自己创建一个类，内部维护一个数组，来模拟这个过程。后面还可以像集合一样，优化使用泛型特性和动态扩容等机制。

1.创建类，创建成员arr，用来存放元素。创建size用来维护数组内现有的元素个数。
比如数组长度是10，但是只存了5个元素，那么size就是5

public class MyArray {
    //声明一个数组
    private int[] arr;

    //数组中存在的元素个数（不是length，length是数组的长度，也可以说是容量（capacity））
    private int size;

    //因为数组提供了length方法，所以不需要创建和维护数组长度的变量
    //private int length;

    public MyArray() {
        this(10);//不传参数，数组长度默认就是10
    }

    public MyArray(int capacity) {
        arr = new int[capacity];////初始化数组
        size = 0;//刚开始数组中没有数据
}

2.创建好了之后，提供一些方法吧，先编写一些基本的方法，比如数组的容量，数组已存在的元素个数，数组是否为空等。这些方法都比较基础，所以也不需要过多解释了。

//返回数组中存在的元素个数
public int getSize() {
    return this.size;
}

//获取容量
public int getCapacity() {
    return arr.length;
}

//判断数组是否为空
public boolean isEmpty() {
    return this.size == 0;
}

//查看数组中是否包含指定元素
public boolean contains(int e)
{
    for(int x = 0; x < size; x++) {
        if(arr[x] == e) {
            return true;
        }
    }
    return false;
}

//查找指定元素在数组中的位置，如果没有，返回-1
public int find(int e)
{
    for(int x = 0; x < size; x++) {
        if(arr[x] == e) {
            return x;
        }
    }
    return -1;
}

3.添加元素，首先是添加元素到末尾。因为size就是目前数组内元素的个数，也就是需要添加到末尾索引的位置。如下图所示，要想添加元素到末尾，那么获取size的位置，添加就可以了，添加过后，维护一下size的数量。哦，对，记得方法的开始判断一下元素的边界，增加程序的健壮性。

//添加元素到数组末尾
public void addLast(int e)
{
    if(size == arr.length) {
        throw new IllegalArgumentException("Add last failed.Array is Full");
    }
    arr[size] = e;
    size++;
}

如果想在指定索引处添加一个元素呢？除了添加以外，还要维护其他的数据。比如下图所示，原来数组是66 88 99 100，现在要插入元素为“77”到索引1的位置，那么就要把索引1以后的元素，全部向右移动一格，给”77″腾出个地方，然后在插入，就解决问题了。（注意不可以跳跃插入，最大使用索引不能超过size所在的索引）

//通过索引添加元素
public void addByIndex(int index,int e)
{
    //插入的元素的索引只能在0和size期间
    if(index < 0 || index > size) {
        throw new ArrayIndexOutOfBoundsException("Add failed.Require index >=0 & <= size");
    }
    //添加一个元素，size就加一，等size个数等于数组长度时，抛异常
    if(size == arr.length) {
        throw new IllegalArgumentException("Add last failed.Array is Full");
    }
    //改变原始数据的位置，从size-1的位置到index的位置
    for(int i = size - 1; i >= index; i--)
    {
        arr[i + 1] = arr[i];
    }
    //插入新的元素
    arr[index] = e;
    size++;
}

那添加一个元素到头部也就很easy了，因为原理和上面一样，需要把头部往后的所有元素都向右移动一格，然后在插入。仔细一看，向尾部和头部插入元素都可以复用上面的代码。

//添加元素到数组末尾
public void addLast(int e)
{
    addByIndex(size,e);
}

//添加元素到数组开头
public void addFirst(int e)
{
    addByIndex(0,e);
}

4.删除元素，删除元素和添加其实差不多，添加是要把从添加位置的索引到最后的元素索引的所有数据做一个向右移动，删除是把从添加位置的索引到最后的元素索引的所有元素做一个向左移动。

public int removeByIndex(int index)
{
    if(index < 0 || index >= size) {
        throw new ArrayIndexOutOfBoundsException("Remove failed.Require index >=0 & <= size");
    }
    int temp = arr[index];
    for(int x = index; x < size; x++)
    {
        arr[x] = arr[x + 1];
    }
    size--;
    return temp;
}

public int removeFirst()
{
    return removeByIndex(0);
}
public int removeLast()
{
    return removeByIndex(size-1);
}


//按照元素删除
public boolean removeElement(int e)
{
    int result = find(e);//先找对应的元素
    if(result != -1)//如果有这个元素，则删除
    {
        removeByIndex(result);//删除这个元素
        return true;
    }
    else
    {
        return false;
    }
}

5.重写toString，方便使用System.out.print的时候显示数据的容量变化以及元素变化

//展示数组元素的方法
@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append(String.format("Array size = %d,capacity=%d\n",size,arr.length));
    sb.append("[");
    for(int x = 0; x < size; x++)
    {
        sb.append(arr[x]);
        if(x != size - 1)
        {
            sb.append(",");
        }
    }
    sb.append("]");
    return sb.toString();
}

6.可以自己定义个main方法测试一下，都没啥问题。

public static void main(String[] args)
{
    MyArray arr = new MyArray(20);
    for(int x = 1000; x < 1010; x++)
    {
        arr.addLast(x);
    }
    System.out.println(arr);
}
Array size = 10,capacity=20
[1000,1001,1002,1003,1004,1005,1006,1007,1008,1009]

7.泛型
但是这个代码目前是有弊端的，能不能像Java中集合那样，可以往数组里面添加任意类型的数据呢？可不可以等到数组容量不够的时候，自动帮我扩容呢？首先先解决一下”泛型”问题，这个问题比较简单，把类改成泛型类就可以啦，增加元素的方法都改成泛型，返回的元素也修改成泛型。

//这样
public class MyArray<E> {
    //声明一个数组
    private E[] arr;
//这样
public MyArray(int capacity) {
    arr = (E[])new Object[capacity];////初始化数组
//还有这样
public E removeByIndex(int index)
public boolean removeElement(E e)

8.扩容操作

假如数组是这些元素，那么当size = capacity的时候，也就是插入的元素数量等于数组长度，俗话说就是数组满了，那么这时候开始扩容。

扩容的原理其实就是再申请一个比当前这个数组还要大的一个数组（至于大多少呢？你可以自己定义。ArrayList扩容机制是大原数组的1.5倍，当然这个值没有对和错，你自己根据业务场景定就好。但尽量做一个权衡，太大了浪费空间，太小了会经常扩容，导致程序变慢。）然后一次性的把原数组的数据放到新数组，在改变一下变量对数组的引用，让变量指向新数组，这个扩容操作在方法内，方法执行完就弹栈了，也就没有变量在指向原数组了，原数组也就会被垃圾回收了。

扩容内存图解

扩容方法实现

//数组扩容方法
private void resize(int length) {
    E[] newArr = (E[])new Object[length];//声明新的数组
    for(int x = 0; x < size; x++)//将原数组所有的数据复制到新数组中
    {
        newArr[x] = arr[x];
    }
    arr = newArr;//改变引用，变量指向新数组
}

addByIndex方法的变动，当元素占满数组时，进行扩容

//元素添加的时候，满了不再抛异常了，进行扩容扩容机制
if(size == arr.length) {
    resize(arr.length * 2);
    //throw new IllegalArgumentException("Add last failed.Array is Full");
}

如果元素变少时，数组太大，也会浪费空间，可以进行缩容
removeByIndex方法的变动

//如果元素个数只占到整体数组长度的一半以下，为了避免浪费内存空间，进行缩容
if(size < arr.length / 2)
{
    resize(arr.length / 2);
}

明天记录该数组实现的时间复杂度，以及均摊复杂度问题和防止复杂度震荡问题。