本節目標：

1. 了解線性表和順序表
2. 能夠實現簡單的順序表及其基本操作
3. 認識 ArrayList類并且知道如何去使用

本篇文章正式進入數據結構！進入之前，先了解一下什么是線性表和順序表。

1.線性表與順序表

線性表

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

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

順序表

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

?2.實現簡單的順序表及其基本操作

在進入 ArrayList 前，我們可以先自己實現一個簡單的順序表和它的一些基本功能，在這個過程中，要特別記住，數據結構的兩個特點：

• 抽象，要有大概的結構
• 邏輯非常的嚴謹

我們實現這個順序表的過程中，會圍繞著這兩點展開！

這是我們要實現的順序表和它的一些操作：

public class SeqList { ? ?

????????private int[] array; ? ?

????????private int size; ? ?

????????// 默認構造方法 ? ?

????????SeqList(){ ? } ? ?

????????// 將順序表的底層容量設置為initcapacity ? ?

????????SeqList(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 位置的元素設為 value

????????public void set(int pos, int value) { ? }

????????//刪除第一次出現的元素

????????public void remove(int toRemove) { ? }

????????// 獲取順序表長度

????????public int size() { return 0; }

????????// 清空順序表

????????public void clear() { ? }

????????// 打印順序表

????????public void display() { ? }

? ? ? ? //這個方法是為了看測試結果才弄的！

}

從易到難，一個一個弄。

構造方法

兩個構造方法比較簡單：

public SeqList() {}public SeqList(int initcapacity) {this.array = new int[initcapacity];}

接著輪到打印順序表的方法

打印順序表

對于打印操作，我們的思路：對存放數據的數組進行遍歷，一個個打印，至于數組中存放有多少個數據，用 size 來表示數組中儲存的元素個數。

public void display() {for (int i = 0; i < this.size; i++) {System.out.println(array[i] + " ");}}

接著輪到獲取順序表長度的方法

獲取順序表長度

//獲取順序表長度public int getSize() {return this.size;}

接著輪到判定順序表是否包含某個元素的方法

?判定順序表是否包含某個元素

要求：判斷順序表是否包含某個元素，若包含則返還true，否則返回false。

思路：可以對順序表進行遍歷，如果在遍歷的過程中找到了這個元素，那么返回true，如果遍歷結束了，還沒有找到這個元素，就說明順序表中不包含這個元素，那么返回false。

//判斷順序表是否包含某個元素，若包含則返還true，否則返回false。public boolean contains(int toFind) {for (int i = 0; i < this.size; i++) {if (array[i] == toFind) {return true;}}return false;}

接著輪到查找某個元素在順序表的位置的方法

查找某個元素在順序表的位置

要求：查找某個元素在順序表的位置，如果順序表包含這個元素，就返回它在順序表中對應的位置，否則返回-1。

思路：思路與判定順序表是否包含某個元素差不多。

//查找某個元素在順序表的位置，如果順序表包含這個元素，就返回它在順序表中對應的位置，否則返回-1；public int indexOf(int toFind) {for (int i = 0; i < this.size; i++) {if (array[i] == toFind) {return i;}}return -1;}

簡單的弄完了，現在稍微上上強度了，需要考慮的事變多了。

新增元素1

要求：新增元素，在數組最后的位置新增。

思路：我們前面說過，使用size來記錄數組中儲存的元素個數，那么size相當于是現在數組的最后一個位置，那么直接將要新增的元素放到 array[size]，接著size++就好了。

?思路很清晰，但是現在有一個問題，如果數組滿了怎么辦？這樣子可放不進去了，那么我們需要在新增的元素之前，判斷一下數組是否滿了，如果滿了，需要對它進行擴容，這樣才能放入新的元素。

//新增元素1public void add(int data) {if (isFull()) {scalingArray();}this.array[size] = data;this.size++;}//判斷數組是否滿了private boolean isFull() {return this.size == array.length;}//對數組進行擴容private void scalingArray() {this.array = Arrays.copyOf(this.array,2*this.array.length);//擴容為原來的兩倍}

這里判斷數組是否滿了的方法與擴容數組的方法被private修飾，原因是我們不希望通過外部去直接訪問它們，在內部使用即可！

在編寫新增元素1的方法的過程中，發現：雖然看起來并不難實現，但是存在著許多的小細節，一不小心就會忽視，這就與之前說的數據結構的兩個特點對應上了！

新增元素2

要求：新增元素，在指定位置新增元素。

思路：假設指定位置是pos，要在pos位置新增元素，那么只需要將pos及其后面的元素向后移動即可，把pos位置騰出空間，同時進行判滿和是否擴容，最后size++即可。

看起來沒啥問題合理，但是我們忽略了一件重要的是：pos一定合法嗎？如果pos < 0 或者 pos > size（順序表不允許脫節），那我們不就炸了！因此還得處理pos合不合法的問題。?對應它不合法的情況，我們可以自定義一個異常類，當pos不合法時拋出異常，接著通過try-catch處理即可。

自定義異常類（pos不合法）：

public class PosIllegal extends RuntimeException{public PosIllegal() {}public PosIllegal(String str) {super(str);}
}

?新增元素2的方法：

//新增元素2public void add(int pos,int data) {try {isIllegal(pos);if (isFull()) {scalingArray();}for (int i = this.size - 1; i >= pos; i--) {array[i + 1] = array[i];}this.array[pos] = data;this.size++;}catch (PosIllegal e) {e.printStackTrace();}}//判斷pos是否合法private void isIllegal(int pos) {if(pos < 0 || pos > this.size) {throw new PosIllegal("pos不合法！");}}
}

獲取某個位置的元素

要求：通過傳入下標pos獲取pos位置的元素。

思路：和之前一樣，在獲取數據之前要對pos進行判斷是否合法，但是這次判斷pos合不合法與之前的不同，因為我們不能獲取pos = size位置的元素，因此pos的范圍只能是 pos >= 0 || pos < size。不僅如此，在判斷pos是否合法前，我們還要判斷數組是不是空的，如果是空的，那沒辦法獲取元素。可以寫一個自定義異常類來解決數組為空的情況，當數組為空時，拋出異常；如果數組不為空，則返回要獲取的元素，若數組中沒有該元素，則返回-1.

自定義異常類（數組為空）：

public class EmptyException extends RuntimeException{public EmptyException() {}public EmptyException(String str) {super(str);}
}

獲取某個位置元素的方法：

public int get(int pos) {try {isEmpty();isIllegal_1(pos);return this.array[pos];}catch (PosIllegal e) {e.printStackTrace();}catch (EmptyException e) {e.printStackTrace();}return -1;}//判斷數組是否為空private void isEmpty() {if(this.size == 0) {throw new EmptyException("數組為空！");}}//判斷pos是否合法——新的標準private void isIllegal_1(int pos) {if (pos < 0 || pos >= this.size) {throw new PosIllegal("pos不合法! ");}}

將某個位置的元素進行更改

要求：將下標為pos的元素進行更改。

思路：與上一個操作類似，第一，我們需要判斷數組是否為空；第二我們需要對pos判斷是否合法，這里pos的范圍與上一個操作一樣，最后用新的元素將pos位置原來的元素覆蓋即可。

//更改某個位置的元素public void set(int pos,int value) {try {isEmpty();isIllegal_1(pos);this.array[pos] = value;}catch (PosIllegal e) {e.printStackTrace();}catch (EmptyException e) {e.printStackTrace();}}

刪除第一次出現的元素

要求：將數組中第一次出現的元素刪除。

思路：通過查找某個元素在順序表的位置方法，查找要刪除的元素的下標，接著讓它后面的元素向前移動，把它覆蓋掉，這樣就達到了刪除的目的，如果數組中沒有這個元素，那么就是給出提示“數組中沒有該元素”，最后令 size-- 即可。

//刪除第一次出現的元素public void remove(int toRemove) {int x = indexOf(toRemove);if (x == -1) {   //x 等于-1說明找不到System.out.println("數組中沒有該元素！");return;}for (int i = x; i < this.size - 1; i++) {this.array[i] = this.array[i + 1];}this.size--;}

清空順序表

要求：將順序表中的所有元素清除。

思路：在這里，我們是通過數組去實現順序表的，而且決定順序表中是否存在元素的是 元素個數size，那么我們直接令 size = 0即可！但這僅僅是對于基本數據類型數組而言，對于引用數據類型數組則需要將數組中的元素一個個指向null。

 //清空順序表public void clear() {this.size = 0;}

總結

至此，我們就實現了一個簡單的順序表。

import java.util.Arrays;public class SeqList {private int[] array;private int size;//構造方法public SeqList() {}public SeqList(int initcapacity) {this.array = new int[initcapacity];}//打印順序表public void display() {for (int i = 0; i < this.size; i++) {System.out.println(array[i] + " ");}}//獲取順序表長度public int getSize() {return this.size;}//判斷順序表是否包含某個元素，若包含則返還true，否則返回false。public boolean contains(int toFind) {for (int i = 0; i < this.size; i++) {if (array[i] == toFind) {return true;}}return false;}//查找某個元素在順序表的位置，如果順序表包含這個元素，就返回它在順序表中對應的位置，否則返回-1；public int indexOf(int toFind) {for (int i = 0; i < this.size; i++) {if (array[i] == toFind) {return i;}}return -1;}//新增元素1public void add(int data) {if (isFull()) {scalingArray();}this.array[size] = data;this.size++;}//判斷數組是否滿了private boolean isFull() {return this.size == array.length;}//對數組進行擴容private void scalingArray() {this.array = Arrays.copyOf(this.array,2*this.array.length);//擴容為原來的兩倍}//新增元素2public void add(int pos,int data) {try {isIllegal(pos);if (isFull()) {scalingArray();}for (int i = this.size - 1; i >= pos; i--) {array[i + 1] = array[i];}this.array[pos] = data;this.size++;}catch (PosIllegal e) {e.printStackTrace();}}//判斷pos是否合法private void isIllegal(int pos) {if(pos < 0 || pos > this.size) {throw new PosIllegal("pos不合法！");}}//獲取某個位置元素public int get(int pos) {try {isEmpty();isIllegal_1(pos);return this.array[pos];}catch (PosIllegal e) {e.printStackTrace();}catch (EmptyException e) {e.printStackTrace();}return -1;}//判斷數組是否為空private void isEmpty() {if(this.size == 0) {throw new EmptyException("數組為空！");}}//判斷pos是否合法2private void isIllegal_1(int pos) {if (pos < 0 || pos >= this.size) {throw new PosIllegal("pos不合法! ");}}//更改某個位置的元素public void set(int pos,int value) {try {isEmpty();isIllegal_1(pos);this.array[pos] = value;}catch (PosIllegal e) {e.printStackTrace();}catch (EmptyException e) {e.printStackTrace();}}//刪除第一次出現的元素public void remove(int toRemove) {int x = indexOf(toRemove);if (x == -1) {   //x 等于-1說明找不到System.out.println("數組中沒有該元素！");return;}for (int i = x; i < this.size - 1; i++) {this.array[i] = this.array[i + 1];}this.size--;}//清空順序表public void clear() {this.size = 0;}
}

3.ArrayList類

3.1 ArrayList的簡介

在集合框架中，ArrayList是一個普通的類，它繼承了一些抽象類和實現了一些接口，具體如下：

【注意事項】

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

3.2 ArrayList的使用

ArrayList的構造

這里對第二種構造方法做解釋：它的參數 Collection<? extends? E> c ，說明傳入這個方法的參數，必須要實現Collection接口，并且要么是E，要么是E的子類。

它們的使用通常如下：

import java.util.ArrayList;public class Main {public static void main(String[] args) {//創建一個空的順序表ArrayList<Integer> arrayList1 = new ArrayList<>();//創建一個具有10個初始容量的順序表ArrayList<Integer> arrayList2 = new ArrayList<>(10);arrayList2.add(1);arrayList2.add(2);arrayList2.add(3);//第二種構造方法的使用ArrayList<Integer> arrayList3 = new ArrayList<>(arrayList2);//因為 arrayList2 的類型也為Integer并且實現了Collection接口，因此它能作為參數傳入}
}

ArrayList的常見操作

ArrayList雖然提供的方法比較多，但是常用方法如下所示：

在這些常用方法中，除了 截取部分 的方法，其他的我們在簡單順序表中基本實現了，這里介紹一下截取部分方法。subList的參數還是很好懂的，fromIndex表示開始截取的位置，toIndex表示截取結束的位置，范圍是：[fromIndex,toIndex)，但是需要注意它的返回值，它的返回值是List，不是ArrayList，而List是一個接口，ArrayList是一個實現了List接口的具體類，因此使用這個方法時，需要用List的引用去接收方法的返回值。舉例：

import java.util.ArrayList;
import java.util.List;public class Main_1 {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>(10);arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);System.out.println(arrayList);List<Integer> arrayList1 = arrayList.subList(0,2);System.out.println(arrayList1);}
}//運行結果
[1, 2, 3, 4, 5]
[1, 2]

subList需要注意的幾點：

1. 該方法返回的是原列表中從?fromIndex（包含）到?toIndex（不包含）的視圖，而不是一個新的獨立列表
2. 對返回的子列表進行修改會影響原列表，反之亦然
3. 如果原列表發生結構性修改（如添加、刪除元素），再操作子列表會拋出?ConcurrentModificationException

比如說這樣：

import java.util.ArrayList;
import java.util.List;public class Main_1 {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>(10);arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);System.out.println(arrayList);List<Integer> arrayList1 = arrayList.subList(0,2);System.out.println(arrayList1);arrayList1.set(0,99);System.out.println(arrayList);System.out.println(arrayList1);}
}//運行結果
[1, 2, 3, 4, 5]
[1, 2]
[99, 2, 3, 4, 5]
[99, 2]

?

?3.3 ArrayList的遍歷

ArrayList可以使用三種方式進行遍歷，分別是 for循環+下標、foreach、使用迭代器。

for循環+下標

import java.util.ArrayList;public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);for (int i = 0; i < arrayList.size(); i++) {System.out.print(arrayList.get(i) + " ");}}
}//運行結果
1 2 3 4 5 

foreach

import java.util.ArrayList;public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);for (Integer e:arrayList) {   //這里是 int e也行，因為在循環過程中會發生自動拆箱System.out.print(e + " ");}}
}

使用迭代器

迭代器是一種接口，它定義了遍歷集合元素的規范，包含三個核心抽象方法：

• boolean hasNext()：判斷是否還有下一個元素
• E next()：獲取下一個元素
• default void remove()：刪除最近一次通過?next()?獲取的元素（JDK 8 后新增的默認方法）

這里我們可以使用分別使用兩個迭代器去比遍歷順序表，它們是 Iterator 和 listIterator。具體使用方式如下：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;public class Test {public static void main(String[] args) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);Iterator<Integer> it = arrayList.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("================");ListIterator<Integer> listIterator = arrayList.listIterator();while(listIterator.hasNext()) {System.out.print(listIterator.next() + " ");}}
}//運行結果
1 2 3 4 5 
================
1 2 3 4 5 

發現這里它們都可以實現遍歷順序表。

3.4 ArrayList的擴容機制

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

1.檢測是否真正需要擴容，如果是調用grow準備擴容

2.預估需要庫容的大小

• ????????初步預估按照1.5倍大小擴容
• ????????如果用戶所需大小超過預估1.5倍大小，則按照用戶所需大小擴容
• ????????真正擴容之前檢測是否能擴容成功，防止太大導致擴容失敗

3.使用copyOf進行擴容

?3.5 ArrayList的缺點

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

到此，ArrayList和順序表的內容完結！感謝您的閱讀，如有錯誤，還請指出！?