目錄
1、ArrayList
2、ArrayList構造方法
3、ArrayList常見方法
4、ArrayList的遍歷
5、ArrayList的擴容機制
6、ArrayList的具體使用
6.1、楊輝三角
6.2、簡單的洗牌算法
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構造方法
底層代碼分析：
1. 帶一個參數的構造方法，初始化 ArrayList 時可以指定初始容量
2. 不帶參數的構造方法，初始化時分配的是一個空數組
既然沒有分配內存，那這個 ArrayList 對象是如何存數據的呢？
^
繼續查看 add 方法的原碼,得出結論：
結論1：雖然初始化時沒有分配內存，但是第一次 add 的時候會分配大小為10的內存
結論2：對于ArrayList來說，當容量滿了，采用的擴容方式是1.5倍擴容
^
3. 有通配符的構造方法
參數列表的含義：
Collection：表示傳入的參數是?Collection 類型的，實現了Collection接口的類型也可以
<? extends E>：通配符上界，這里表示可以傳入的參數類型是 E 或者 E 的子類
^
例如：
ArrayList<Integer> list?= new ArrayList<>();
ArrayList<Number> list1?= new ArrayList<>(list);
首先，list 是實現了 Collection 接口的，？：Integer ；E：?Number，Integer 是?Number 的子類，list 滿足這兩個條件，所以可以作為參數正確執行。相當于把 list 表中數據打包給到 list
public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);ArrayList<Number> list2 = new ArrayList<>(list1);list2.add(99);list2.add(88);System.out.println(list2); // 輸出 [1,2,3,99,88]}
3、ArrayList常見方法
public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);ArrayList<Number> list123 = new ArrayList<>();list123.addAll(list); // 與上述第三個構造方法類似System.out.println(list123);//123list123.remove(2); // 刪除 2 位置元素list123.remove(new Integer(2)); // 刪除遇到的第一個 2System.out.println(list123);//23list123.get(0);list123.set(1,2);list123.contains(1);list.add(4);list.add(5);//并不會產生新的對象！List<Integer> list1 = list.subList(1,3); // [1,3)System.out.println(list1);System.out.println("==============");list1.set(0,99);System.out.println(list1);System.out.println(list);}上述?subList 方法執行結果：
list1：??[99,3]
list：??? [1, 99, 3,4, 5]
發現通過 list1 修改，list 也會發生改變，所以?subList 的執行過程并不會產生新的對象，在這個案例中，list1 的起始位置指向 list 的 1 下標
4、ArrayList的遍歷
1.?for循環+下標
public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);// 使用下標+for遍歷for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println(); }2.?foreach
^
for(Integer x : list) {
? ? System.out.print(x+" ");}
System.out.println();
3. 迭代器
只有實現了 literable 接口的類型，才能使用迭代器；Map 就不能使用，因為他沒有實現 literable 接口
Iterator<Integer> it = list.iterator();? ? --? 通用迭代器
Iterator<Integer> it = list.listIterator();? ? --? List 的專屬迭代器
^
//使用 迭代器 遍歷集合類 list
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
? ? System.out.println(it.next()+" ");}
注意：ArrayList最長使用的遍歷方式是：for循環+下標 以及 foreach?
5、ArrayList的擴容機制
在上述構造方法中，通過查看 add 方法的底層代碼得出結論：ArrayList是一個動態類型的順序表，即：在插入元素的過程中會自動擴容
底層代碼總結：
1. 檢測是否真正需要擴容，如果是調用grow準備擴容
2. 預估需要庫容的大小
- 初步預估按照1.5倍大小擴容
- 如果用戶所需大小超過預估1.5倍大小，則按照用戶所需大小擴容
- 真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗
3. 使用copyOf進行擴容
6、ArrayList的具體使用
6.1、楊輝三角
力扣118
分析 List<List<Integer>>?
class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<>();// 1. 先處理第一行List<Integer> list = new ArrayList<>();list.add(1);ret.add(list);// 2. 從第2行開始計算 每個list當中的數據for(int i = 1;i < numRows;i++) {// 3. 先準備當前行數據List<Integer> curRow = new ArrayList<>();// 4. 準備當前行的第一個數據curRow.add(1);// 5. 準備當前的中間數據List<Integer> prevRow = ret.get(i-1); // 拿到上一行的數據for(int j = 1; j < i;j++) {// 上一行的當前列 + 上一行的前一列int val = prevRow.get(j) + prevRow.get(j-1);curRow.add(val);}// 6. 準備當前行最后一個數據curRow.add(1);// 7. 把這個數據放到二維數組當中去ret.add(curRow);}return ret;} }
6.2、簡單的洗牌算法
實現這個算法要解決的問題：
1.買一副牌【要生成一副撲克牌】放到哪里？
2.洗牌，怎么洗?
3.揭牌，每個人輪流抓5張牌，怎么抓牌?抓的牌放到哪里？
1. 創建一個 card 類，定義 花色 和 數字 兩個屬性；生成 get 和 set 方法；生成toString方法
package card;public class Card {private String suit;//花色private int rank;//數字public Card(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+" ";} }
2. 創建 CardDemo 和 Test 類；CardDemo類中定義一個買牌的方法，在Test類中測試
? ? 一共52張牌 1-k，其中1對應A、J對應11、Q對應12、K對應13
?3. 在CardDemo 類中再定義一個花色類，并完善buyCard方法
4. 買完牌后洗牌，這里使用生成隨機數的方式，從最后一張牌開始，與隨機生成的牌交換
5. 揭牌，3個人每人輪流揭5張，每次揭1張
把三個人的關系用一個二維數組表示
每揭一張牌，就把整副牌的0下標位置刪除
CardDemo 類的完整代碼
public class CardDemo {private final String[] suits = {"?","?","?","?"};/*** 52張 1-K* J Q K* 11 12 13* @return*/public List<Card> buyCard() {List<Card> cardList = new ArrayList<>();for (int i = 0; i < 4; i++) {for (int j = 1; j <= 13; j++) {Card card = new Card(suits[i],j);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);//index i 交換swap(cardList,i,index);}}private void swap(List<Card> cardList,int a,int b) {Card tmp = cardList.get(a);cardList.set(a,cardList.get(b));cardList.set(b,tmp);/*** tmp = a* a = b* b = tmp*/}/*** 揭牌* 3個人 每個人輪流揭牌5張* @param cardList*/public void getCard(List<Card> cardList) {List<Card> hand1 = new ArrayList<>();List<Card> hand2 = new ArrayList<>();List<Card> hand3 = new ArrayList<>();List<List<Card>> hands = new ArrayList<>();hands.add(hand1);hands.add(hand2);hands.add(hand3);//3個人 輪流抓牌5張 每次揭牌1張for (int i = 0; i < 5; i++) {//j代表人for (int j = 0; j < 3; j++) {Card card = cardList.remove(0);hands.get(j).add(card);}}System.out.println("第1個揭牌如下：");System.out.println(hand1);System.out.println("第2個揭牌如下：");System.out.println(hand2);System.out.println("第3個揭牌如下：");System.out.println(hand3);System.out.println("剩下的牌：");System.out.println(cardList);}
}Test 類中代碼
public class Test {public static void main(String[] args) {CardDemo cardDemo = new CardDemo();List<Card> cardList = cardDemo.buyCard();System.out.println("買的牌如下：");System.out.println(cardList);System.out.println("洗牌：");cardDemo.shuffle(cardList);System.out.println(cardList);System.out.println("揭牌：");cardDemo.getCard(cardList);}
}7、順序表的優缺點
缺點：
- 插入數據必須移動其他數據，最壞情況下，就是插入到0位置。時間復雜度O(N)
- 刪除數據也需要移動數據，最壞情況下，就是刪除0位置。時間復雜度O(N)
- 擴容之后有可能會浪費空間
優點：在給定下標進行查找的時候，時間復雜度O(1)
總結：順序表比較適合進行給定下標查找的場景。
)
 算法詳解與PyTorch實現)