目录
一、ArrayList简介
二、ArrayList源码介绍(动态扩容以及构造方法是如何实现的)
1. 扩容机制:
源码:
源码详解: 编辑
如何扩容:
2. 扩容源码详解:
三、ArrayList的构造方法
四、ArrayList的几种遍历方式
五、ArrayList练习
1. 实现洗牌算法
2. 杨辉三角
常见的线性表结构:顺序表,链表,栈,队列。(线性表在逻辑上是线性结构,也就是一条线,但是在物理结构上不一定是连续的,通常是以数组和链表的形式存储)
顺序表:用一段物理地址连续的存储空间来存储数据元素,一般采用数组存储。
一、ArrayList简介
在集合框架中,ArrayList是一个类,实现了List接口:
1. ArrayList是以泛型的方式实现的,使用时必须先实例化 |
2. ArrayList实现了randomAccess接口,所以ArrayList支持随机访问 |
3. ArrayList实现了Cloneable接口,ArrayList时可以克隆的 |
4. ArrayList不是线程安全的,(Vector是线程安全的) |
5. ArrayList是一段连续的空间,可以动态扩容,是动态的顺序表 |
二、ArrayList源码介绍(动态扩容以及构造方法是如何实现的)
1. 扩容机制:
public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);
}
源码:
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
如下代码;当我们new一个ArrayList数组的时候,我们可以看到ArrayList的源码,此时并没有开辟一块内存空间,而是new了一个空的数组,所以应该是在add第一个数据元素的时候开辟的空间,我们需要再看一下add() 方法的源码:
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 void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}
2. 扩容源码详解:
三、ArrayList的构造方法
ArrayList( ) | 无参数构造 |
ArrayList(Collection<? extends E> c) | 只要实现了Collection接口的类都可以作为这个构造方法的参数 |
ArrayList(int initialCapacity) | 指定顺序表初始容量 |
构造方法的演示:
public static void main(String[] args) {//无参构造,在第一次add元素时给初始容量大小是10,扩容按1.5倍扩容ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);//可以传参一个实现了Collection接口的类的实例化对象LinkedList<Integer> linkedList = new LinkedList<>();//可以传参一个具体的对象,之后这个ArrayList1数组就包含了这个LinkedList中的数据ArrayList<Integer> arrayList1 = new ArrayList<>(linkedList);//带一个参数的构造:这个参数多大,这个数组的初始化容量就是多大ArrayList<Integer> arrayList2 = new ArrayList<>(20);
}
四、ArrayList的几种遍历方式
1. 直接打印输出,因为在父类AbstractCollection中重写了toString()方法 |
2. for循环遍历数组中的元素 |
3. for each循环遍历数组中的元素 |
4. Iterator迭代器循环遍历数组中的元素 |
public static void main(String[] args) {//无参构造,在第一次add元素时给初始容量大小是10,扩容按1.5倍扩容List<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);//直接遍历:在AbstractCollection中重写了toString方法System.out.println(arrayList);//for循环遍历for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i) + " ");}//for each遍历System.out.println();for (Integer x : arrayList) {System.out.print(x + " ");}//迭代器的遍历Iterator<Integer> it = arrayList.listIterator();while (it.hasNext()) {System.out.println(it.next() + " ");}
}
五、ArrayList练习
1. 实现洗牌算法
package PokerGame;public class Poker {//定义花色private String suit;//数字private int rank;public Poker(String suit, int rank) {this.suit = suit;this.rank = rank;}public String getSuit() {return suit;}public void setSuit(String suit) {this.suit = suit;}public int getRank() {return rank;}public void setRank(int rank) {this.rank = rank;}@Overridepublic String toString() {return "{" + suit + " " + rank + "}";}
}
package PokerGame;import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class Game {private static final String[] suits = {"♥", "♣", "♦", "♠"};public List<Poker> buyPoker() {List<Poker> pokers = new ArrayList<>();//每一张Poker都需要有四种颜色for (int i = 0; i < 4; i++) {//每一种颜色都需要生成13张牌for (int j = 1; j <= 13; j++) {Poker poker = new Poker(suits[i],j);pokers.add(poker);}}return pokers;}public void shuffle(List<Poker> pokers) {for (int i = pokers.size() - 1; i > 0; i--) {Random random = new Random();int index = random.nextInt(i);//这里就是生成一个0-51的随机数//交换: 生成一个随机数,从最后一张牌开始和前边的牌交换swap(pokers,i,index);}}private void swap(List<Poker> pokers,int i, int j) {Poker tmp = pokers.get(i);pokers.set(i,pokers.get(j));//这里调用的是List的set方法pokers.set(j,tmp);}public List<List<Poker>> game(List<Poker> pokers) {List<List<Poker>> hand = new ArrayList<>();List<Poker> hand1 = new ArrayList<>();List<Poker> hand2 = new ArrayList<>();List<Poker> 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++) {Poker removePoker = pokers.remove(0);hand.get(j).add(removePoker);}}return hand;}
}
package PokerGame;import java.util.List;public class Text {public static void main(String[] args) {Game game = new Game();List<Poker> pokers = game.buyPoker();System.out.println(pokers);//洗牌System.out.println("洗牌:");game.shuffle(pokers);//System.out.println(pokers);//揭牌:List<List<Poker>> hand = game.game(pokers);System.out.println("揭牌:");for (int i = 0; i < hand.size(); i++) {System.out.println("第"+(i+1)+"个人的牌:"+hand.get(i));}//剩下的牌System.out.println(pokers);}
}
2. 杨辉三角
//杨辉三角public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();List<Integer> row = new ArrayList<>();row.add(1);ret.add(row);for (int i = 1; i < numRows; i++) {//i就是行的下标List<Integer> prevRow = ret.get(i-1);List<Integer> curRow = new ArrayList<>();curRow.add(1);//第一个1//中间的数值for (int j = 1; j < i; j++) {//j就是列的下标int x = prevRow.get(j) + prevRow.get(j - 1);curRow.add(x);}curRow.add(1);ret.add(curRow);}return ret;}