前言

我们学习的第一个数据结构就是数组，相信数组是每一个学习编程的同学不管你使用什么语言都一定会接触的一个数据结构。相对而言，数组也是非常简单的一种数据结构。

数组基础

• 把数据码成一排进行存放
  
• 数组的索引
  对于数组来说，有一个很重要的概念，叫做索引。换句话说，由于我们的数组中每一个元素都是一个个紧挨着存放，这时候可以给每个元素做一个编号，而这个编号便是索引。并且这个数组是可以存放不同的数据类型(在java语言中,便是int,double,char...等8种基本数据类型)。

注：以java语言为例，一个数组只能存放同一种类型的多个元素。

• 数组的创建
  想要声明一个数组，就要开辟空间，使用new这样的语法，在开辟空间的同时，我们就必须声明这个数组的容量
  
• 数组最大的优点：快速查询。例如：scores[2]

存在的问题

• 数组在创建的时候，大小已经固定了
• 开辟的数组空间多了(浪费)或者少了(不够用)

制作动态数组类

结构

制作属于我们自己的动态数组类，结构图如下：

首先，它是支持使用泛型的

为什么要使用泛型呢？

• 为了可以让我们的数据结构可以放置"任意"的数据类型，而不仅仅只是java语言的8种基本类型的包装类(Boolean,Byte,Char,Short,Integer,Long,Float,Double)

注：泛型<E>也可以用其他寓意的词替换，例<Element>

用代码演示：

public class Array
    
      {    private E[] data;    private int size;    // 无参数的构造函数，默认的数组的容量capacity=10    public Array() {        this(10);    }    // 构造函数，传入数组的容量capacity构造Array    public Array(int capacity) {        data = (E[]) new Object[capacity];        size = 0;    }    // 获取数组中的元素个数    public int getSize() {        return size;    }    // 获取数组的容量    public int getCapacity() {        return data.length;    }    public boolean isEmpty() {        return size == 0;    }}
    

向数组中添加元素

向数组的末尾添加一个元素

初始的时候，整个数组为空，这个size=0，现在向数组末尾添加一个新的元素，我们只要在data[0]这个位置放上66，同时维护一下size++(这个size表示数组中元素个数)，而size变量指向的是数组中首个没有元素的位置。我们向数组末尾添加元素，其实就等同于向size这个位置添加元素。添加下个元素同理。

图解：

代码演示：

// 向所有元素后添加一个新元素public void addLast(int e) {    if(size == data.length){        throw new IllegalArgumentException("AddLast failed. Array is full.");    }    data[size] = e;    size++;}

向指定位置添加元素

我们需要把当前索引（比如1）为指定位置的的元素和它后面的元素，都向后挪一个位置。

• 先把最后一个元素（索引为3）挪到size（大小为4）这个位置
• 前一个元素（索引为2）诺到size-1（也就是3），反复以此……
• 最后挪完以后，索引为1就腾出来了，然后我们只要直接插入数据77就好了。
• 全部完成操作之后，需要维护一下size++，保证了它指向数组中首个没有元素的位置。

图解:

代码演示：

// 在index个位置插入一个新元素epublic void add(int index, E e) {    if (size == data.length) {        throw new IllegalArgumentException("Add failed. Array is full");    }    if (index < 0 || index > size) {        throw new IllegalArgumentException("Add failed. Required index >= 0 and index <= size");    }    for (int i = size - 1; i >= index; i--) {        data[i++] = data[i];    }    data[index] = e;    size++;}

在数组中查询元素和修改元素

如何在数组中添加元素，现在我们数组中有个元素之后，就可以尝试查询数组中的元素，并且修改相应的元素。 代码演示：

// 获取index索引位置的元素public E getIndex(int index) {    if (index < 0 || index >= size) {        throw new IllegalArgumentException("Get failed. Index is illegal.");    }    return data[index];}// 修改index索引位置的元素epublic void setIndex(int index, E e) {    if (index < 0 || index >= size) {        throw new IllegalArgumentException("Set failed. Index is illegal.");    }    data[index] = e;}

数组中的包含，搜索和删除元素

继续在这个数组类中添加相应的方法，主要包括包含、搜索和删除三个方法。在很多时候，我们在数据结构中存储了一些元素，我们需要查找在这些元素中是否包含某个元素，搜索元素所在的位置，并且删除该元素等等的操作。

• 数组中查询包含元素的代码演示：

// 查找数组中是否有元素epublic boolean contains(E e) {    for (int i = 0; i < size; i++) {        if (data[i] == e) {            return true;        }    }    return false;}

• 数组中搜索元素的代码演示

// 查找数组中元素e所在的索引，如果不存在元素额，则返回-1public int find(E e) {    for (int i = 0; i < size; i++) {        if (data[i] == e) {            return i;        }    }    return -1;}

• 数组中删除元素的代码演示

// 从数组中删除元素epublic void removeElement(E e) {    int index = find(e);    if (index != -1) {        remove(index);    }}

删除指定位置元素

最后，我们来看一下如何从数组中删除指定位置的元素。

举个栗子：比如说在我们的数组中有66,77,88,99,100这五个元素，指定了想删除索引为1的元素(77)

• 分析
  我们想要删除索引为1前，需要在这个索引后的所有元素向左移动（其实相当于把索引1的元素覆盖掉）
• 操作
  1. 将索引为2的元素移动到索引为1的位置上，即data[1] = data[2]
  2. 继续循环下去，直至data[size--] = data[size]
  3. 最后维护下size，进行size--操作
• 注意
  这个size既表示数组中有多少个元素，同时也指向了首个没有元素的位置
  图解操作：
  代码演示：

// 从数组中删除index位置的元素，返回删除的元素public E remove(int index) {    if (index < 0 || index >= size) {        throw new IllegalArgumentException("Remove failed. Index is illegal.");    }    E ret = data[index];    for (int i = index + 1; i < size; i++) {        data[index - 1] = data[index];    }    size--;    return ret;}