在上一章节中，我们通过代码示例以及画图的方式详细了解了顺序表，并模拟实现了它。那么，是不是以后每次需要用到顺序表这种数据结构时，我们都需要先模拟实现顺序表之后才能使用呢？答案是否定的。 在Java中，提供了ArrayList类来帮助我们实现顺序表这种数据结构。ArrayList是一个普通的类，实现了List接口：

接下来，我们就来学习在Java中ArrayList类的具体用法。

一、ArrayList的构造

常见的ArrayList的构造有三种方式：

    public static void main(String[] args) {//构造ArrayList<Integer> arrayList = new ArrayList<>(); //无参构造List<Integer> list = new ArrayList<>(2); //指定顺序表容量List<Integer> list1 = new ArrayList<>(list); //参数为 顺序表}

分别是：无参构造、指定容量、参数为顺序表。因为ArrayList类实现了List接口，所以在进行构造时，等号左边既可以是ArrayList也可以是List。在使用第三种构造方法时，需注意：list中元素的类型必须与list1中元素的类型相同才行，否则会编译报错。

二、ArrayList常见操作

ArrayList类中提供了非常多的方法，使用频率最高的为以下这些：

这些方法绝大部分我们已经自己模拟实现过了，用法和我们模拟实现的一样，不过有一些特殊的方法需要特殊记忆：

    public static void main(String[] args) {//方法测试List<Integer> list = new ArrayList<>(); //无参构造list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list); //[1, 2, 3, 4, 5]//addAll:添加一个顺序表中的所有元素list.addAll(list);System.out.println(list); //[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]//使用remove进行删除时，如果想要删除值，需要通过new关键字list.remove(2);System.out.println(list); //[1, 2, 4, 5, 1, 2, 3, 4, 5]list.remove(new Integer(2));System.out.println(list); //[1, 4, 5, 1, 2, 3, 4, 5]//使用subList对顺序表进行截取List<Integer> list1 = list.subList(1, 3); //左闭右开区间System.out.println(list1); //[4, 5]//当修改截取到的顺序表中的值时，原顺序表对应位置的值也会被修改list1.set(1, 666);System.out.println(list1); //[4, 666]System.out.println(list); //[1, 4, 666, 1, 2, 3, 4, 5]}

在上面这段代码中，我们还需注意一点：当调用无参的构造方法时，不会分配内存；默认是在第一次调用add方法时，分配大小为10的内存空间；当空间不够需要扩容时，默认以1.5倍大小进行扩容。

三、ArrayList的遍历

ArrayList的遍历有很多种方式：直接输出、for循环遍历以及迭代器：

    public static void main(String[] args) {//遍历List<Integer> list = new ArrayList<>(); //无参构造list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);//方式一：soutSystem.out.println(list); //源码中重写了toString方法System.out.println("===========================");//方式二：for循环for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();for (Integer x : list) {System.out.print(x + " ");}System.out.println();System.out.println("===========================");/*** 方式三：迭代器* Iterator 和 ListIterator都可以遍历顺序表，ListIterator还可以逆序遍历*/Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + " ");}System.out.println();ListIterator<Integer> listIterator = list.listIterator();while (listIterator.hasNext()) {System.out.print(listIterator.next() + " ");}System.out.println();//使用ListIterator逆序输出ListIterator<Integer> listIterator1 = list.listIterator(list.size());while (listIterator1.hasPrevious()) {System.out.print(listIterator1.previous() + " ");}System.out.println();}

在这些方式中，最常使用的是for-i循环以及for-each循环。

四、ArrayList练习

1.【小练习】

题目： 已知两个字符串s1、s2，现在要求：删除第一个字符串中出现的 所有的 第二个字符串中的字符：

根据题意，我们需要删除s1中出现的所有的s2中的字符，那么，我们就可以遍历s1，获取s1中所有的字符，看这个字符是否为s2中的字符，如果不是，我们就将此字符添加到顺序表中，最后返回一个顺序表即可。

    //编写一个方法实现主要操作public static ArrayList<Character> del(String s1, String s2) {//创建一个顺序表，接收s1中与s2中不重复的字符ArrayList<Character> arrayList = new ArrayList<>();//遍历s1for (int i = 0; i < s1.length(); i++) {//获取对应下标位置的字符char ch = s1.charAt(i);if (!s2.contains(ch + "")){arrayList.add(ch);}}return arrayList;}public static void main(String[] args) {//小练习String s1 = "welcome to victim";String s2 = "come";ArrayList<Character> ret = del(s1, s2); //接收返回值for (Character x : ret) {System.out.print(x);}}

2.杨辉三角

杨辉三角

在解决这道在线编程题时，我们需要注意理解代码模板中给出的返回值的含义：我们已经知道顺序表的底层其实是一个数组，那么对于本题中给出的返回值，我们就可以理解为其本质是一个二维数组：

我们为杨辉三角的每一行都创建一个顺序表，存储对应行中的数据元素，最后再将这些顺序表都存储到一个新的顺序表中，在这个新的顺序表中的每个元素都是一个顺序表。

我们再回归到这个数学问题本身，可以观察到，每一行的第一个元素和最后一个元素的值都为1，我们再将杨辉三角变换为直角三角形的形式进行观察，那么，每一个元素都是其上方元素和其上方元素的前一个元素的和。

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new ArrayList<>(); //定义二维顺序表List<Integer> row = new ArrayList<>(); //定义每一行的顺序表//因为第一行只有一个元素，对第一行单独处理row.add(1);list.add(row);//代码运行至此，杨辉三角第一行处理完毕//以下代码，对第二行及以后行数 进行处理for(int i = 1; i < numRows; i++) {List<Integer> curRow = new ArrayList<>(); //每一行一个顺序表curRow.add(1); //顺序表的第一个元素List<Integer> preRow = list.get(i - 1); //获取上一行for(int j = 1; j < i; j++) {int x = preRow.get(j) + preRow.get(j - 1);curRow.add(x);}curRow.add(1); //顺序表的最后一个元素list.add(curRow); //添加到二维顺序表中}return list;}
}

3.简单的洗牌算法

现在有这样一个场景：有一副新的扑克牌（排除大小王），三个人玩，先开始洗牌，然后一人抓一张，抓五轮，看每个人都抓到的是什么牌：

我们先对牌进行定义：

public class Card {public String suit; //花色public int rank; //数字public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {
//        return "Card{" +
//                "suit='" + suit + '\'' +
//                ", rank=" + rank +
//                '}';return suit + rank;}
}

接下来，我们依次完成定义一副新的牌、洗牌、发牌操作：

public class CardList {public static final String[] SUITS = {"♠", "♥", "♦", "♣"}; //定义四种花色//定义一副新的牌public static List<Card> newCard() {//用顺序表存放牌List<Card> list = new ArrayList<>();for (int i = 0; i < SUITS.length; i++) {for (int j = 1; j <=13 ; j++) {Card card = new Card(SUITS[i], j);list.add(card);}}return list;}//洗牌public static void washCard(List<Card> list) {//生成随机数交换牌，达到洗牌的目的Random random = new Random();for (int i = list.size() - 1; i > 0; i--) {int index = random.nextInt(i);swap(list, i, index);}}//交换牌private static void swap(List<Card> list, int i, int j) {Card tmp = list.get(i);list.set(i, list.get(j));list.set(j, tmp);}public static void main(String[] args) {List<Card> list = newCard();System.out.println(list);washCard(list);System.out.println(list);//用来存放三个人各自的牌List<Card> p1 = new ArrayList<>();List<Card> p2 = new ArrayList<>();List<Card> p3 = new ArrayList<>();//存放三个人List<List<Card>> p = new ArrayList<>();p.add(p1);p.add(p2);p.add(p3);//发牌for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = list.remove(0);p.get(j).add(card);}}System.out.println("A的牌：" + p.get(0));System.out.println("B的牌：" + p.get(1));System.out.println("C的牌：" + p.get(2));System.out.println("剩的牌：" + list);}
}

一个简单的洗牌算法就完成啦。

五、ArrayList小结

ArrayList底层是数组实现的，所以在进行有关查找的操作时，速度很快；但也是因为底层是数组实现的，这也导致了在进行增加或者删除操作时，需要逐个移动元素，效率很低，速度慢；在进行扩容操作时，1.5倍的扩容大小也可能会导致很多空间的浪费。

---

Ending。