自己動手實現java資料結構（一） 向量
1.向量介紹
計算機程式主要執行在記憶體中，而記憶體在邏輯上可以被看做是連續的地址。為了充分利用這一特性，在主流的程式語言中都存在一種底層的被稱為陣列(Array) 的資料結構與之對應。在使用陣列時需要事先宣告固定的大小 以便程式在執行時為其開闢記憶體空間；陣列通過下標值計算出地址偏移量來對內部元素進行訪問。
可以看到，原始的陣列很基礎，所以執行效率非常的高。但同時也存在著嚴重的問題：
1.由於陣列的大小需要在建立時被固定下來，但大多數程式在編寫時無法很好的預測到可能的資料量大小，因而也就無法在建立時設定合適的陣列大小，過大則浪費記憶體空間 ；過小則會出現上溢 ，需要程式設計人員進行特別的處理。
2.訪問陣列時，很容易出現數組下標越界的情況。由於陣列的訪問是非常頻繁的，因而在追求效能的語言中(如C語言 )，編譯器都沒有對陣列下標越界進行額外的檢查，當程式出現了意外的陣列下標越界時，依然允許程式訪問和修改陣列外部的記憶體地址，這很容易造成古怪的，難以復現的bug。(Java ，python 等較為高階的語言為了安全起見，即使捨棄掉一定的效能也要對陣列下標越界進行檢查)。
針對上述問題，我們需要對原始的陣列進行一定程度的封裝，在不改變基本使用方式的前提下，使其在執行過程中能夠針對所儲存的資料量大小自適應的擴容； 對陣列下標的越界訪問進行檢查，同時提供一系列的常用介面供使用者使用。
而這個基於陣列封裝之後的資料結構，我們一般稱之為"向量(vector) "或者"順序表(sequence list) "。
2.向量主要ADT介面介紹
由於是使用java作為實現的語言，因此在設計上參考了jdk自帶的向量資料結構：java.util.ArrayList 類。
1.size()
介面定義：int size();
介面描述：返回當前列表中元素的個數。
2.isEmpty()
介面定義：boolean isEmpty();
介面描述：如果當前列表中元素個數為0，返回true ；否則，返回false 。
3.indexOf()
介面定義：int indexOf(E e);
介面描述：判斷元素"e"是否存在於列表中
4.contains()
介面定義：boolean contains(E e);
介面描述: 判斷元素"e"是否存在於列表中
5.add()
介面定義：boolean add(E e);
介面描述：在列表的最後插入元素"e" 。
介面定義：void add(int index,E e);
介面描述：在列表的下標為"index" 位置處插入元素"e" 。
6.remove()
介面定義：boolean remove(E e);
介面描述：從列表中找到並且移除 "e " 物件，找到並且成功移除返回true ；否則返回false 。
介面定義：E remove(int index);
介面描述：移除列表中下標為"index" 位置處的元素，返回被移除的元素。
7.set()
介面定義：E set(int index,E e);
介面描述：將列表中下標為"index" 位置處的元素替代為"e" ,返回被替代的元素。
8.get()
介面定義：E get(int index);
介面描述：返回列表中下標為"index" 位置處的元素。
3.向量實現細節
3.1 向量屬性
向量作為陣列的進一步封裝，內部持有著一個數組，首先我們有以下屬性：
public class ArrayList <E> implements List <E>{
/**
* 內部封裝的陣列
*/
private Object[] elements;
/**
* 線性表預設的容量大小
* */
private static final int DEFAULT_CAPACITY = 16;
/**
* 擴容翻倍的基數
* */
private static final double EXPAND_BASE = 1.5;
/**
* 內部陣列的實際大小
* */
private int capacity;
/**
* 當前線性表的實際大小
* */
private int size;
//=================================================構造方法======================================================
/**
* 預設的無參構造方法
* */
public ArrayList() {
size = 0;
//:::設定陣列大小為預設
elements = new Object[DEFAULT_CAPACITY];
}
/**
* 設定內部陣列初始大小的構造方法
* @param capacity 內部陣列初始大小
* */
public ArrayList(int capacity) {
this.capacity = capacity;
size = 0;
//:::設定陣列大小
elements = new Object[capacity];
}
｝
3.2 較為簡單的size()，isEmpty()，indexOf()，contains()方法實現：
@Override
public int size() {
return this.size;
}
@Override
public boolean isEmpty() {
return (this.size == 0);
}
@Override
public int indexOf(E e) {
//:::判斷當前引數是否為null
if(e != null){
//::::引數不為null
//:::從前到後依次比對
for(int i=0; i<this.size; i++){
//:::判斷當前item是否 equals 引數e
if(e.equals(elements[i])){
//:::匹配成功，立即返回當前下標
return i;
}
}
}else{
//:::引數為null
//:::從前到後依次比對
for(int i=0; i<this.size; i++){
//:::判斷當前item是否為null
if(this.elements[i] == null){
//:::為null，立即返回當前下標
return i;
}
}
}
//:::遍歷列表未找到相等的元素，返回特殊值"-1"代表未找到
return -1;
}
@Override
public boolean contains(E e) {
//:::複用indexOf方法,如果返回-1代表不存在;反之，則代表存在
return (indexOf(e) != -1);
}
indexOf、contains方法——時間複雜度：
可以看到indexOf 方法的內部是通過一次迴圈遍歷來查詢的。
因此indexOf 方法、contains 方法的漸進時間複雜度 都是O(n) ，這個查詢效率比未來要介紹的雜湊表 的查詢時間複雜度O(1) 有明顯差距。
3.3.增刪改查介面實現：
3.3.1 下標越界檢查
部分增刪改查介面會通過下標來進行操作，必須對訪問陣列的下標進行校驗。
下標越界檢查方法實現：
/**
* 插入時,下標越界檢查
* @param index 下標值
*/
private void rangeCheckForAdd(int index){
//:::如果下標小於0或者大於size的值，丟擲異常
//:::注意：插入時，允許插入向量的末尾，因此(index == size)是合法的
if(index > this.size || index < 0){
throw new RuntimeException("index errorindex=" + index + " size=" + this.size) ;
}
}
/**
* 下標越界檢查
* @param index 下標值
*/
private void rangeCheck(int index){
//:::如果下標小於0或者大於等於size的值，丟擲異常
if(index >= this.size || index < 0){
throw new RuntimeException("index errorindex=" + index + " size=" + this.size) ;
}
}
3.3.2 插入方法實現：
@Override
public boolean add(E e) {
//:::插入新資料前進行擴容檢查
expandCheck();
//;::在末尾插入元素
this.elements[this.size] = e;
//:::size自增
this.size++;
return true;
}
@Override
public void add(int index, E e) {
//:::插入時，陣列下標越界檢查
rangeCheckForAdd(index);
//:::插入新資料前進行擴容檢查
expandCheck();
//:::插入位置下標之後的元素整體向後移動一位(防止資料被覆蓋，並且保證資料在陣列中的下標順序)
//:::Tips: 比起for迴圈，System.arraycopy基於native的記憶體批量複製在內部陣列資料量較大時具有更高的執行效率
for(int i=this.size; i>index; i--){
this.elements[i] = this.elements[i-1];
}
//:::在index下標位置處插入元素"e"
this.elements[index] = e;
//:::size自增
this.size++;
}
插入方法——時間複雜度:
可以看到，向量的插入操作會導致插入位置之後的資料整體向後平移一位。
在這裡，使用了for迴圈將資料一個一個的進行復制。事實上，由於陣列中下標連續的資料段在記憶體中也是連續成片的(邏輯意義上的 )，因此作業系統可以通過批量複製記憶體的方法來優化這種"陣列中一片連續資料複製 "的操作。java在jdk中自帶的向量實現中採用了native 的System.arraycopy() 方法來實現這個優化操作。
在我的向量實現中，有多處這種"陣列中一片連續資料複製"的操作，為了增強程式碼的可理解性，都使用了for迴圈這種較低效率的實現方式，希望能夠理解。
雖然System.arraycopy 能夠優化這一操作的效率，但是在漸進的意義上，向量 插入操作 的時間複雜度 為O(n) 。
動態擴容：
前面我們提到，向量相比陣列的一大改進 就是向量能夠在資料新增時根據儲存的資料量進行動態的擴容 ，而不需要人工的干預。
向量擴容方法的實現：
/**
* 內部陣列擴容檢查
* */
private void expandCheck(){
//:::如果當前元素個數 = 當前內部陣列容量
if(this.size == this.capacity){
//:::需要擴容
//:::先暫存之前內部陣列的引用
Object[] tempArray = this.elements;
//:::當前內部陣列擴充 一定的倍數
this.capacity = (int)(this.capacity * EXPAND_BASE);
//:::內部陣列指向擴充了容量的新陣列
this.elements = new Object[this.capacity];
//:::為了程式碼的可讀性，使用for迴圈實現新老陣列的copy操作
//:::Tips: 比起for迴圈，System.arraycopy基於native的記憶體批量複製在內部陣列資料量較大時具有更高的執行效率
for(int i=0; i<tempArray.length; i++){
this.elements[i] = tempArray[i];
}
}
}
動態擴容——時間複雜度：
動態擴容的操作由於需要進行內部陣列的整體copy，其時間複雜度是O(n)。
但是站在全域性的角度，動態擴容只會在插入操作導致空間不足時偶爾 的被觸發，所以整體來看，動態擴容的時間複雜度為O(1) 。
3.3.3 刪除方法實現：
@Override
@SuppressWarnings("unchecked")
public E remove(int index) {
//:::陣列下標越界檢查
rangeCheck(index);
//:::先暫存將要被移除的元素
E willBeRemoved = (E)this.elements[index];
//:::將刪除下標位置之後的資料整體前移一位
//:::Tips: 比起for迴圈，System.arraycopy基於native的記憶體批量複製在內部陣列資料量較大時具有更高的執行效率
for(int i=index+1; i<this.size; i++){
this.elements[i-1] = this.elements[i];
}
//:::由於資料整體前移了一位，釋放列表末尾的失效引用，增加GC效率
this.elements[(this.size - 1)] = null;
//:::size自減
this.size--;
//:::返回被刪除的元素
return willBeRemoved;
}
刪除方法——時間複雜度:
向量的刪除操作會導致被刪除位置之後的資料整體前移一位。
和插入操作類似，向量 刪除操作 的時間複雜度 為O(n) 。
3.3.4 修改/查詢方法實現：
@Override
@SuppressWarnings("unchecked")
public E set(int index, E e) {
//:::陣列下標越界檢查
rangeCheck(index);
//:::先暫存之前index下標處元素的引用
E oldValue = (E)this.elements[index];
//:::將index下標元素設定為引數"e"
this.elements[index] = e;
//:::返回被替換掉的元素
return oldValue;
}
@Override
@SuppressWarnings("unchecked")
public E get(int index) {
//:::陣列下標越界檢查
rangeCheck(index);
//:::返回對應下標的元素
return (E)this.elements[index];
}
修改/查詢方法——時間複雜度：
可以看到，向量的修改和查詢操作都直接通過下標訪問內部陣列。
通過下標訪問陣列內部元素只需要計算偏移量即可直接訪問對應資料，因此向量 修改/查詢操作 的時間複雜度 為O(1) 。
3.4 向量其它介面：
3.4.1 clear方法
clear方法用於清空向量內的元素，初始化向量。
@Override
public void clear() {
//:::遍歷列表，釋放內部元素引用，增加GC效率
for(int i=0; i<this.size; i++){
this.elements[i] = null;
}
//:::將size重置為0
this.size = 0;
}
3.4.2 trimToSize方法
前面提到，向量在空間不足時會自動的進行擴容。自動增長的特性非常方便，但是也帶來了一個問題：向量會在新增元素時擴容，但出於效率的考量，刪除元素卻不會自動的收縮。舉個例子：一個很大的向量執行clear 時，雖然內部元素的引用被銷燬，但是內部陣列elements 依然佔用了很多不必要的記憶體空間。
因此，向量提供了trimToSize 方法，允許使用者在必要的時候手動的使向量收縮 ，以增加空間效率。
/**
* 收縮內部陣列，使得"內部陣列的大小"和"向量邏輯大小"相匹配，提高空間利用率
* */
public void trimToSize(){
//:::如果當前向量邏輯長度 小於 內部陣列的大小
if(this.size < this.capacity){
//:::建立一個和當前向量邏輯大小相等的新陣列
Object[] newElements = new Object[this.size];
//:::將當前舊內部陣列的資料複製到新陣列中
//:::Tips: 這裡使用Arrays.copy方法進行復制,效率更高
for(int i = 0; i< newElements.length; i++){
newElements[i] = this.elements[i];
}
//:::用新陣列替換掉之前的老內部陣列
this.elements = newElements;
//:::設定當前容量
this.capacity = this.size;
}
}
3.4.3 toString方法
@Override
public String toString(){
//:::空列表
if(this.isEmpty()){
return "[]";
}
//:::列表起始使用"["
StringBuilder s = new StringBuilder("[");
//:::從第一個到倒數第二個元素之間
for(int i=0; i<size-1; i++){
//:::使用", "進行分割
s.append(elements[i]).append(",").append(" ");
}
//:::最後一個元素使用"]"結尾
s.append(elements[size - 1]).append("]");
return s.toString();
}
4.向量的Iterator(迭代器)
在我們使用資料結構容器時，會遇見以下問題：
1. 需要理解內部設計才能遍歷容器中資料。如果說基於陣列的向量 還可以較輕鬆 的通過迴圈下標來進行遍歷，那麼更加複雜的資料結構例如雜湊表 、平衡二叉樹 等在遍歷時將變得更加困難 。同時在業務程式碼中如果儲存資料的容器型別一旦被改變(向量--->連結串列 ) ，意味著大量程式碼的推倒重寫。
2. 缺少對容器遍歷行為的抽象，導致重複程式碼的出現。這一問題必須在實現了多個數據結構容器之後才會體現出來。例如，上面提到的向量的toString方法中，如果將遍歷內部陣列的行為抽象出來，則可以使得多種不同的型別的資料結構容器複用同一個toString 方法。
為此java在設計資料結構容器架構時，抽象出了Iterator 介面，用於整合容器遍歷的行為，並要求所有的容器都必須提供對應的Iterator介面 。
Iterator介面設計：
1. hasNext()
介面定義：boolean hasNext();
介面描述：當前迭代器 是否存在下一個元素。
2. next()
介面定義：E next();
介面描述：獲得迭代器 迭代的下一個元素。
3. remove()
介面定義：void remove();
介面描述: 移除迭代器指標當前指向的元素
個人認為迭代器之所以加上了remove介面，是因為很多時候迭代的操作都伴隨著刪除容器內部元素的需求。由於刪除元素會導致內部資料結構的變化，導致無法簡單的完成遍歷，需要使用者熟悉容器內部實現原理，小心謹慎的實現遍歷程式碼。
而Iterator 介面的出現，將這一問題帶來的複雜度交給了容器的設計者，降低了使用者使用資料結構容器的難度。
向量Iterator實現：
/**
* 向量 迭代器內部類
* */
private class Itr implements Iterator<E>{
/**
* 迭代器下一個元素 指標下標
*/
private int nextIndex = 0;
/**
* 迭代器當前元素 指標下標
* */
private int currentIndex = -1;
@Override
public boolean hasNext() {
//:::如果"下一個元素指標下標" 小於 "當前向量長度" ==> 說明迭代還未結束
return this.nextIndex < ArrayList.this.size;
}
@Override
@SuppressWarnings("unchecked")
public E next() {
//:::當前元素指標下標 = 下一個元素指標下標
this.currentIndex = nextIndex;
//:::下一個元素指標下標自增,指向下一元素
this.nextIndex++;
//:::返回當前元素
return (E)ArrayList.this.elements[this.currentIndex];
}
@Override
public void remove() {
//:::刪除當前元素
ArrayList.this.remove(this.currentIndex);
//:::由於刪除了當前下標元素，資料段整體向前平移一位，因此nextIndex不用自增
//:::為了防止使用者在一次迭代(next呼叫)中多次使用remove方法，將currentIndex設定為-1
this.currentIndex = -1;
}
}
5.向量總結
5.1 向量的效能
空間效率：向量中空間佔比最大的就是一個隨著儲存資料規模增大而不斷增大的內部陣列。而陣列是十分緊湊的，因此向量 的空間效率 非常高 。
時間效率：評估一個數據結構容器的時間效率，可以從最常用的增刪改查介面來進行衡量。
我們已經知道，向量的增加、刪除 操作的時間複雜度 為O(n)， 效率較低；而向量的隨機修改、查詢 操作效率則非常高，為常數的時間複雜度O(1) 。對於有序向量 ，其查詢特定元素的時間複雜度 也能夠被控制在O(logn) 對數時間複雜度上。
因此向量在隨機查詢較多，而刪除和增加較少的場景表現優異，但是並不適合頻繁插入和刪除的場景。
5.2 當前向量實現存在的缺陷
到這裡，我們已經完成了一個最基礎的向量資料結構。限於個人水平，以及為了程式碼儘可能的簡單和易於理解，所以並沒有做進一步的改進。
下面是我認為當前實現版本的主要缺陷：
1.不支援併發
java是一門支援多執行緒的語言，因此容器也必然會在多執行緒併發的環境下執行。
jdk的向量資料結構，Vector 主要通過對方法新增synchronized 關鍵字，用悲觀鎖 來實現執行緒安全，效率較低。而另一個向量的實現，ArrayList 則是採用了快速失敗的，基於版本號的樂觀鎖 對併發提供一定的支援。
2.沒有站在足夠高的角度構建資料結構容器的關係
java在設計自身的資料結構容器的架構時，高屋建瓴的設計出了一個龐大複雜的集合型別關係。這使得java的資料結構容器API 介面非常的靈活，各種內部實現迥然不同的容器可以很輕鬆的互相轉化，使用者可以無負擔的切換所使用的資料結構容器。同時，這樣的設計也使編寫出抽象程度很高的API介面成為可能，減少了大量的重複程式碼。
3.介面不夠豐富
限於篇幅，這裡僅僅列舉和介紹了主要的向量介面，還有許多常見的需求介面沒有實現。其實，在理解了前面內容的基礎之上，實現一些其它常用的介面也並不困難。
4.異常處理不夠嚴謹
在當前版本的下標越界校驗中，沒有對容器可能產生的各種異常進行仔細的歸類和設計，丟擲的是最基礎的RunTimeException， 這使得使用者無法針對容器丟擲的異常型別進行更加細緻的處理。
5.3 "自己動手實現java資料結構"系列部落格後續
這是"自己動手實現java資料結構"系列的第一篇部落格，因此選擇了相對比較簡單的"向量 "資料結構入手。
我的目標並不在於寫出非常完善的資料結構實現，而是嘗試著用最易於接受的方式 使大家熟悉常用的資料結構 。如果讀者能夠在閱讀這篇部落格之後，在理解思路，原理的基礎之上，自己動手實現一個初級，原始的向量資料結構，以及在此基礎上進行優化，那麼這篇部落格的目標就完美達成啦。
本系列部落格的程式碼在我的 github上：https://github.com/1399852153/DataStructures ，歡迎交流 0.0。