我们不过是普通人，只不过在彼此眼中闪闪发光

1、什么是顺序表？

2、模拟实现ArrayList

2.1 模拟实现前的约定

2.2 构造方法

2.3 add方法

2.4 contains 方法

2.5 indexOf 方法

2.6 get 方法

2.7 set 方法

2.8 remove 方法

2.9 getSize 和 clear 方法

3、ArrayList 的学习

3.1 ArrayList的成员属性

3.2 ArrayList的构造方法

3.2.1 构造方法1

3.2.2 构造方法2

3.2.3 构造方法3

3.3 ArrayList 的 add 方法

3.4 ArrayList的常用方法

4、ArrayList的使用

4.1 ArrayList的遍历

4.2 扑克牌例子

4.2.1 准备工作

4.2.2 买一副牌逻辑

4.2.3 洗牌逻辑

4.2.3 发牌逻辑(重点)

4.2.4 测试整体逻辑

1、什么是顺序表？

这里运用博主之前写C语言实现顺序表中引用的一句话：

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。

顺序表又可以分为动态存储的顺序表和静态存储的顺序表，基本上现在不会使用静态的，这里就不介绍静态的了，所谓动态，就是当顺序表满的时候会自动扩容！我们接着往下看：

在Java中官方提供了ArrayList类，底层也是用数组实现的顺序表。

那么今天我们不急着去解读ArrayList类，而是先凭借我们之前的学习面向对象的知识，以及C语言数据结构阶段顺序表的实现，尝试着模拟实现 ArrayList类，当然，Java提供的是一个泛型类，可以存放任意指定类型数据(基本数据类型除外) ，我们就不模拟的那么复杂，能基本实现一些常见方法就行，等模拟实现之后，我们再去阅读源码。

2、模拟实现ArrayList

2.1 模拟实现前的约定

我们约定 elem 是存放整型数据的数组，size 表示数组当前有效元素个数，DEFAULT_CAPACITY 容量值，那么就可以写出这样的代码：

java">public class MyArrayList {
    private int elem[]; //存放数据
    private int size; //数组有效元素个数
    private static final int DEFAULT_CAPACITY = 10; //约定容量
}

同时我们还要实现以下几个常用的方法：

java">public void add(int data);// 新增元素,默认在数组最后新增

public void add(int pos, int data);// 在 pos 位置新增元素

public boolean contains(int toFind);// 判定是否包含某个元素

public int indexOf(int toFind);// 查找某个元素对应的位置

public int get(int pos);// 获取 pos 位置的元素

public void set(int pos, int value);// 给 pos 位置的元素设为 value

public void remove(int toRemove);//删除第一次出现的关键字key

public int getSize()// 获取顺序表长度

public void clear();// 清空顺序表

其实还有很多方法，比如头插，尾删，但这些你实现了上面的，相信你自己也能解决的，现在我们就撸起袖子写代码吧：

2.2 构造方法

这里我们想一想，如何设置我们的构造方法呢？如果用户想一开始的时候就自定义大小呢？如果不想自定义我们是不是要设置一个默认的大小？那么就可以写出下面两个构造方法：

java">// 无参构造方法，默认将数组容量设置成DEFAULT_CAPACITY
public MyArrayList() {
    this.elem = new int[DEFAULT_CAPACITY];
}
// 带参数构造方法，将数组容量设置成用户指定的容量
public MyArrayList(int capacity) throws IllegalCapacityException {
    // 检查指定容量是否非法
    if (capacity <= 0) {
        throw new IllegalCapacityException("设置非法容量");
    }
    this.elem = new int[capacity];
}

代码中的异常是我自定义的一个运行时异常，如果对异常还不了解的，可以看博主之前写的JavaSE系列文章，这里我就不再谈异常了。

2.3 add方法

java">private void capacity() {
    //将原数组扩大到2倍，利用Arrays.copyOf
    int len = getSize();
    this.elem = Arrays.copyOf(this.elem, len * 2);
}

// 新增元素,默认在数组最后新增
public void add(int data) {
    // 1.空间是否满了，满了则需要扩容
    if (getSize() == this.elem.length) {
        capacity(); //扩容
    }
    // 2.往数组最后位置新增元素
    // 3.有效数据自增1
    this.elem[this.size++] = data;
}

在写这个方法的时候，我们要注意数组如果满了就要增容，而增容这里我们用到 copyOf 方法，每次扩容2倍。

add方法重载，在pos位置新增：

java">// 在 pos 位置新增元素
public void add(int pos, int data) throws IllegalPosException {
    //1.检查pos下标的合法性(顺序表指定插入前面必须有元素，不能隔着插入)
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("指定插入pos位置不合法");
    }
    //2.判断数组是否需要增容
    if (getSize() == this.elem.length) {
        capacity(); //扩容
    }
    //3.从pos位置的元素都往后移
    for (int i = this.size - 1; i >= pos; i--) {
        this.elem[i + 1] = this.elem[i];
    }
    //4.pos位置放入数据，size自增
    this.elem[pos] = data;
    this.size++;
}

这里图就不给大家画了，在博主数据结构C语言版本的时候已经有很详细了图解了，感兴趣的可以去看一看，大同小异。

这里我们直接来说第一个要注意的点，因为是顺序表，插入元素不能隔着元素插入，也就是你插入的位置前面必须要有元素！也就得出 pos 必须小于等于我们的有效元素个数！

而且 pos 的位置不能小于0！

接着就是判断扩容和中间插入需要挪动后面的元素了，过程很简单，这里就不多谈了。

2.4 contains 方法

java">// 判定是否包含某个元素
public boolean contains(int toFind) {
    //1.遍历数组
    for (int i = 0; i < getSize(); i++) {
        if (this.elem[i] == toFind) {
            return true; //2.找到返回true
        }
    }
    //3.找不到返回false
    return false;
}

这个方法就太简单了，看我写的注释就能看懂！

2.5 indexOf 方法

java">// 查找某个元素对应的位置
public int indexOf(int toFind) {
    //1.遍历数组
    for (int i = 0; i < getSize(); i++) {
        if (this.elem[i] == toFind) {
            return i; //2.找到返回下标
        }
    }
    //3.找不到返回-1
    return -1;
}

这个方法跟上面contains方法大同小异，无需多言！

2.6 get 方法

java">// 获取 pos 位置的元素
public int get(int pos) {
    //1.判断pos位置是否合法
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("获取pos位置不合法");
    }
    //2.返回pos位置值
    return this.elem[pos];
}

这个方法需要注意的点就是判断pos下标位置的合法性，注意这一点就ok了！

2.7 set 方法

java">// 给 pos 位置的元素设为 value
public void set(int pos, int value) {
    //1.判断pos位置是否合法
    if (pos > getSize() || pos < 0) {
        throw new IllegalPosException("pos位置不合法");
    }
    //2.设置值
    this.elem[pos] = value;
}

好像跟上面的 get 方法没什么区别唉，多简单就不用我多说了吧！

2.8 remove 方法

java">//删除第一次出现的关键字key
public void remove(int toRemove) {
    //1.获取第一次key出现的位置
    int pos = indexOf(toRemove);
    if (pos == -1) {
        return;
    }
    //2.从pos位置的元素都往前覆盖
    for (int i = pos + 1; i < getSize(); i++) {
        this.elem[i - 1] = this.elem[i];
    }
    //3.有效数据减一(如果是引用类型需要置null)
    this.size--;
}

这个方法我们就可以复用我们之前写的 indexOf 方法了，不用重新写查找逻辑了，接着把后面的元素覆盖掉 pos 下标的元素就可以了！记得别忘记有效数据减一哦！

2.9 getSize 和 clear 方法

java">// 获取顺序表长度
public int getSize() {
    return this.size;
}

// 清空顺序表
public void clear() {
    this.size = 0;
}

这两个就简单了吧，但是要注意一点，如果你的顺序表放的是引用类型，需要置null，方法已经实现的差不多了，感兴趣的下来结合代码画图写一写吧！

3、ArrayList 的学习

3.1 ArrayList的成员属性

ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
ArrayList实现了Serializable接口，表明ArrayList是支持序列化的

这就是类定义的前部分，这里还是比较复杂的，会随着我们学习的深入，逐步学习到。

接下来我们来看ArrayList的几个成员变量：

3.2 ArrayList的构造方法

3.2.1 构造方法1

当前是一个带参数的构造方法，很好理解，根据传递的参数开辟大小，如果参数是等于0，就直接把 EMPTY_ELEMENTDATA 共享空数组赋值给存放数据的数组中，如果是给定一个负数，显然是错误的，也即直接抛出异常！

3.2.2 构造方法2

奇怪，这个无参构造方法居然也是给了一个空数组，也就是没有分配数组内存，那到底是怎么把数据放进去的呢？别急，随着后面的讲解，你会解开这个谜题。

3.2.3 构造方法3

按照集合迭代器返回元素的顺序，构造一个包含指定集合元素的列表，如果是属于同类型，就直接放入到存放数据的数组中，如果不是同类型，则利用 copyOf 拷贝指定的集合，如果指定集合长度为0，则把 EMPTY_ELEMENTDATA 共享空数组赋值给存放数据的数组中。

这个地方如果你不是很理解，没关系，因为现在还没接触迭代器，随着学习的深入就会接触到。

3.3 ArrayList 的 add 方法

别小看这几行代码，跟我们自己模拟实现的还是有区别的，真正有内涵的代码其实在 ensureCapacityInternal 这个方法中，那么现在，我们就一步步去解开他的面纱：

有了上面的图解我们不难看出，真正的扩容是在 add 方法中实现的，所以在实例化 ArrayList 的时候，是不会默认给你开辟空间的。所以 ArrayList 默认容量是在 add 方法调用后，才会分配空间。而且在真正扩容之前会检测是否能扩容成功，防止太大导致扩容失败。

3.4 ArrayList的常用方法

方法	作用
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空顺序表
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

还有其他方法需要使用的话，就可以去查阅Java的帮助文档，到了数据结构阶段，就要尝试着自己看源码，看文档了，培养自主学习的能力！

4、ArrayList的使用

4.1 ArrayList的遍历

对于顺序表的遍历，我们可以通过 for 循环，for-each，以及迭代器的方法遍历：

java">public class TestArrayList {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        // 通过for循环遍历ArrayList
        for (int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        // 通过for-each循环遍历ArrayList
        for (Integer integer : arrayList) {
            System.out.print(integer + " ");
        }
        // 通过迭代器遍历ArrayList(了解即可)
        Iterator<Integer> it = arrayList.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}

4.2 扑克牌例子

这里我们要运用我们上面学的知识写一个扑克牌的例子：

4.2.1 准备工作

首先我们肯定有一个类把我们的一张扑克抽象出来，扑克有花色和点数，那么我们就可以这样写：

java">public class Poker {
    private String decor;
    private int number;

    public Poker(String decor, int number) {
        this.decor = decor;
        this.number = number;
    }

    @Override
    public String toString() {
        return this.decor + this.number;
    }
}

那么我们还得需要表示多张扑克牌，同时也需要一个存放扑克牌的容器，这里我们选用 ArrayList，同时还需要一个数组来存储对应花色。

java">public class Pokers {
    private final String[] decor = { "♥", "♠", "♣", "♦" };
    private List<Poker> pokerList = new ArrayList<>();

    // 获取花色
    public String get(int index) {
        return decor[index];
    }
}

这里为什么可以使用 List 接收 ArrayList 的对象呢？因为 List 是一个接口，ArrayList 实现了这个接口，所以这里就实现了向上转型。