目錄

一、List 接口

1.1 List 接口的簡單介紹

1.1 常用方法

二、順序表

2.1 線性表的介紹

2.2 順序表的介紹

2.3 順序表的實現

2.3.1 前置條件：自定義異常

2.3.2 順序表的初始化

2.3.2 順序表的實現

三、ArrayList 實現類

3.1 ArrayList 的兩種使用方式

3.2 ArrayList的構造方法

3.3 常用方法及 API

3.3.1 remove 方法

3.3.2 subList 方法

3.3 ArrayList 的三種遍歷方式

3.3.1 for 循環遍歷

3.3.2 for-each 遍歷

3.3.3 迭代器遍歷

3.4 ArrayList 的擴容機制

3.4.1 無參構造源碼分析

3.4.2 帶參構造源碼分析

3.4.3 借助容器構造源碼分析

四、鏈接算法

4.1 筆試真題

4.1.1 CVTE 刪除字符串

4.1.2 楊輝三角

---

一、List 接口

1.1 List 接口的簡單介紹

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

Collection也是一個接口，該接口中規范了后序容器中常用的一些方法，具體如下所示：

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

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

1.1 常用方法

常用方法如下：

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

二、順序表

2.1 線性表的介紹

線性表（linear list）：是 n 個具有相同特性的數據元素的有限序列（序列就是指元素之間是有順序的）。若存在多個元素，則第一個元素無前驅，最后一個元素無后繼，其他每個元素都有且只有一個前驅和后繼。

線性表是一種在實際中廣泛使用的數據結構，常見的線性表：順序表、鏈表、棧、隊列。

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

2.2 順序表的介紹

順序表：是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構。底層結構是通過數組存儲（因為數組是按順序進行存儲的），在數組上完成數據的增刪查改。

2.3 順序表的實現

2.3.1 前置條件：自定義異常

public class PosOutOfException extends RuntimeException{public PosOutOfException(){super();}public PosOutOfException(String message){super(message);}
}

2.3.2 順序表的初始化

public class MyArrayList {/*** 用于存儲數據元素*/private int[] elem;/*** 代表當前順序表的有效元素的個數：默認值為 0*/private int usedSize;private static final int DEFAULT_SIZE = 10;public MyArrayList() {this.elem = new int[DEFAULT_SIZE];this.usedSize = 0;}/*** 指定容量* @param initCapacity*/public MyArrayList(int initCapacity) {this.elem = new int[initCapacity];this.usedSize = 0;}
}

2.3.2 順序表的實現

/*** 遍歷數組：建議使用的時候加上 this*/
public void display(){for(int i=0;i<this.usedSize;i++){System.out.print(this.elem[i]+" ");}System.out.println();
}
/*** 新增元素：默認放置到數組末尾*/
public void add(int data){if(isFull()){// 擴容this.elem = Arrays.copyOf(this.elem,this.elem.length*2);}this.elem[this.usedSize] = data;this.usedSize++;
}/*** 指定位置新增元素* @param pos* @param data*/
public void add(int pos,int data){// 前置：判斷 pos 位置是否合法if(pos<0 || pos>this.usedSize){throw new PosOutOfException(pos+"位置不合法!");}//1.如果容量滿，需要進行擴容；否則導致移動元素發生數組越界訪問if(isFull()){