文章目录
- 前言
- 1.ArrayList的简介
- 2. ArrayList使用
- 2.1.ArrayList的构造
- 2.2.ArrayList的扩容机制(JDK17)
- 3.ArrayList的常见操作
- 4. ArrayList的具体使用
- 4.1.[杨辉三角](https://leetcode.cn/problems/pascals-triangle/description/)
- 4.2.简单的洗牌游戏
- 5.ArrayList的问题及思考
前言
上一篇我们模拟实现了ArrayList的部分功能,现在我们讨论如何使用Java中自带的ArrayList方法。
1.ArrayList的简介
在集合框架中,ArrayList是一个普通的类,实现了List接口,具体框架图如下
【说明】
- ArrayList是以泛型方式实现的,使用时必须要先实例化
- ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问
- ArrayList实现了Cloneable接口,表明ArrayList是可以clone的
- ArrayList实现了Serializable接口,表明ArrayList是支持序列化的
- 和Vector不同,ArrayList不是线程安全的,在单线程下可以使用,在多线程中可以选择Vector或者
CopyOnWriteArrayList - ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表
2. ArrayList使用
2.1.ArrayList的构造
首先我们看一下这三个构造方法有什么区别
上面有个疑问,等会再解答。
2.2.ArrayList的扩容机制(JDK17)
为了解决这个问题,我们看一下add的源码,这样就可以明白扩容机制。
我们把上面的问题解决了,现在考虑扩容机制(即当数组满的时候,那么或扩充多少空间)
通过上述的分析,我们发现Java内部ArrayList扩容机制是扩充1.5倍
总结】
- 检测是否真正需要扩容,如果是调用grow准备扩容
- 预估需要库容的大小
初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小,则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功,防止太大导致扩容失败 - 使用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的问题及思考
- ArrayList底层使用连续的空间,任意位置插入或删除元素时,需要将该位置后序元素整体往前或者往后搬
移,故时间复杂度为O(N) - 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继
续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
思考: 如何解决以上问题呢?