【数据结构】(5) ArrayList 顺序表

一、使用 ArrayList

        ArrayList 就是数组的封装，但是数组只有 [] 操作存取值，和 .length 操作获取数组内存长度；而 ArrayList 有更多的功能：

1、创建对象

2、扩容机制

        ArrayList 有自动扩容机制，在插入元素时不用担心数组容量是否足够。创建对象时，数组容量默认为为 10，容量不够时，每次扩容都会乘以 1.5 倍。源码如下：

        调用无参构造函数，数组初始化为空数组：

        第一次添加一个元素：

        进入 calculateCapacity 计算需用数组长度：

        计算得到需用数组长度为 10：

        此时，10 > 0，数组容量不够，需要扩容：

        若添加元素时，触发扩容机制（即 Arrays.copyOf ），过程如下：

• 创建一个新的数组，长度比原来大。
• 将旧数组的元素拷贝到新数组中。
• 添加新的元素到新数组中。
• 释放旧数组的空间。

        可以看到扩容存在拷贝操作，需要遍历旧数组中的元素，因此效率低下。故创建对象时应设置一个合适的大小，避免频繁扩容。

        从上面的源代码可以看到，Arrays.copyOf 方法，创建了 newCapacity 容量的新数组，并把旧数组 elementData 复制到新数组中，并返回新数组。

3、插入一个元素

.addAll(list)：把 list 中的所有元素添加到末尾。

        总结一下获取数组长度的方法：

• 数组为 .length
• String 为 .length()
• 集合类 为 .size()

        同样的作用却有不同的名字，这是在以后开放中需要避免的，我们应该统一风格。

4、获取、设置一个元素

5、遍历元素

        使用 for 循环或 for-each，重点讲 for-each。回顾集合类框架，集合接口 Collection 继承了可迭代的接口 Iterable：

        因此实现了 Iterable 接口的 iterator 方法的集合类，可通过对象调用 iterator 方法得到一个迭代器。ArrayList 实现 iterator 方法的源码如下：

        手动实现遍历：

        迭代器的效果等价于 for-each，因此实现了 Iterable 接口的 iterator 方法的类，都是可迭代的，即可使用 for-each 语句的。

6、删除一个元素

7、获取一个元素的位置

8、判断是否包含一个元素

        源码使用了 indexOf：

9、获取子列表

        若想避免子列表牵动父列表，应创建新的列表：

10、清空元素

        Java 中存在垃圾回收机制，JVM会自动回收没被引用的内存空间，不需要手动地释放元素所占空间（如 C 中的 free）。

二、ArrayList 的使用练习

1、实现简单的洗牌算法

        Card 类，对象表示一张牌，存有花色和牌值：

class Card {
    String suit; // 花色
    String value; // 牌值

    public Card(String suit, String value) {
        this.suit = suit;
        this.value = value;
    }

    public String getSuit() {
        return suit;
    }

    public String getValue() {
        return value;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return this.suit + this.value;
    }
}

        主类中 createPokerCards 方法，创建一副新牌：

    public static ArrayList<Card> createPokerCards() {
        ArrayList<Card> cards = new ArrayList<Card>();
        String[] suits = {"♠", "♥", "♦", "♣"};
        String[] values = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
        for (String suit : suits) {
            for (String value : values) {
                cards.add(new Card(suit, value));
            }
        }
        return cards;
    }

         主类中 shufflePokerCards 方法，打乱扑克牌：

    public static void shufflePokerCards(ArrayList<Card> cards) {
        Random random = new Random();
        for (int i = 0; i < cards.size(); i++) {
            int j = random.nextInt(cards.size()); // 随机生成 j 位置
            // 交换 i 位置和 j 位置的牌
            Card temp = new Card(cards.get(i).getSuit(), cards.get(i).getValue()); // 创建新的对象，避免后续 temp 因 i 位置被 j 处覆盖而发生改变
            cards.set(i, cards.get(j));
            cards.set(j, temp);
        }
    }

        主类中 dealPokerCards 方法，发牌：

    public static ArrayList<ArrayList<Card>> dealPokerCards(ArrayList<Card> cards, int numPlayers) {
        ArrayList<ArrayList<Card>> hands = new ArrayList<>();
        // 创建 numPlayers 手空牌
        for (int i = 0; i < numPlayers; i++) {
            ArrayList<Card> hand = new ArrayList<>();
            hands.add(hand);
        }
        int numCards = cards.size() / numPlayers; // 每人手牌数
        // 给每人发牌
        for (int i = 0; i < numCards; i++) {
            for (int j = 0; j < numPlayers; j++) {
                Card card = cards.remove(0); // 取出第一张牌
                hands.get(j).add(card); // 给 j 号玩家发牌
            }
        }
        return hands;
    }

        主类中 printHands 方法，打印所有手牌：

    public static void printHands(ArrayList<ArrayList<Card>> hands) {
        for (ArrayList<Card> hand : hands) {
            System.out.println("手牌:" + hand);
        }
    }

        主逻辑：

    public static void main(String[] args) {
        // 创建扑克牌
        ArrayList<Card> cards = createPokerCards();
        System.out.println("新牌：" + cards);
        // 洗牌
        shufflePokerCards(cards);
        System.out.println("洗牌：" + cards);
        // 发牌
        ArrayList<ArrayList<Card>> hands = dealPokerCards(cards, 4);
        // 打印手牌
        printHands(hands);
    }

        结果：

2、打印杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

分析：

• 第 i (0 ~ numRows) 行有 i + 1 列。
• 每一行第一个和最后一个都为 1。
• 中间的第 j 个等于 [i-1][j-1] + [i-1][j] 。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> rows = new ArrayList<>(numRows);
        for(int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>(i + 1);
            for(int j = 0; j < i+1; j++) {
                if(j == 0 || j == i) {
                    row.add(1);
                }
                else {
                    List<Integer> lastRow = rows.get(i - 1);
                    row.add(lastRow.get(j - 1) + lastRow.get(j));
                }
            }
            rows.add(row);
        }
        return rows;
    }
}

三、自己实现一个 MyArrayList

1、功能实现

import java.util.Arrays;

/** 功能代码 **/
public class MyArrayList {
    private int[] arr;
    private int size = 0; // 已用容量

    // 构造函数, 默认容量为10
    public MyArrayList() {
        arr = new int[10];
    }

    // 构造函数, 指定容量
    public MyArrayList(int capacity) {
        arr = new int[capacity];
    }

    // 获取元素个数
    public int size() {
        return size;
    }

    // 扩容, 私有, 不需要暴露给外界
    private void resize() {
        // 创建一个新的数组, 容量为原来的1.5倍
        int oldCapacity = arr.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍; cpu 计算加减移位比乘除快
        // 创建新数组，并将原数组中的元素复制到新数组中
        arr = Arrays.copyOf(arr, newCapacity);
    }

    // 添加元素
    public void add(int val) {
        // 已满，扩容
        if (size == arr.length) {
            resize();
        }
        // 添加元素
        arr[size++] = val;
    }

    // 指定位置添加元素
    public void add(int index, int val) {
        // 超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        // 已满，扩容
        if (size == arr.length) {
            resize();
        }
        // 移动元素
        for (int i = size - 1; i >= index; i--) {
            arr[i + 1] = arr[i];
        }
        // 添加元素
        arr[index] = val;
        size++;
    }

    // 根据下标，获取元素
    public int get(int index) {
        // 超出范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return arr[index];
    }

    // 根据下标，设置元素
    public void set(int index, int val) {
        // 超出范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        arr[index] = val;
    }

    // 根据下标，删除元素，返回删除的元素
    public int remove(int index) {
        // 超出范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        int val = arr[index];
        // 移动元素
        for (int i = index; i < size - 1; i++) {
            arr[i] = arr[i + 1];
        }
        size--;
        return val;
    }

    // 根据值，删除元素
    public boolean delete(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                remove(i);
                return true;
            }
        }
        return false;
    }

    // 查找元素所在下标，不存在返回-1
    public int indexOf(int val) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }

    // 倒着查找元素所在下标，不存在返回-1
    public int lastIndexOf(int val) {
        for (int i = size - 1; i >= 0; i--) {
            if (arr[i] == val) {
                return i;
            }
        }
        return -1;
    }

    // 判断是否包含元素
    public boolean contains(int val) {
        return indexOf(val) >= 0;
    }

    // 清空元素
    public void clear() {
        size = 0;
    }

    // 打印元素
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(arr[i]);
            if (i < size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

2、单元测试

/** 单元测试 **/
class MyArrayListTest {
    // 测试1：构造函数和 add 方法 和 size 方法 和 toString 方法
    public static void test1() {
        MyArrayList list = new MyArrayList(3);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(1,4); // 自动扩容

        if (list.size() == 4) {
            System.out.println("test1 pass");
        }
        else {
            System.out.println("test1 fail");
        }

        if (list.toString().equals("[1, 4, 2, 3]")) {
            System.out.println("test1 pass");
        }
        else {
            System.out.println("test1 fail");
        }

        list.add(100,5); // 越界
    }

    // 测试2：get 方法 和 set 方法
    public static void test2() {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        if (list.get(0) == 1 && list.get(1) == 2 && list.get(2) == 3) {
            System.out.println("test2 pass");
        }
        else {
            System.out.println("test2 fail");
        }
        list.set(1, 100);
        if (list.get(1) == 100) {
            System.out.println("test2 pass");
        }
        else {
            System.out.println("test2 fail");
        }

        list.get(100); // 越界
        list.set(100, 100); // 越界
    }

    // 测试3：remove 方法 和 delete 方法
    public static void test3() {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.remove(2);

        if (list.toString().equals("[1, 2, 4, 5]")) {
            System.out.println("test3 pass");
        }
        else {
            System.out.println("test3 fail");
        }

        list.delete(4);
        if (list.toString().equals("[1, 2, 5]")) {
            System.out.println("test3 pass");
        }
        else {
            System.out.println("test3 fail");
        }

        if (!list.delete(100)) {
            System.out.println("test3 pass");
        }
        else {
            System.out.println("test3 fail");
        }

        list.remove(100); // 越界
    }

    // 测试4：indexOf 方法 和 lastIndexOf 方法 和 contains 方法 和 clear 方法
    public static void test4() {
        MyArrayList list = new MyArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2);

        if (list.indexOf(2) == 1 && list.lastIndexOf(2) == 3 && list.contains(2)) {
            System.out.println("test4 pass");
        }
        else {
            System.out.println("test4 fail");
        }

        if (list.indexOf(100) == -1 && list.lastIndexOf(100) == -1 && !list.contains(100)) {
            System.out.println("test4 pass");
        }
        else {
            System.out.println("test4 fail");
        }

        list.clear();
        if (list.size() == 0) {
            System.out.println("test4 pass");
        }
        else {
            System.out.println("test4 fail");
        }
    }

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
        test4();
    }
}

3、注意事项

• 顺序表是一个有序表，在实现添加一个元素时，不能直接将 index 处的元素移到最后面，再把新元素添加到 index 处；这样虽然避免了大量移动，但是打乱了顺序表的有序性，不符合要求。
• 顺序表的缺点：顺序表在中间插入和删除需要大量移动，时间复杂度为 O(N)；扩容也需要大量拷贝，降低效率；很有可能造成内存空间浪费。
• 后续的链表可以解决以上问题，但同样带来了其它的问题，总的来说还是 ArrayList 更常用。