前言: 這是我最一年學習java的一部分的回顧總結
1.List
1.1什么是List?
在框架集合中,List是一個接口,繼承自Collection。
Collection也是一個接口，該接口中規范了后序容器中常用的一些方法，具體如下所示
| ---- | ---- |
|---|---|
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 將 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 刪除 index 位置元素 |
| boolean remove(Object o) | 刪除遇到的第一個 o |
| E get(int index) | 獲取下標 index 位置元素 |
| E set(int index, E element) | 將下標 index 位置元素設置為 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判斷 o 是否在線性表中 |
| int indexOf(Object o) | 返回第一個 o 所在下標 |
| int lastIndexOf(Object o) | 返回最后一個 o 的下標 |
| List subList(int fromIndex, int toIndex) | 截取部分 list |
站在數據結構的角度來看，List就是一個線性表，即n個具有相同類型元素的有限序列，在該序列上可以執行增刪改查以及變量等操作。
1.2 List的使用
List是個接口，并不能直接用來實例化
如果要使用，必須去實例化List的實現類
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;public class ListExample {public static void main(String[] args) {// 使用 ArrayList 實現類List<String> arrayList = new ArrayList<>();arrayList.add("Apple");arrayList.add("Banana");arrayList.add("Orange");System.out.println("ArrayList: " + arrayList);// 使用 LinkedList 實現類List<String> linkedList = new LinkedList<>();linkedList.add("Mango");linkedList.add("Kiwi");linkedList.add("Grape");System.out.println("LinkedList: " + linkedList);}
}
List 不能直接實例化是因為接口本身只是一種規范或契約，它定義了一組方法的簽名，但并沒有提供這些方法的具體實現。
接口的主要目的是為了實現多態性和代碼的解耦。通過定義接口，不同的類可以實現相同的接口，從而以統一的方式進行處理。 打個比方，想象 List
接口是一個菜譜，它只規定了要有哪些菜（方法），但沒有告訴你具體怎么做這些菜（方法的實現）。只有具體的廚師（實現類），比如 ArrayList
或者 LinkedList ，才能按照這個菜譜做出實際的菜肴（實現方法）。
ArrayList與順序表
2.1 線性表
線性表（linear list）是n個具有相同特性的數據元素的有限序列。 線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列…
線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲
2.2 順序表
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。
下面是手動實現一個順序表的實現
package com;import java.util.Arrays;public class SeqList {private int[] array;//記錄當前順序表當中 有多少個有效的數據private int size;private static final int INIT_CAPACITY = 5;// 默認構造方法 將順序表的底層容量設置為INIT_CAPACITYpublic SeqList(){this.array = new int[INIT_CAPACITY];}//判斷當前順序表是否滿了 注意在進行新增操作是都要考慮數組是否需要判斷滿表public boolean isFull(){//返回當前表中的元素個數與當前表的長度作比較若相等是ture,反之falsereturn size == array.length;}//給數組擴容 注意在進行新增操作是都要考慮數組是否需要擴容private void resize(){array = Arrays.copyOf(array,2*array.length);}// 新增元素,默認在數組最后新增public void add(int data){if (isFull()){resize();}this.array[size] = data;//將當前指針位置＋1,每次新增操作都需要size++;}// 在 pos 位置新增元素public void add(int pos,int data){//判斷pos位置合不合法if (pos<0 || pos>this.size){throw new PosOutBoundsException("add 元素的時候，pos位置不合法！");}if(isFull()){resize();}for (int i = size-1; i >= pos; i--) {array[i+1] = array[i];}array[pos] = data;size++;}// 判定是否包含某個元素public boolean contains(int toFind) {for (int i = 0; i <this.size; i++) {if(array[i] == toFind){return true;}}return false;}// 查找某個元素對應的位置public int indexOf(int toFind) {for (int i = 0; i < this.size; i++) {if (array[i] == toFind){return i;}}return -1;}// 獲取 pos 位置的元素public int get(int pos) {if (pos<0 || pos>this.size){throw new PosOutBoundsException("pos位置不合法！");}return array[pos];}// 給 pos 位置的元素設為 valuepublic void set(int pos, int value) {if (pos<0 || pos>this.size){throw new PosOutBoundsException("pos位置不合法！");}this.array[pos] = value;}//刪除第一次出現的關鍵字keypublic void remove(int toRemove) {if (isEmpty()){return;}int index = indexOf(toRemove);if (index == -1){System.out.println("沒有你要刪除的數據");}for (int i = index; i < this.size-1; i++) {this.array[i] = this.array[i+1];}size--;}// 獲取順序表長度public int size() {return size;}// 清空順序表public void clear() {size=0;}// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的public void display() {for (int i = 0; i < this.size; i++) {System.out.println(this.array[i]+ " ");}}public boolean isEmpty(){return this.size == 0;}public static void main(String[] args) {SeqList seqList = new SeqList();seqList.add(1);seqList.add(2);seqList.add(3);seqList.add(4);seqList.add(1,10000);seqList.display();}
}
2.3 ArrayList的遍歷
ArrayList 可以使用三方方式遍歷：for循環+下標、foreach、使用迭代器
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();// 借助foreach遍歷for (Integer integer : list) {System.out.print(integer + " ");}System.out.println();Iterator<Integer> it = list.listIterator();while (it.hasNext()){System.out.print(it.next()+" ");}System.out.println();}
注意:
- ArrayList最常使用的遍歷方式是：for循環+下標 以及 foreach
- 迭代器是設計模式的一種
2.4ArrayList的擴容機制
ArrayList是一個動態類型的順序表，即：在插入元素的過程中會自動擴容。以下是ArrayList源碼中擴容方式：
private static final int DEFAULT_CAPACITY = 10;// 默認容量大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 默認空間
transient Object[] elementData; 存放元素的空間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 code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 獲取舊空間大小
int oldCapacity = elementData.length;
// 預計按照1.5倍方式擴容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用戶需要擴容大小 超過 原空間1.5倍，按照用戶所需大小擴容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果需要擴容大小超過MAX_ARRAY_SIZE，重新計算容量大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 調用copyOf擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0，拋出OutOfMemoryError異常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
總結:
- 檢測是否真正需要擴容，如果是調用grow準備擴容
- 預估需要庫容的大小初步預估按照1.5倍大小擴容如果用戶所需大小超過預估1.5倍大小，則按照用戶所需大小擴容真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗
- 使用copyOf進行擴容
2.5 ArrayList的小練習
給定一個非負整數 numRows，生成「楊輝三角」的前 numRows 行。
楊輝三角
解法:
public List<List<Integer>> generate(int numRows) {List<List<Integer>> allList = new ArrayList<>();for (int i = 0; i < numRows; i++) {List<Integer> list = new ArrayList<>();list.add(1);for (int j = 1; j < i; j++) {list.add(allList.get(i-1).get(j-1)+allList.get(i-1).get(j));}if(i != 0){list.add(1);}allList.add(list);}return allList;}
2.6ArrayList的問題及思考
問題:
- ArrayList底層使用連續的空間，任意位置插入或刪除元素時，需要將該位置后序元素整體往前或者往后搬移，故時間復雜度為O(N)
- 增容需要申請新空間,拷貝數據釋放舊空間,會有不小的消耗
- 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間。
思考:
如何解決以上問題呢？
-
對于頻繁的插入或刪除元素 我們可以適合的數據結構,例如LinkedList。LinkedList底層使用鏈表實現，在鏈表中間進行插入和刪除操作的時間復雜度為 O(1)，但它在隨機訪問元素時的性能相對較差。
-
針對增容帶來消耗的問題：
如能預先估計集合可能需要存儲的元素數量，在創建ArrayList時指定合適的初始容量，可以減少擴容的次數。或者采用內存池技術：創建一個內存池來管理內存分配和釋放。當需要擴容時，從內存池中獲取預先分配好的合適大小的內存塊，而不是每次都進行新的內存申請和釋放操作。 -
關于增容導致的空間浪費問題：
一種解決思路是使用自定義的動態數組實現，根據實際元素數量更精確地控制擴容策略，而非簡單地按照固定倍數擴容。例如，可以根據當前元素數量和一個預設的負載因子來決定是否擴容以及擴容的幅度。但這種方式需要自己實現動態數組的相關邏輯，增加了編程的復雜性
![[pwn]靜態編譯](http://pic.xiahunao.cn/[pwn]靜態編譯)
)
