1.順序表的創建? ? ? ? ? ? ? ? ?2.常見操作? ? ? ? ? ? ? ? ? ?3.遍歷? ? ? ? ? ? ? ? ? 4.擴容機制? ? ? ? ? ? ? ? ? 5.例子
1.順序表的創建
在集合框架中,ArrayList是?個普通的類,實現了List接口,具體框架圖如下:
2.常見操作
代碼實現
import java.util.ArrayList;
import java.util.List;public class Test1 {public static void main(String[] args) {//ArrayList<Integer> arrayList1 = new ArrayList<>();List<Integer> list = new ArrayList<>();//尾插 List 是可以直接打印的. 不像數組, 還需要轉成 Stringlist.add(1);list.add(2);list.add(3);list.add(4);list.add(2);System.out.println(list);// add 也可以指定位置來插入. 往下標 2 這個元素之前插入 100. 插入成功之后, 100 元素的下標就是 2 .list.add(2,100);System.out.println(list);// 頭插list.add(0, 200);System.out.println(list);// list.add(100, 300); 顯然不行. 100 下標太大了.下標越界了;但是可以往 6 這個位置插入. 就相當于尾插.list.add(6, 300);System.out.println(list);//插入一組元素List<Integer> list1 = new ArrayList<>();list1.addAll(list);System.out.println(list1);//按照下標刪除 但下標不能超出總長度范圍 也可以同時記錄一下被刪除的元素 返回resultInteger result = list.remove(1);System.out.println(list);System.out.println(result);//按照值來刪除 下標也不能超出指定的范圍 如果 List 中不包含這個值, 就返回 falseboolean isRemoved = list.remove(Integer.valueOf(1));System.out.println(list);System.out.println(isRemoved);// 雖然是刪除 2 這個值, 由于有多個, 實際上只刪除了第一個.list.remove(Integer.valueOf(2));System.out.println(list);//但這樣可以刪除所有2List<Integer> toRemove = new ArrayList<>();toRemove.add(2);list.removeAll(toRemove);System.out.println(list);//獲取元素System.out.println(list.get(1));//修改元素list.set(0,100);System.out.println(list);//清空list1.clear();System.out.println(list1);//判斷某元素是否存在System.out.println(list.contains(3));//返回第一個元素所在的下標System.out.println(list.indexOf(100));//返回最后一個元素所在的下標System.out.println(list.lastIndexOf(100));//截取部分list subList [1,3) 前閉后開System.out.println(list.subList(1,3));System.out.println(list);//subList 操作, 并不是創建一個 "副本" (拷貝一份), 而是得到原始 List 的片段.//注:此處 subList 方法的返回值類型是 List<E>,而不是 ArrayList<E>List<Integer> subList = list.subList(1,3);subList.set(0,1);System.out.println(subList);//針對 subList 修改, 也會影響到原始的 ListSystem.out.println(list);//獲取元素個數 sizeSystem.out.println(list.size());list.add(8);System.out.println(list.size());}
}
3.遍歷
ArrayList可以使用三種方式遍歷:for循環+下標、foreach、使用迭代器
import java.util.ArrayList;
import java.util.Iterator;public class Test3 {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);for(int i = 0; i < list.size(); i++){System.out.println(list.get(i));// list[i] 這樣的寫法是不行的.}//通過 foreach 遍歷. num 就會依次被賦值成 list 中的每個元素//這里的 num 只能用來 "讀" 不能用來 "寫" foreach 本質上就是迭代器寫法的簡化寫法.// 此處 num 是一個臨時變量. 不會影響到 List 中的元素的.for(Integer num: list){System.out.println(num);}//數組不具備的方式, 通過 "迭代器" 來遍歷. 典型的 Java 風格的迭代器寫法. 不僅僅是在集合類里.Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()){//通過 next 獲取到 list 中的每個元素. 通過 hasNext 判定是否遍歷結束.System.out.println(iterator.next());}}}
4.擴容機制
ArrayList是?個動態類型的順序表,即:在插入元素的過程中會自動擴容。
5.例子
5.1?模擬撲克牌
import java.util.ArrayList;
import java.util.Collections;// 通過一個類, 表示 "一張牌"
class Card{private String rank; //點數private String suit; //花色public Card(String rank, String suit){this.rank = rank;this.suit = suit;}// 搞一個 toString, 方便后續打印牌的內容public String toString(){return "(" + suit + rank + ")";}
}public class shi_xian_pukepai {// 通過這個方法創建一副撲克牌. 通過 ArrayList 表示了. deck--一副牌private static ArrayList<Card> creatDeck() {ArrayList<Card> deck = new ArrayList<>();// 把 4 種花色, 每個花色 13 個牌都創建進去. 不包含大小王String[] suits = {"?", "?", "?", "?"};for (String suit : suits) {//處理2-10for (int i = 2; i <= 10; i++) {Card card = new Card("" + i, suit);deck.add(card);}//處理JQKAdeck.add(new Card("J", suit));deck.add(new Card("Q", suit));deck.add(new Card("K", suit));deck.add(new Card("A", suit));}return deck;}public static void main(String[] args) {//Card card = new Card("A", "?");//System.out.println(card);ArrayList<Card> deck = creatDeck();System.out.println(deck);// 洗牌, 標準庫有一個現成的方法, shuffle, 就可以完成洗牌. 打亂 ArrayList 中的順序.// 修改原有的 ArrayList.Collections.shuffle(deck);System.out.println("洗牌后: " + deck);// 發牌, 假設有 3 個玩家, 每個玩家發 5 張牌. (梭哈) 使用三個 ArrayList 表示三個玩家.
// ArrayList<Card> player1 = new ArrayList<>();
// ArrayList<Card> player2 = new ArrayList<>();
// ArrayList<Card> player3 = new ArrayList<>();// 通過類似于 "二維數組" 的方式, 構造二維的 ArrayList.ArrayList<ArrayList<Card>> players = new ArrayList<>();for(int i = 0; i < 3; i++){players.add(new ArrayList<>());}// 發牌, 取出牌堆中的第一張牌, 放到第一個玩家的 ArrayList 中.// 再取出牌堆中的第二張牌, 放到第二個玩家的 ArrayList 中. 以此類推. 發 5 個輪次for(int round = 0; round < 5; round++){for(int i = 0; i < 3; i++){// 取出牌堆中的第一張牌Card card = deck.remove(0);// 放到對應玩家的 ArrayList 中ArrayList<Card> player = players.get(i);player.add(card);}}// 打印每個玩家的牌for(int i = 0; i < 3; i++){ArrayList<Card> player = players.get(i);System.out.println("玩家" + (i+1) + "的牌" + player);}}
}
5.2 楊輝三角
import java.util.ArrayList;
import java.util.List;public class yang_hui_san_jiao {public List<List<Integer>> generate(int numRows) {List<List<Integer>> result = new ArrayList<>();//每次循環,構造一行數據for (int i = 0; i < numRows; i++) {//構造ArrayList 表示當前行List<Integer> row = new ArrayList<>();//填寫若干列for (int j = 0; j <= i; j++) {//針對第一列和最后一列 都是1if (j == 0 || j == i) {row.add(1);}//其他情況 先取出上一行 再找到兩數相加else {List<Integer> lastRow = result.get(i - 1);int curValue = lastRow.get(j - 1) + lastRow.get(j);row.add(curValue);}}//此時這一行構造完 把這一行都添加到 result 中result.add(row);}return result;}
}
6.模擬實現 ArrayList
代碼實現
// 不寫成泛型的方式. 只是保存 String 類型的數據~~
// 泛型方式, 寫起來更麻煩一些. 未來面試的時候, 一般也都不要寫泛型版本的.
public class MyArrayList {private String[] data = null; // 通過這個數組, 來表示順序表中的元素private int size = 0; // 表示有效元素的個數.public MyArrayList() {data = new String[10];} // 默認的初始容量為 10public MyArrayList(int capacity) {if(capacity <= 10) capacity = 10;data = new String[capacity];}@Overridepublic String toString() {// 把有效元素轉為字符串, 并拼接到一起.StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(data[i]);// 如果 i 是 size - 1, 說明是最后一個元素, 不需要加 , 了.if (i < size - 1) stringBuilder.append(", ");}stringBuilder.append("]");return stringBuilder.toString();}// 實現擴容操作.private void resize() {// 1. 創建更長的數組, 新的數組容量是之前的 1.5 倍.String[] newData = new String[data.length + (data.length >> 1)];// 2. 把舊數組的元素, 復制到新數組上.for (int i = 0; i < size; i++) { newData[i] = data[i]; }// 3. 使用新數組代替舊數組.data = newData;}// 實現尾插操作. 把新的元素添加到順序表末尾. elem 就是 element(元素) 的縮寫. 時間復雜度 O(1)// 雖然可能觸發擴容 O(N), 但是認為在使用的時候通過設置良好的初始容量, 降低擴容的次數.public void add(String elem) {// 把 elem 放到 data 的最后一個位置上. 也就是下標為 size 的位置.// [0, size) 區間是有效元素. 需要實現擴容邏輯.if (size >= data.length) resize(); // 擴容操作.data[size] = elem;size++;}// 往中間位置插入. 往 index 元素之前插入, 確保新元素的下標就是 index. 時間復雜度 O(N)public void add(int index, String elem) {// 判定 index 是否合法. 此處是否要寫作 index <= 0 或者 index >= size?? 邊界值都需要重點討論.// 如果 index 為 0, 意思是插入完畢后, 元素就處于 0 號位置. 就相當于 "頭插"// 如果 index 為 size, 意思是插入完畢后, 元素處于 size 號位置. 就相當于 "尾插"if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);if (size >= data.length) resize(); // 擴容操作.// 把元素放到 index 位置上. 進行搬運, 把 index 之后的元素, 都往后移動一個位置.// 需要從后往前遍歷, 代入 size 為 6 的時候, 最后一個元素下標就是 5; 初始的搬運就是把 data[5] 放到 data[6] 上去// 最終的代碼就是 data[i+1] = data[i]是寫作 i >= index 還是 i > index??for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; }// 把新元素放到 index 位置上data[index] = elem;size++;}// 按照下標刪除 返回被刪除的元素的值 時間復雜度 O(N)public String remove(int index){if(index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", size: " + size);// 提前把刪除的元素的值保存一份. 否則后面搬運的時候就會覆蓋.String elem = data[index];for(int i = index; i < size-1; i++) data[i] = data[i+1];size--;return elem;}// 按照元素值來刪除 如果刪除成功, 返回 true. 否則, 返回 false. 如果 elem 本身不存在, 就認為是刪除失敗. 時間復雜度 O(N)public boolean remove(String elem) {// 先找到 elem 對應的位置在哪里int removePos = 0;// 找到了. i 這個下標就是要刪除的元素的位置.for (; removePos < size; removePos++) { if (data[removePos].equals(elem)) break; }// 上述循環結束, 有兩種可能: 1. 沒找到 elem, i 和 size 相等了.if (removePos == size) return false;//2. 找到了elem 拿著 removePos 進行刪除 進行搬運操作.for (int i = removePos; i < size - 1; i++) { data[i] = data[i + 1]; }size--;//第二點也可以直接服用上一個刪除用法 即 remove(removePos)return true;}//獲取下標index的元素 時間復雜度 O(1)public String get(int index){if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);return data[index];}//將下標index位置元素設置為element 時間復雜度 O(1)public void set(int index, String element){if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);data[index] = element;}// 刪除所有元素. 時間復雜度 O(1) 不需要把數組中的每個元素都設為 null 之類的public void clear() { size = 0; }//遍歷, 看 elem 元素是否存在. 存在就返回 true 時間復雜度 O(N)public boolean contains(String elem) {for (int i = 0; i < size; i++) { if(data[i].equals(elem)) return true; }return false;}// 從前往后遍歷, 看 elem 元素是否存在. 存在就返回它的第一個下標. 時間復雜度 O(N)public int indexOf(String elem){for(int i = 0; i < size; i++) { if(data[i].equals(elem)) return i; }return -1;}// 從后往前遍歷, 看 elem 元素是否存在. 存在就返回它的最后一個下標. 時間復雜度 O(N)public int lastIndexOf(String elem){for(int i = size - 1; i >= 0; i--) { if(data[i].equals(elem)) return i; }return -1;}// 截取[fromIndex, toIndex) 區間的元素. 時間復雜度 O(N)// 創建一個新的 MyArrayList 對象. 把上述區間的元素, 添加到新的對象中即可.public MyArrayList subList(int fromIndex, int toIndex){// 注意邊界值. fromIndex 如果為 0, 是合法的情況. toIndex 如果是 size, 也是合法的情況// fromIndex == toIndex 的時候, 也是合法, 得到空的區間.if(fromIndex < 0 || toIndex > size || fromIndex > toIndex)throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex);MyArrayList subList = new MyArrayList(toIndex-fromIndex);for(int i = fromIndex; i < toIndex; i++){String elem = this.get(i);subList.add(elem);}return subList;}// 測試尾插// 測試代碼也很關鍵. 把每個功能點的測試代碼單獨拎出來, 作為一個測試方法.// 這種測試的思路稱為 "單元測試"private static void text1(){MyArrayList list = new MyArrayList();list.add("Hello");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");System.out.println(list);// 還有辦法, 不通過打印, 也能看到 list 中的內容. 借助調試器}// 測試中間位置插入private static void text2(){MyArrayList list = new MyArrayList();list.add(0,"a");list.add(0,"b");list.add(0,"c");list.add(0,"d");list.add(2,"x");System.out.println(list);}// 測試刪除操作private static void test3(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");String elem = list.remove(1);System.out.println(elem);System.out.println(list);}private static void test4(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");boolean ret = list.remove("dd");System.out.println(ret);System.out.println(list);}private static void test5(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");System.out.println(list.contains("bb"));}private static void test6(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");System.out.println(list.indexOf("bb"));}private static void test7(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");list.add("dd");System.out.println(list.subList(1,3));}public static void main(String[] args) {test7();}}