Java(十七)---ArrayList的使用

---

前言

上一篇我们模拟实现了ArrayList的部分功能，现在我们讨论如何使用Java中自带的ArrayList方法。

---

1.ArrayList的简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下

【说明】

1. ArrayList是以泛型方式实现的，使用时必须要先实例化
2. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
3. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
4. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
5. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者
   CopyOnWriteArrayList
6. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

---

2. ArrayList使用

2.1.ArrayList的构造

首先我们看一下这三个构造方法有什么区别

上面有个疑问，等会再解答。

2.2.ArrayList的扩容机制(JDK17)

为了解决这个问题，我们看一下add的源码，这样就可以明白扩容机制。

我们把上面的问题解决了，现在考虑扩容机制(即当数组满的时候，那么或扩充多少空间)

通过上述的分析，我们发现Java内部ArrayList扩容机制是扩充1.5倍
总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容
2. 预估需要库容的大小
   初步预估按照1.5倍大小扩容
   如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
   真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容

---

3.ArrayList的常见操作

上面的方法主要讲最后一个

public static void main(String[] args) {ArrayList<Integer>list=new ArrayList<>();//add尾插list.add(1);list.add(2);list.add(3);//在指定位置插入list.add(2,4);for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();//subListList<Integer>list1=new ArrayList<>();list1=list.subList(2,4);for (int i=0;i<list1.size();i++){System.out.print(list1.get(i)+" ");}System.out.println();list.set(2,99);for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i)+" ");}System.out.println();for (int i=0;i<list1.size();i++){System.out.print(list1.get(i)+" ");}}

我们看一下结果：

这是为什么呢，我们调试一下

我们会发现，两个数组所指向的内存是一样的，因此使用set()方法，改的时候，两个数组对应的值都会发生变化。

---

4. ArrayList的具体使用

4.1.杨辉三角

这个题吗，如果使用数组的话，很好做，但是

必须要使用顺序表，并且List<List< Integer >>什么意思？
如果联想一下二维数组，不难知道，这是一个二维顺序表。

public List<List<Integer>> generate(int numRows) {List<List<Integer>>list=new ArrayList<>();//先把第一行填满List<Integer>list0=new ArrayList<>();list0.add(1);list.add(list0);//再把剩余的填满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 val1=preRow.get(j);int val2=preRow.get(j-1);curRow.add(val2+val1);}//最后一个curRow.add(1);list.add(curRow);}return list;}

4.2.简单的洗牌游戏

一副拍克牌，除去大小王，三个人完，洗完牌后，三个人轮流拿一张牌，拿五轮，写出算法。
Card类

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

CardDemo类

public class CardDemo {public static final String[]suits={"♣","♦","♥","♠"};public List<Card> buyCard(){List<Card>cards=new ArrayList<>(52);for (int i=0;i<4;i++){for (int j=1;j<=13;j++){int rank=j;String suit=suits[i];Card card=new Card(rank,suit);cards.add(card);}}return cards;}private void Swap(List<Card>cards,int i,int j){Card tmp=cards.get(i);cards.set(i,cards.get(j));cards.set(j,tmp);}//洗牌public void shuttle(List<Card>cards){Random random=new Random();for (int i = cards.size()-1; i >0 ; i--) {int index=random.nextInt(i);Swap(cards,i,index);}}//发牌public List<List<Card>> play(List<Card>cards){List<List<Card>>hand=new ArrayList<>(3);List<Card>hand1=new ArrayList<>();List<Card>hand2=new ArrayList<>();List<Card>hand3=new ArrayList<>();hand.add(hand1);hand.add(hand2);hand.add(hand3);for (int i=0;i<5;i++){for (int j=0;j<3;j++){Card card=cards.remove(0);hand.get(j).add(card);}}return hand;}
}

---

5.ArrayList的问题及思考

1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬
   移，故时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继
   续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
   思考： 如何解决以上问题呢?