Java 数据结构：ArrayList 与顺序表详解

二、ArrayList 简介

2.1. ArrayList 的构造

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //第一种方式，创建 ArrayList 对象，构造空的顺序表
        ArrayList<String> arrayList1 = new ArrayList<>();
        //第二种方式
        List<String> list = new ArrayList<>();
    }
}

其中 ArrayList 里面，也是实现了 List 的接口。也就是说，我们完全可以通过向上转型，把 List 引用指向 ArrayList 的实例。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

我们来看下面两段代码，两个都是构造空的顺序表，二者有什么区别呢？第一个是创建了一个盒子，盒子里面为空，而第二个却连盒子都没有。

ArrayList<String> arrayList1 = new ArrayList<>();
ArrayList<String> arrayList2 = null;

//使用 arrayList1 复制一份，生成 arrayList3
ArrayList<String> arrayList3 = new ArrayList<>(arrayList1);

//构造的同时，可以去指定初始容量
ArrayList<String> arrayList4 = new ArrayList<>(10);

当前构造出来的 ArrayList 初始容量为 10，这里与数组的区别是：数组我们在一开始就规定好了它的容量，不能在进行修改了；而 ArrayList 的容量可以进行动态扩容，只要机器内存允许，就能一直扩容，把想要的元素容纳进去。

2.2. ArrayList 的常见操作

（1）add 尾插操作

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        System.out.println(list);
    }
}

（2）获取元素个数

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //获取元素个数，数组提供了.length 属性获取到元素个数，集合类提供了 size() 方法获取元素个数
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        System.out.println(list.size());
    }
}

事实上，不仅是 List，只要是集合类，都可以通过.size 来获取长度。

（3）ArrayList 的访问和修改

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //获取或者设置 list 中的元素
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");//进行了自动扩容
        System.out.println(list.get(0));
        System.out.println(list.get(1));
        System.out.println(list.get(2));
        System.out.println(list.get(3));
        //System.out.println(list.get(4)); // 此时会出现下标越界访问的异常
    }
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //获取或者设置 list 中的元素
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");//进行了自动扩容
        list.set(0,"eee");
        System.out.println(list);
    }
}

（4）ArrayList 的遍历

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("aaa");
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");
        //遍历是可能会进行各种操作的，不一定是打印
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        //for-each 写法
        for (String s : list) {
            System.out.print(s+" ");
        }
    }
}

并不是所有的类都能写进 for-each 里面，要求这个类必须能够实现 Iterable 接口。实现 Iterable 接口中的 iterator 方法，得到一个迭代器对象，进行进一步循环遍历。

public interface List<E> extends Collection<E>

public interface Collection<E> extends Iterable<E> 

Iterator<E> iterator();

迭代也是计算机中的专业术语，可以理解成'逐渐接近目标'。集合类中用到迭代。上面的 for-each 循环，我们可以看作是以下代码的简化。

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

hasNext 用于判断有没有下一个元素，iterator.next 用于取出当前元素，并准备下一个元素。

（5）其他的一些操作

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        //通过 contains 判断元素是否存在
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ccc");
        list1.add("ccc");
        list1.add("ddd");
        System.out.println(list1.contains("aaa"));
        //通过 indexOf 获取元素第一次出现的位置
        System.out.println(list1.indexOf("ccc"));
        //通过 lastIndexOf 获取元素最后一次出现的位置
        list1.lastIndexOf("ccc");
        
        //按照元素内删除
        removeByElement(args);
        //按照下标删除元素
        removeByIndex(args);
        //在任意位置添加元素
        addAtPosition(args);
    }

    public static void removeByElement(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ddd");
        list1.remove("ddd");
        System.out.println(list1);
    }

    public static void removeByIndex(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ddd");
        list1.remove(2);
        System.out.println(list1);
    }

    public static void addAtPosition(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("aaa");
        list1.add("bbb");
        list1.add("ccc");
        list1.add("ddd");
        list1.add(1,"eee");
        System.out.println(list1);
    }
} 

2.3. ArrayList 的扩容机制

当 ArrayList 内存不够时，就会自动申请额外的内存空间。ArrayList 内部持有一个数组，设置的初始容量相当于数组的大小。比如说我们初始容量为 10，当循环到第 11 次的时候，发现元素已经满了；add 真正写进元素之前，就要创建一个更大的数组。新的数组要把旧的数组里的元素添加进来，新的元素也要添加进新的数组里面，原来旧的数组要进行释放。

三、ArrayList 的具体使用

3.1. 洗牌算法

问题描述：现有一副扑克牌，对其进行洗牌。

我们先来定义一个 Card 类，用来表示一张扑克牌。

class Card {
    public String suit;//表示花色
    public String rank;//表示点数
    public Card(String suit, String rank) {
        this.suit = suit;
        this.rank = rank;
    }
    public String getSuit() { return suit; }
    public void setSuit(String suit) { this.suit = suit; }
    public String getRank() { return rank; }
    public void setRank(String rank) { this.rank = rank; }
    @Override
    public String toString() { return this.suit+this.rank; }
}

接下来要先把 Card 这个对象实例化，并用 ArrayList 把所有的牌添加进去。

public class Main {
    public static void main(String[] args) {
        //使用 ArrayList 表示一副扑克牌
    }
    public static ArrayList<Card> CreateDeck() {
        //创建一副扑克牌
        ArrayList<Card> deck = new ArrayList<>();
        String[] suits = {"♠","♦","♥","♣"};
        //通过两层 for 循环，第一层先循环花色，第二层在循环点数
        //每个花色中，生成对应的点数
        for (String suit:suits){
            for (int i = 2; i <= 10; i++) {
                Card cardNum = new Card(suit,""+i);
                deck.add(cardNum);//添加到扑克牌中
            }
            Card cardJ = new Card(suit,"J");
            Card cardQ = new Card(suit,"Q");
            Card cardK = new Card(suit,"K");
            Card cardA = new Card(suit,"A");
            deck.add(cardJ);
            deck.add(cardQ);
            deck.add(cardK);
            deck.add(cardA);
        }
        return deck;
    }
}

然后我们调用 CreateDeck 方法，对这副牌进行一个打印。

public class Main {
    public static void main(String[] args) {
        //使用 ArrayList 表示一副扑克牌
        ArrayList<Card> deck = CreateDeck();
        System.out.println(deck);
    }
}

接下来是进行洗牌的操作，在 Java 标准库中，提供了进行洗牌的方法 shuffle。

import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        //使用 ArrayList 表示一副扑克牌
        ArrayList<Card> deck = CreateDeck();
        System.out.println("原始牌组:"+deck);
        //洗牌
        Collections.shuffle(deck);
        System.out.println("洗牌之后:"+deck);
    }
}

我们也可以自己写一个方法，来进行洗牌。

public static void shuffle(ArrayList<Card> deck){
    //把整个 ArrayList 从后往前遍历
    //每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换
    Random random = new Random();
    for (int i = deck.size() - 1; i >0 ; i--) {
        int j = random.nextInt(deck.size());//生成随机下标 [0,deck.size)
        //交换操作
        Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保 tmp 拿到 i 的下标，不能交换的时候发生修改
        deck.set(i, deck.get(j));
        deck.set(j, tmp);
    }
}

下面是发牌，一共有 3 个人，每个人发 5 张牌。我们可以看成一个 3 行 5 列的一个二维数组。

ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组
//先创建 3 个人手里的牌
for (int i = 0; i < 3; i++) {
    ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌
    hands.add(hand);//发到每个人手里
    //已经添加了 3 个元素进去，但还是长度为 0 的 ArrayList
}

最后是发牌的过程。

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 3; j++) {
        //发牌是轮流的过程.
        ArrayList<Card> currentHand = hands.get(j);
        Card card = deck.remove(0);
        currentHand.add(card); //一次循环，相当于取出一张牌交给玩家
    }
}

完整代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

class Card {
    public String suit;//表示花色
    public String rank;//表示点数
    public Card(String suit, String rank) {
        this.suit = suit;
        this.rank = rank;
    }
    public String getSuit() { return suit; }
    public void setSuit(String suit) { this.suit = suit; }
    public String getRank() { return rank; }
    public void setRank(String rank) { this.rank = rank; }
    @Override
    public String toString() { return this.suit+this.rank; }
}

public class Main {
    public static void main(String[] args) {
        //使用 ArrayList 表示一副扑克牌
        ArrayList<Card> deck = CreateDeck();
        System.out.println("原始牌组:"+deck);
        //洗牌
        //Collections.shuffle(deck);
        System.out.println("洗牌之后:"+deck);
        
        ArrayList<ArrayList<Card>> hands = new ArrayList<ArrayList<Card>>();//构成一个二维数组
        //先创建 3 个人手里的牌
        for (int i = 0; i < 3; i++) {
            ArrayList<Card> hand = new ArrayList<>();//每一个人的手牌
            hands.add(hand);//发到每个人手里
            //已经添加了 3 个元素进去，但还是长度为 0 的 ArrayList
        }
        
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                //发牌是轮流的过程.
                ArrayList<Card> currentHand = hands.get(j);
                Card card = deck.remove(0);
                currentHand.add(card); //一次循环，相当于取出一张牌交给玩家
            }
        }
        //打印每个人的手牌
        for (int i = 0; i < 3; i++) {
            System.out.println("第"+i+"个人的手牌"+hands.get(i));
        }
    }
    
    public static void shuffle(ArrayList<Card> deck){
        //把整个 ArrayList 从后往前遍历
        //每次取一张牌，生成一个随机下标，用当前的拍和随机下标的牌进行交换
        Random random = new Random();
        for (int i = deck.size(); i >0 ; i--) {
            int j = random.nextInt(deck.size());//生成随机下标 [0,deck.size)
            //交换操作
            Card tmp = new Card(deck.get(i).getSuit(), deck.get(i).getRank());//必须要确保 tmp 拿到 i 的下标，不能交换的时候发生修改
            deck.set(i, deck.get(j));
            deck.set(j, tmp);
        }
    }
    
    public static ArrayList<Card> CreateDeck() {
        //创建一副扑克牌
        ArrayList<Card> deck = new ArrayList<>();
        String[] suits = {"♠","♦","♥","♣"};
        //通过两层 for 循环，第一层先循环花色，第二层在循环点数
        //每个花色中，生成对应的点数
        for (String suit:suits){
            for (int i = 2; i <= 10; i++) {
                Card cardNum = new Card(suit,""+i);
                deck.add(cardNum);//添加到扑克牌中
            }
            Card cardJ = new Card(suit,"J");
            Card cardQ = new Card(suit,"Q");
            Card cardK = new Card(suit,"K");
            Card cardA = new Card(suit,"A");
            deck.add(cardJ);
            deck.add(cardQ);
            deck.add(cardK);
            deck.add(cardA);
        }
        return deck;
    }
}

3.2. 杨辉三角

问题描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2: 输入: numRows = 1 输出: [[1]]

通过上面的图，我们可以总结出以下规律：1.第 i 行有 i+1 个列 (因为要用二维数组解决，所以把第一行定义第 0 行)；2.每一行的第一列和最后一列都是 1；3.第 i 行第 j 列的元素 = 第 i-1 行第 j-1 列的元素 + 第 i-1 行第 j 列的元素。

完整代码：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public List<List<Integer>> generate(int numRows) {
        //先写一个表示结果的二维数组
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //先来构造行
        for (int i = 0; i < numRows; i++) {
            List<Integer> rows = new ArrayList<>();//用到了向上转型。需要往这一行里面里面添加元素
            for (int j = 0; j < i+1; j++) {
                if (j==0 || j==i){
                    rows.add(1);
                } else {
                    List<Integer> prevRow = result.get(i - 1);
                    int current = prevRow.get(j - 1) + prevRow.get(j);
                    rows.add(current);
                }
            }
            //一行构造好了之后，把这一行添加到 result 中
            result.add(rows);
        }
        return result;
    }
    
    public static void main(String[] args) {
        Main m = new Main();
        Scanner num = new Scanner(System.in);
        int b = num.nextInt();
        List<List<Integer>> result = m.generate(b);
        System.out.println(result);
    }
}