数据结构青铜到王者第三话---ArrayList与顺序表（2）

续接上一话：

一、ArrayList的使用（续）

1、ArrayList的扩容机制（续）

五、ArrayList的相关练习

1、杨辉三角

2、简单的洗牌算法

六、ArrayList的问题及思考

一、ArrayList的使用（续）

1、ArrayList的扩容机制（续）

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：

 Object[] elementData;   // 存放元素的空间private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认空间private static final int DEFAULT_CAPACITY = 10;  // 默认容量大小public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {// 获取旧空间大小int oldCapacity = elementData.length;// 预计按照1.5倍方式扩容int newCapacity = oldCapacity + (oldCapacity >> 1);// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 调用copyOf扩容elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {// 如果minCapacity小于0，抛出OutOfMemoryError异常if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

总结：

（1）检测是否真正需要扩容，如果是调用grow准备扩容

（2）预估需要库容的大小

初步预估按照1.5倍大小扩容

如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容

真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

（3）使用copyOf进行扩容

五、ArrayList的相关练习

1、杨辉三角

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

分析：

这里就是外侧全是1，其他的分别是上面紧挨着的两个的加和。但是，显然我们不能像左图一样创建顺序表，可以转换成如右图所示的样式！！！如右图，最外侧都为1，若位置为（i，j）,则[i][j] = [i-1][j] + [i-1][j-1]

因此，我们创建一个空列表ret，用来存储所有的行（每行是一个整数列表）。

先处理第一行，元素为1；再循环生成一共numRows行，将每行的第一个元素添加为1。

利用上一行计算中间元素，最后添加上尾巴（1）。

class Solution {public static List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> list0 = new ArrayList<>();list0.add(1);ret.add(list0);//从第2行开始 进行求每个元素for (int i = 1; i < numRows; i++) {//处理第一个元素List<Integer> curRow = new ArrayList<>();curRow.add(1);//中间List<Integer> preRow = ret.get(i-1);for (int j = 1; j < i; j++) {int val1 = preRow.get(j);int val2 = preRow.get(j-1);curRow.add(val1+val2);}//尾巴curRow.add(1);ret.add(curRow);}return ret;}
}

2、简单的洗牌算法

（一副新牌，四种花色（♥，♦，♠，♣），数值分别为1--13，经过一系列的洗牌之后，分别发给三个人每人5张（轮流抓牌），最后展示剩余牌和三人手里的牌）

public class Card {private String suit;//花色private int rank;   //牌面值public Card(String suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {/*return "Card{" +"suit='" + suit + '\'' +", rank=" + rank +'}';*/return String.format("[%s %d]", suit, rank);}
}

import java.util.List;
import java.util.ArrayList;
import java.util.Random;public class CardDemo {public static final String[] suits = {"♥","♠","♣","♦"};//买来一副新牌public List<Card> buyCard() {List<Card> cardList = new ArrayList<>(52);for (int i = 1; i <= 13; i++) {for (int j = 0; j < 4; j++) {int rank = i;String suit = suits[j];Card card = new Card(suit,rank);cardList.add(card);}}return cardList;}//洗牌public void shuffle(List<Card> cardList) {Random random = new Random();for (int i = cardList.size()-1; i > 0 ; i--) {int index = random.nextInt(i);swap(cardList,i,index);}}private void swap(List<Card> cardList,int i,int j) {/*Card tmp =  cardList[i];cardList[i] = cardList[j];cardList[j] = tmp;*/Card tmp = cardList.get(i);cardList.set(i,cardList.get(j));cardList.set(j,tmp);}//分别发牌public List<List<Card>> play(List<Card> cardList) {List<Card> hand0 = new ArrayList<>();List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<List<Card>> hand = new ArrayList<>();hand.add(hand0);hand.add(hand1);hand.add(hand2);for (int i = 0; i < 5; i++) {for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);//怎么把对应的牌 放到对应的人的手里面hand.get(j).add(card);}}return hand;}
}

import java.util.*;
public class Test {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();//1. 买52张牌List<Card> cardList = cardDemo.buyCard();System.out.println("刚买回来的牌：");System.out.println(cardList);//2. 洗牌cardDemo.shuffle(cardList);System.out.println("洗过的牌:");System.out.println(cardList);//3. 3个人每个人轮流发牌5张List<List<Card>> ret = cardDemo.play(cardList);for (int i = 0; i < ret.size(); i++) {System.out.println("第"+(i+1)+"个人的牌："+ret.get(i));}System.out.println("剩下的牌：");System.out.println(cardList);}

运行程序可以得到类似的运行结果：

刚买回来的牌:
[[♠ 1], [♠ 2], [♠ 3], [♠ 4], [♠ 5], [♠ 6], [♠ 7], [♠ 8], [♠ 9], [♠ 10], [♠ 11], [♠ 12], [♠ 13], [♥ 1], [♥ 2], [♥ 3], [♥ 4], [♥ 5], [♥ 6], [♥ 7], 
[♥ 8], [♥ 9], [♥ 10], [♥ 11], [♥ 12], [♥ 13], [♣ 1], [♣ 2], [♣ 3], [♣ 4], [♣ 5], [♣ 6], [♣ 7], [♣ 8], [♣ 9], [♣ 10], [♣ 11], [♣ 12], [♣ 
13], [♦ 1], [♦ 2], [♦ 3], [♦ 4], [♦ 5], [♦ 6], [♦ 7], [♦ 8], [♦ 9], [♦ 10], [♦ 11], [♦ 12], [♦ 13]]
洗过的牌:
[[♥ 11], [♥ 6], [♣ 13], [♣ 10], [♥ 13], [♠ 2], [♦ 1], [♥ 9], [♥ 12], [♦ 5], [♥ 8], [♠ 6], [♠ 3], [♥ 5], [♥ 1], [♦ 6], [♦ 13], [♣ 12], [♦ 12], 
[♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦ 4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠ 
12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]]
第1个人的牌:[[♥ 11], [♣ 10], [♦ 1], [♦ 5], [♠ 3]]
第2个人的牌:[[♥ 6], [♥ 13], [♥ 9], [♥ 8], [♥ 5]]
第3个人的牌:[[♣ 13], [♠ 2], [♥ 12], [♠ 6], [♥ 1]]
剩下的牌:
[[♦ 6], [♦ 13], [♣ 12], [♦ 12], [♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦ 
4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠ 12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]]

六、ArrayList的问题及思考

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬移，故时间复杂度为O(N)

解决方案：

        使用LinkedList：链表结构插入删除时间复杂度为O(1)
        分段数组：将大数组分成多个小数组块
        树状数组：使用树形结构维护数据

链表+数组组合（Unrolled Linked List）
class Chunk {private static final int CHUNK_SIZE = 64;private Object[] data;private int size;private Chunk next;// 插入删除只在当前chunk内搬移数据// 大大减少数据移动量
}

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

解决方案：

        预分配策略：根据业务场景预估容量
        增量式扩容：每次只扩容部分空间
        内存池技术：预先申请大块内存
        使用链表结构：完全避免扩容问题

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

解决方案：

        更合理的扩容因子：1.5倍或其他经验值
        缩容机制：当空间利用率低于阈值时自动缩容
        弹性数组：动态调整容量
        内存碎片整理：定期整理内存空间

弹性数组（弹性扩容因子）
class ElasticArrayList<T> {private static final double GROW_FACTOR = 1.5;private static final double SHRINK_THRESHOLD = 0.3;private Object[] elementData;private int size;// 根据使用情况动态调整扩容因子private int calculateNewCapacity(int minCapacity) {if (size < 1000) return (int)(size * 1.8);else if (size < 10000) return (int)(size * 1.5);else return (int)(size * 1.2);}// 自动缩容机制public void trimToUsage() {if (size < elementData.length * SHRINK_THRESHOLD) {elementData = Arrays.copyOf(elementData, size);}}
}