List介紹

什么是List

在集合框架中，List是一個接口，繼承自Collection

Collection也是一個接口，該接口中規范了后序容器中常用的一些方法

Iterable也是一個接口，表示實現該接口的類是可以逐個元素進行遍歷的，具體如下：

List的官方文檔

List (Java Platform SE 8 )List (Java Platform SE 8 )

站在數據結構的角度來看，List就是一個線性表，即n個具有相同類型元素的有限序列，在該序列上可以執行增刪改查以及變量等操作
?

List常見接口介紹

List接口包括Collection接口的所有方法。這是因為Collection是List的超級接口。

Collection接口中還提供了一些常用的List接口方法：

add() - 將元素添加到列表

addAll() - 將一個列表的所有元素添加到另一個

get() - 有助于從列表中隨機訪問元素

iterator() - 返回迭代器對象，該對象可用于順序訪問列表的元素

set() - 更改列表的元素

remove() - 從列表中刪除一個元素

removeAll() - 從列表中刪除所有元素

clear() - 從列表中刪除所有元素（比removeAll()效率更高）

size() - 返回列表的長度

toArray() - 將列表轉換為數組

contains() -? 如果列表包含指定的元素，則返回true

List的使用

注意：List是個接口，并不能直接用來實例化。如果要使用，必須去實例化List的實現類。在集合框架中，ArrayList和LinkedList都實現了List接口

線性表

線性表（linear list）是n個具有相同特性的數據元素的有限序列。線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列...

線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲

順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改

接口的實現

public class SeqList {private int[] array;private int size;// 默認構造方法SeqList() {}// 將順序表的底層容量設置為initcapacitySeqList(int initcapacity) {}// 新增元素,默認在數組最后新增public void add(int data) {}// 在 pos 位置新增元素public void add(int pos, int data) {}// 判定是否包含某個元素public boolean contains(int toFind) {return true;}// 查找某個元素對應的位置public int indexOf(int toFind) {return -1;}// 獲取 pos 位置的元素public int get(int pos) {return -1;}// 給 pos 位置的元素設為 valuepublic void set(int pos, int value) {}//刪除第一次出現的關鍵字keypublic void remove(int toRemove) {}// 獲取順序表長度public int size() {return 0;}// 清空順序表public void clear() {}// 打印順序表，注意：該方法并不是順序表中的方法，為了方便看測試結果給出的public void display() {}
}

ArrayList的簡介

在集合框架中，ArrayList是一個普通的類，實現了List接口，具體框架圖如下：

ArrayList使用

說明

ArrayList是以泛型方式實現的，使用時必須要先實例化
ArrayList實現了RandomAccess接口，表明ArrayList支持隨機訪問
ArrayList實現了Cloneable接口，表明ArrayList是可以clone的
ArrayList實現了Serializable接口，表明ArrayList是支持序列化的
和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者 CopyOnWriteArrayList
ArrayList底層是一段連續的空間，并且可以動態擴容，是一個動態類型的順序表

ArrayList使用

ArrayList的構造

ArrayList() 無參構造
ArrayList(Collection c) 利用其他 Collection 構建 ArrayList
ArrayList(int initialCapacity) 指定順序表初始容量

public static void main(String[] args) {
// ArrayList創建，推薦寫法
// 構造一個空的列表List<Integer> list1 = new ArrayList<>();
// 構造一個具有10個容量的列表List<Integer> list2 = new ArrayList<>(10);list2.add(1);list2.add(2);list2.add(3);
// list2.add("hello"); // 編譯失敗，List<Integer>已經限定了，list2中只能存儲整形元素
// list3構造好之后，與list中的元素一致ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略類型，否則：任意類型的元素都可以存放，使用時將是一場災難List list4 = new ArrayList();list4.add("111");list4.add(100);
}

public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("JavaSE");list.add("JavaWeb");list.add("JavaEE");list.add("JVM");list.add("測試課程");System.out.println(list);// 獲取list中有效元素個數System.out.println(list.size());// 獲取和設置index位置上的元素，注意index必須介于[0, size)間System.out.println(list.get(1));list.set(1, "JavaWEB");System.out.println(list.get(1));// 在list的index位置插入指定元素，index及后續的元素統一往后搬移一個位置list.add(1, "Java數據結構");System.out.println(list);// 刪除指定元素，找到了就刪除，該元素之后的元素統一往前搬移一個位置list.remove("JVM");System.out.println(list);// 刪除list中index位置上的元素，注意index不要超過list中有效元素個數,否則會拋出下標越界異常list.remove(list.size() - 1);System.out.println(list);// 檢測list中是否包含指定元素，包含返回true，否則返回falseif (list.contains("測試課程")) {list.add("測試課程");}// 查找指定元素第一次出現的位置：indexOf從前往后找，lastIndexOf從后往前找list.add("JavaSE");System.out.println(list.indexOf("JavaSE"));System.out.println(list.lastIndexOf("JavaSE"));// 使用list中[0, 4)之間的元素構成一個新的SubList返回,但是和ArrayList共用一個elementData數組List<String> ret = list.subList(0, 4);System.out.println(ret);list.clear();System.out.println(list.size());
}

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
迭代器是設計模式的一種

ArrayList的擴容機制

下面代碼有缺陷嗎？為什么？

public static void main(String[] args) {List<Integer> list = new ArrayList<>();for (int i = 0; i < 100; i++) {list.add(i);}
}

ArrayList是一個動態類型的順序表，即：在插入元素的過程中會自動擴容。

以下是ArrayList源碼中擴容方式：

transient Object[] elementData; // non-private to simplify nested class access
private int size;
//構造方法
public ArrayList( int initialCapacity){if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: " +initialCapacity);}
}
public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}
}public void ensureCapacity(int minCapacity) {if (minCapacity > elementData.length&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA&& minCapacity <= DEFAULT_CAPACITY)) {modCount++;grow(minCapacity);}
}private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1           /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}
/*
這段代碼是Java語言編寫的，它定義了一個名為`grow`的方法，這個方法的作用是擴容一個數組，使其能夠容納更多的元素。這個方法是私有的，意味著它只能在定義它的類內部被調用。下面是對這個方法的逐行解釋：1. `private Object[] grow(int minCapacity) {`：定義了一個私有方法`grow`，它接受一個整型參數`minCapacity`，表示數組需要擴容到的最小容量，并返回一個`Object`類型的數組。2. `int oldCapacity = elementData.length;`：獲取當前數組`elementData`的容量，并將其存儲在變量`oldCapacity`中。3. `if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {`：檢查當前數組是否已經有容量（即不是默認的空數組）。`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`可能是一個常量，表示默認的空數組。4. `int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1);`：調用`ArraysSupport.newLength`方法來計算新的容量。這個方法的參數包括：- `oldCapacity`：當前數組的容量。- `minCapacity - oldCapacity`：需要增加的最小容量。- `oldCapacity >> 1`：推薦的增長量，這里使用了右移操作符`>>`，相當于將`oldCapacity`除以2。5. `return elementData = Arrays.copyOf(elementData, newCapacity);`：使用`Arrays.copyOf`方法將當前數組`elementData`復制到一個新的數組中，新數組的容量為`newCapacity`。這個方法會返回新的數組，并且更新`elementData`引用指向這個新數組。6. `} else {`：如果當前數組是空的（即沒有容量），則執行else塊中的代碼。7. `return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];`：在這種情況下，創建一個新的`Object`數組，其容量是`DEFAULT_CAPACITY`和`minCapacity`中的最大值。`DEFAULT_CAPACITY`可能是一個定義了默認初始容量的常量。8. `}`：方法的結束。總的來說，這個方法的目的是確保`elementData`數組有足夠的容量來存儲至少`minCapacity`個元素。如果當前數組的容量已經足夠，它將按照一定的增長策略（至少是當前容量的一半）來擴容。如果當前數組是空的，它將創建一個新的數組，其容量至少為`DEFAULT_CAPACITY`或`minCapacity`中的較大值。*/

總結

檢測是否真正需要擴容，如果是調用grow準備擴容
預估需要庫容的大小初步預估按照1.5倍大小擴容如果用戶所需大小超過預估1.5倍大小，則按照用戶所需大小擴容真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗
使用copyOf進行擴容

ArrayList的問題及思考

ArrayList底層使用連續的空間，任意位置插入或刪除元素時，需要將該位置后序元素整體往前或者往后搬移，故時間復雜度為O(N)
增容需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗
增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間

如何解決上述問題？