1.向量介紹
計(jì)算機(jī)程序主要運(yùn)行在內(nèi)存中滴肿，而內(nèi)存在邏輯上可以被看做是連續(xù)的地址违柏。為了充分利用這一特性，在主流的編程語言中都存在一種底層的被稱為數(shù)組(Array)的數(shù)據(jù)結(jié)構(gòu)與之對應(yīng)。在使用數(shù)組時(shí)需要事先聲明固定的大小以便程序在運(yùn)行時(shí)為其開辟內(nèi)存空間；數(shù)組通過下標(biāo)值計(jì)算出地址偏移量來對內(nèi)部元素進(jìn)行訪問蚪腋。
可以看到，原始的數(shù)組很基礎(chǔ)究流，所以運(yùn)行效率非常的高辣吃。但同時(shí)也存在著嚴(yán)重的問題：
1.由于數(shù)組的大小需要在創(chuàng)建時(shí)被固定下來，但大多數(shù)程序在編寫時(shí)無法很好的預(yù)測到可能的數(shù)據(jù)量大小芬探，因而也就無法在創(chuàng)建時(shí)設(shè)置合適的數(shù)組大小，過大則浪費(fèi)內(nèi)存空間厘惦；過小則會出現(xiàn)上溢偷仿，需要編程人員進(jìn)行特別的處理哩簿。
2.訪問數(shù)組時(shí)，很容易出現(xiàn)數(shù)組下標(biāo)越界的情況酝静。由于數(shù)組的訪問是非常頻繁的节榜，因而在追求性能的語言中(如C語言)，編譯器都沒有對數(shù)組下標(biāo)越界進(jìn)行額外的檢查别智，當(dāng)程序出現(xiàn)了意外的數(shù)組下標(biāo)越界時(shí)宗苍，依然允許程序訪問和修改數(shù)組外部的內(nèi)存地址，這很容易造成古怪的薄榛，難以復(fù)現(xiàn)的bug讳窟。(Java，python等較為高級的語言為了安全起見敞恋，即使舍棄掉一定的性能也要對數(shù)組下標(biāo)越界進(jìn)行檢查)丽啡。
針對上述問題，我們需要對原始的數(shù)組進(jìn)行一定程度的封裝硬猫，在不改變基本使用方式的前提下补箍，使其在運(yùn)行過程中能夠針對所存儲的數(shù)據(jù)量大小自適應(yīng)的擴(kuò)容；對數(shù)組下標(biāo)的越界訪問進(jìn)行檢查啸蜜，同時(shí)提供一系列的常用接口供用戶使用坑雅。
而這個(gè)基于數(shù)組封裝之后的數(shù)據(jù)結(jié)構(gòu)，我們一般稱之為"向量(vector)"或者"順序表(sequence list)"衬横。
2.向量主要ADT接口介紹
由于是使用java作為實(shí)現(xiàn)的語言裹粤，因此在設(shè)計(jì)上參考了jdk自帶的向量數(shù)據(jù)結(jié)構(gòu)：java.util.ArrayList類蛹尝。
1.size()
接口定義：int size();
接口描述：返回當(dāng)前列表中元素的個(gè)數(shù)突那。
2.isEmpty()
接口定義：boolean isEmpty();
接口描述：如果當(dāng)前列表中元素個(gè)數(shù)為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);
接口描述：在列表的下標(biāo)為"index"位置處插入元素"e"来吩。
6.remove()
接口定義：boolean remove(E e);
接口描述：從列表中找到并且移除"e"對象弟疆，找到并且成功移除返回true兽间；否則返回false嘀略。
接口定義：E remove(int index);
接口描述：移除列表中下標(biāo)為"index"位置處的元素帜羊，返回被移除的元素。
7.set()
接口定義：E?set(int index,E e);
接口描述：將列表中下標(biāo)為"index"位置處的元素替代為"e",返回被替代的元素。
8.get()
接口定義：E?get(int index);
接口描述：返回列表中下標(biāo)為"index"位置處的元素痹籍。
3.向量實(shí)現(xiàn)細(xì)節(jié)
3.1 向量屬性
向量作為數(shù)組的進(jìn)一步封裝悠垛，內(nèi)部持有著一個(gè)數(shù)組确买，首先我們有以下屬性：
public class ArrayList <E> implements List <E>{
? ? //===============================================成員變量======================================================
? ? /**
? ? * 內(nèi)部封裝的數(shù)組
? ? */
? ? private Object[] elements;
? ? /**
? ? * 線性表默認(rèn)的容量大小
? ? * */
? ? private static final int DEFAULT_CAPACITY = 16;
? ? /**
? ? * 擴(kuò)容翻倍的基數(shù)
? ? * */
? ? private static final double EXPAND_BASE = 1.5;
? ? /**
? ? * 內(nèi)部數(shù)組的實(shí)際大小
? ? * */
? ? private int capacity;
? ? /**
? ? * 當(dāng)前線性表的實(shí)際大小
? ? * */
? ? private int size;
? ? //=================================================構(gòu)造方法======================================================
? ? /**
? ? * 默認(rèn)的無參構(gòu)造方法
? ? * */
? ? public ArrayList() {
? ? ? ? this.capacity = DEFAULT_CAPACITY;
? ? ? ? size = 0;
? ? ? ? //:::設(shè)置數(shù)組大小為默認(rèn)
? ? ? ? elements = new Object[capacity];
? ? }
? ? /**
? ? * 設(shè)置內(nèi)部數(shù)組初始大小的構(gòu)造方法
? ? * @param capacity 內(nèi)部數(shù)組初始大小
? ? * */
? ? public ArrayList(int capacity) {
? ? ? ? this.capacity = capacity;
? ? ? ? size = 0;
? ? ? ? //:::設(shè)置數(shù)組大小
? ? ? ? elements = new Object[capacity];
? ? }
}
3.2 較為簡單的?size()，isEmpty()周偎，indexOf()撑帖，contains()方法實(shí)現(xiàn)：
@Override
? ? public int size() {
? ? ? ? return this.size;
? ? }
? ? @Override
? ? public boolean isEmpty() {
? ? ? ? return (this.size == 0);
? ? }
? ? @Override
? ? public int indexOf(E e) {
? ? ? ? //:::判斷當(dāng)前參數(shù)是否為null
? ? ? ? if(e != null){
? ? ? ? ? ? //::::參數(shù)不為null
? ? ? ? ? ? //:::從前到后依次比對
? ? ? ? ? ? for(int i=0; i<this.size; i++){
? ? ? ? ? ? ? ? //:::判斷當(dāng)前item是否 equals 參數(shù)e
? ? ? ? ? ? ? ? if(e.equals(elements[i])){
? ? ? ? ? ? ? ? ? ? //:::匹配成功蓉坎，立即返回當(dāng)前下標(biāo)
? ? ? ? ? ? ? ? ? ? return i;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }else{
? ? ? ? ? ? //:::參數(shù)為null
? ? ? ? ? ? //:::從前到后依次比對
? ? ? ? ? ? for(int i=0; i<this.size; i++){
? ? ? ? ? ? ? ? //:::判斷當(dāng)前item是否為null
? ? ? ? ? ? ? ? if(this.elements[i] == null){
? ? ? ? ? ? ? ? ? ? //:::為null胡嘿，立即返回當(dāng)前下標(biāo)
? ? ? ? ? ? ? ? ? ? return i;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //:::遍歷列表未找到相等的元素蛉艾，返回特殊值"-1"代表未找到
? ? ? ? return -1;
? ? }
? ? @Override
? ? public boolean contains(E e) {
? ? ? ? //:::復(fù)用indexOf方法,如果返回-1代表不存在;反之衷敌，則代表存在
? ? ? ? return (indexOf(e) != -1);
? ? }
indexOf助琐、contains方法——時(shí)間復(fù)雜度：
可以看到indexOf方法的內(nèi)部是通過一次循環(huán)遍歷來查詢的。
因此indexOf方法掘譬、contains方法的漸進(jìn)時(shí)間復(fù)雜度都是O(n)葱轩，這個(gè)查詢效率比未來要介紹的哈希表的查詢時(shí)間復(fù)雜度O(1)有明顯差距。
3.3.增刪改查接口實(shí)現(xiàn)：
3.3.1 下標(biāo)越界檢查
部分增刪改查接口會通過下標(biāo)來進(jìn)行操作藐握，必須對訪問數(shù)組的下標(biāo)進(jìn)行校驗(yàn)靴拱。
下標(biāo)越界檢查方法實(shí)現(xiàn)：
/**
? ? * 插入時(shí),下標(biāo)越界檢查
? ? * @param index 下標(biāo)值
? ? */
? ? private void rangeCheckForAdd(int index){
? ? ? ? //:::如果下標(biāo)小于0或者大于size的值，拋出異常
? ? ? ? //:::注意：插入時(shí)猾普，允許插入向量的末尾袜炕，因此(index == size)是合法的
? ? ? ? if(index > this.size || index < 0){
? ? ? ? ? ? throw new RuntimeException("index error? index=" + index + " size=" + this.size) ;
? ? ? ? }
? ? }
? ? /**
? ? * 下標(biāo)越界檢查
? ? * @param index 下標(biāo)值
? ? */
? ? private void rangeCheck(int index){
? ? ? ? //:::如果下標(biāo)小于0或者大于等于size的值，拋出異常
? ? ? ? if(index >= this.size || index < 0){
? ? ? ? ? ? throw new RuntimeException("index error? index=" + index + " size=" + this.size) ;
? ? ? ? }
? ? }
3.3.2 插入方法實(shí)現(xiàn)：
@Override
? ? public boolean add(E e) {
? ? ? ? //:::插入新數(shù)據(jù)前進(jìn)行擴(kuò)容檢查
? ? ? ? expandCheck();
? ? ? ? //;::在末尾插入元素
? ? ? ? this.elements[this.size] = e;
? ? ? ? //:::size自增
? ? ? ? this.size++;
? ? ? ? return true;
? ? }
? ? @Override
? ? public void add(int index, E e) {
? ? ? ? //:::插入時(shí)抬闷，數(shù)組下標(biāo)越界檢查
? ? ? ? rangeCheckForAdd(index);
? ? ? ? //:::插入新數(shù)據(jù)前進(jìn)行擴(kuò)容檢查
? ? ? ? expandCheck();
? ? ? ? //:::插入位置下標(biāo)之后的元素整體向后移動一位(防止數(shù)據(jù)被覆蓋妇蛀，并且保證數(shù)據(jù)在數(shù)組中的下標(biāo)順序)
? ? ? ? //:::Tips: 比起for循環(huán)，System.arraycopy基于native的內(nèi)存批量復(fù)制在內(nèi)部數(shù)組數(shù)據(jù)量較大時(shí)具有更高的執(zhí)行效率
? ? ? ? for(int i=this.size; i>index; i--){
? ? ? ? ? ? this.elements[i] = this.elements[i-1];
? ? ? ? }
? ? ? ? //:::在index下標(biāo)位置處插入元素"e"
? ? ? ? this.elements[index] = e;
? ? ? ? //:::size自增
? ? ? ? this.size++;
? ? }
插入方法——時(shí)間復(fù)雜度:
可以看到笤成，向量的插入操作會導(dǎo)致插入位置之后的數(shù)據(jù)整體向后平移一位评架。
在這里，使用了for循環(huán)將數(shù)據(jù)一個(gè)一個(gè)的進(jìn)行復(fù)制炕泳。事實(shí)上纵诞，由于數(shù)組中下標(biāo)連續(xù)的數(shù)據(jù)段在內(nèi)存中也是連續(xù)成片的(邏輯意義上的)，因此操作系統(tǒng)可以通過批量復(fù)制內(nèi)存的方法來優(yōu)化這種"數(shù)組中一片連續(xù)數(shù)據(jù)復(fù)制"的操作培遵。java在jdk中自帶的向量實(shí)現(xiàn)中采用了native的System.arraycopy()方法來實(shí)現(xiàn)這個(gè)優(yōu)化操作浙芙。
在我的向量實(shí)現(xiàn)中登刺，有多處這種"數(shù)組中一片連續(xù)數(shù)據(jù)復(fù)制"的操作，為了增強(qiáng)代碼的可理解性嗡呼，都使用了for循環(huán)這種較低效率的實(shí)現(xiàn)方式纸俭，希望能夠理解。
雖然System.arraycopy能夠優(yōu)化這一操作的效率南窗，但是在漸進(jìn)的意義上揍很，向量插入操作的時(shí)間復(fù)雜度為O(n)。
動態(tài)擴(kuò)容：
前面我們提到万伤，向量相比數(shù)組的一大改進(jìn)就是向量能夠在數(shù)據(jù)新增時(shí)根據(jù)存儲的數(shù)據(jù)量進(jìn)行動態(tài)的擴(kuò)容窒悔，而不需要人工的干預(yù)。
向量擴(kuò)容方法的實(shí)現(xiàn)：
/**
? ? * 內(nèi)部數(shù)組擴(kuò)容檢查
? ? * */
? ? private void expandCheck(){
? ? ? ? //:::如果當(dāng)前元素個(gè)數(shù) = 當(dāng)前內(nèi)部數(shù)組容量
? ? ? ? if(this.size == this.capacity){
? ? ? ? ? ? //:::需要擴(kuò)容
? ? ? ? ? ? //:::先暫存之前內(nèi)部數(shù)組的引用
? ? ? ? ? ? Object[] tempArray = this.elements;
? ? ? ? ? ? //:::當(dāng)前內(nèi)部數(shù)組擴(kuò)充 一定的倍數(shù)
? ? ? ? ? ? this.capacity = (int)(this.capacity * EXPAND_BASE);
? ? ? ? ? ? //:::內(nèi)部數(shù)組指向擴(kuò)充了容量的新數(shù)組
? ? ? ? ? ? this.elements = new Object[this.capacity];
? ? ? ? ? ? //:::為了代碼的可讀性敌买，使用for循環(huán)實(shí)現(xiàn)新老數(shù)組的copy操作
? ? ? ? ? ? //:::Tips: 比起for循環(huán)简珠，System.arraycopy基于native的內(nèi)存批量復(fù)制在內(nèi)部數(shù)組數(shù)據(jù)量較大時(shí)具有更高的執(zhí)行效率
? ? ? ? ? ? for(int i=0; i<tempArray.length; i++){
? ? ? ? ? ? ? ? this.elements[i] = tempArray[i];
? ? ? ? ? ? }
? ? ? ? }
? ? }
動態(tài)擴(kuò)容——時(shí)間復(fù)雜度：
動態(tài)擴(kuò)容的操作由于需要進(jìn)行內(nèi)部數(shù)組的整體copy，其時(shí)間復(fù)雜度是O(n)虹钮。
但是站在全局的角度聋庵，動態(tài)擴(kuò)容只會在插入操作導(dǎo)致空間不足時(shí)偶爾的被觸發(fā)，所以整體來看芜抒，動態(tài)擴(kuò)容的時(shí)間復(fù)雜度為O(1)珍策。
3.3.3 刪除方法實(shí)現(xiàn)：
@Override
? ? @SuppressWarnings("unchecked")
? ? public E remove(int index) {
? ? ? ? //:::數(shù)組下標(biāo)越界檢查
? ? ? ? rangeCheck(index);
? ? ? ? //:::先暫存將要被移除的元素
? ? ? ? E willBeRemoved = (E)this.elements[index];
? ? ? ? //:::將刪除下標(biāo)位置之后的數(shù)據(jù)整體前移一位
? ? ? ? //:::Tips: 比起for循環(huán)，System.arraycopy基于native的內(nèi)存批量復(fù)制在內(nèi)部數(shù)組數(shù)據(jù)量較大時(shí)具有更高的執(zhí)行效率
? ? ? ? for(int i=index+1; i<this.size; i++){
? ? ? ? ? ? this.elements[i-1] = this.elements[i];
? ? ? ? }
? ? ? ? //:::由于數(shù)據(jù)整體前移了一位宅倒，釋放列表末尾的失效引用攘宙，增加GC效率
? ? ? ? this.elements[(this.size - 1)] = null;
? ? ? ? //:::size自減
? ? ? ? this.size--;
? ? ? ? //:::返回被刪除的元素
? ? ? ? return willBeRemoved;
? ? }
刪除方法——時(shí)間復(fù)雜度:
向量的刪除操作會導(dǎo)致被刪除位置之后的數(shù)據(jù)整體前移一位。
和插入操作類似拐迁，向量刪除操作的時(shí)間復(fù)雜度為O(n)蹭劈。
3.3.4 修改/查詢方法實(shí)現(xiàn)：
@Override
? ? @SuppressWarnings("unchecked")
? ? public E set(int index, E e) {
? ? ? ? //:::數(shù)組下標(biāo)越界檢查
? ? ? ? rangeCheck(index);
? ? ? ? //:::先暫存之前index下標(biāo)處元素的引用
? ? ? ? E oldValue = (E)this.elements[index];
? ? ? ? //:::將index下標(biāo)元素設(shè)置為參數(shù)"e"
? ? ? ? this.elements[index] = e;
? ? ? ? //:::返回被替換掉的元素
? ? ? ? return oldValue;
? ? }
? ? @Override
? ? @SuppressWarnings("unchecked")
? ? public E get(int index) {
? ? ? ? //:::數(shù)組下標(biāo)越界檢查
? ? ? ? rangeCheck(index);
? ? ? ? //:::返回對應(yīng)下標(biāo)的元素
? ? ? ? return (E)this.elements[index];
? ? }
修改/查詢方法——時(shí)間復(fù)雜度：
可以看到，向量的修改和查詢操作都直接通過下標(biāo)訪問內(nèi)部數(shù)組线召。
通過下標(biāo)訪問數(shù)組內(nèi)部元素只需要計(jì)算偏移量即可直接訪問對應(yīng)數(shù)據(jù)铺韧，因此向量修改/查詢操作的時(shí)間復(fù)雜度為O(1)。
3.4 向量其它接口：
3.4.1 clear方法
@Override
? ? public void clear() {
? ? ? ? //:::遍歷列表缓淹，釋放內(nèi)部元素引用哈打，增加GC效率
? ? ? ? for(int i=0; i<this.size; i++){
? ? ? ? ? ? this.elements[i] = null;
? ? ? ? }
? ? ? ? //:::將size重置為0
? ? ? ? this.size = 0;
? ? }
3.4.2 trimToSize方法
前面提到，向量在空間不足時(shí)會自動的進(jìn)行擴(kuò)容讯壶。自動增長的特性非常方便料仗，但是也帶來了一個(gè)問題：向量會在新增元素時(shí)擴(kuò)容，但出于效率的考量伏蚊，刪除元素卻不會自動的收縮立轧。舉個(gè)例子：一個(gè)很大的向量執(zhí)行clear時(shí)，雖然內(nèi)部元素的引用被銷毀，但是內(nèi)部數(shù)組elements依然占用了很多不必要的內(nèi)存空間氛改。
因此帐萎，向量提供了trimToSize方法，允許用戶在必要的時(shí)候手動的使向量收縮胜卤，以增加空間效率疆导。
/**? ? * 收縮內(nèi)部數(shù)組，使得"內(nèi)部數(shù)組的大小"和"向量邏輯大小"相匹配瑰艘，提高空間利用率
? ? * */publicvoid trimToSize(){
? ? ? ? //:::如果當(dāng)前向量邏輯長度 小于 內(nèi)部數(shù)組的大小if(this.size
? ? ? ? ? ? //:::創(chuàng)建一個(gè)和當(dāng)前向量邏輯大小相等的新數(shù)組Object[] newElements =newObject[this.size];
? ? ? ? ? ? //:::將當(dāng)前舊內(nèi)部數(shù)組的數(shù)據(jù)復(fù)制到新數(shù)組中
? ? ? ? ? ? //:::Tips: 這里使用Arrays.copy方法進(jìn)行復(fù)制,效率更高for(inti = 0; i< newElements.length; i++){
? ? ? ? ? ? ? ? newElements[i] =this.elements[i];
? ? ? ? ? ? }
? ? ? ? ? ? //:::用新數(shù)組替換掉之前的老內(nèi)部數(shù)組this.elements = newElements;
? ? ? ? ? ? //:::設(shè)置當(dāng)前容量this.capacity =this.size;
? ? ? ? }
? ? }
3.4.3 toString方法
@Override
? ? public String toString(){
? ? ? ? //:::空列表
? ? ? ? if(this.isEmpty()){
? ? ? ? ? ? return "[]";
? ? ? ? }
? ? ? ? //:::列表起始使用"["
? ? ? ? StringBuilder s = new StringBuilder("[");
? ? ? ? //:::從第一個(gè)到倒數(shù)第二個(gè)元素之間
? ? ? ? for(int i=0; i<size-1; i++){
? ? ? ? ? ? //:::使用", "進(jìn)行分割
? ? ? ? ? ? s.append(elements[i]).append(",").append(" ");
? ? ? ? }
? ? ? ? //:::最后一個(gè)元素使用"]"結(jié)尾
? ? ? ? s.append(elements[size - 1]).append("]");
? ? ? ? return s.toString();
? ? }
4.向量的Iterator(迭代器)
在我們使用數(shù)據(jù)結(jié)構(gòu)容器時(shí)是鬼，會遇見以下問題：
1. 需要理解內(nèi)部設(shè)計(jì)才能遍歷容器中數(shù)據(jù)。如果說基于數(shù)組的向量還可以較輕松的通過循環(huán)下標(biāo)來進(jìn)行遍歷紫新，那么更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)例如哈希表、平衡二叉樹等在遍歷時(shí)將變得更加困難李剖。同時(shí)在業(yè)務(wù)代碼中如果存儲數(shù)據(jù)的容器類型一旦被改變(向量--->鏈表)? 芒率，意味著大量代碼的推倒重寫。
2.?缺少對容器遍歷行為的抽象篙顺，導(dǎo)致重復(fù)代碼的出現(xiàn)偶芍。這一問題必須在實(shí)現(xiàn)了多個(gè)數(shù)據(jù)結(jié)構(gòu)容器之后才會體現(xiàn)出來。例如德玫，上面提到的向量的toString方法中匪蟀，如果將遍歷內(nèi)部數(shù)組的行為抽象出來，則可以使得多種不同的類型的數(shù)據(jù)結(jié)構(gòu)容器復(fù)用同一個(gè)toString方法宰僧。
為此java在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)容器架構(gòu)時(shí)材彪，抽象出了Iterator接口，用于整合容器遍歷的行為琴儿，并要求所有的容器都必須提供對應(yīng)的Iterator接口段化。
Iterator接口設(shè)計(jì)：
1. hasNext()
接口定義：boolean?hasNext();
接口描述：當(dāng)前迭代器 是否存在下一個(gè)元素。
2. next()
接口定義：E next();
接口描述：獲得迭代器 迭代的下一個(gè)元素造成。
3. remove()
接口定義：void remove();
接口描述:??移除迭代器指針當(dāng)前指向的元素
個(gè)人認(rèn)為迭代器之所以加上了remove接口显熏，是因?yàn)楹芏鄷r(shí)候迭代的操作都伴隨著刪除容器內(nèi)部元素的需求。由于刪除元素會導(dǎo)致內(nèi)部數(shù)據(jù)結(jié)構(gòu)的變化晒屎，導(dǎo)致無法簡單的完成遍歷喘蟆，需要使用者熟悉容器內(nèi)部實(shí)現(xiàn)原理，小心謹(jǐn)慎的實(shí)現(xiàn)遍歷代碼鼓鲁。
而Iterator接口的出現(xiàn)蕴轨，將這一問題帶來的復(fù)雜度交給了容器的設(shè)計(jì)者，降低了用戶使用數(shù)據(jù)結(jié)構(gòu)容器的難度坐桩。
向量Iterator實(shí)現(xiàn)：
/**
? ? * 向量 迭代器內(nèi)部類
? ? * */
? ? private class Itr implements Iterator<E>{
? ? ? ? /**
? ? ? ? * 迭代器下一個(gè)元素 指針下標(biāo)
? ? ? ? */
? ? ? ? private int nextIndex = 0;
? ? ? ? /**
? ? ? ? * 迭代器當(dāng)前元素 指針下標(biāo)
? ? ? ? * */
? ? ? ? private int currentIndex = -1;
? ? ? ? @Override
? ? ? ? public boolean hasNext() {
? ? ? ? ? ? //:::如果"下一個(gè)元素指針下標(biāo)" 小于 "當(dāng)前向量長度" ==> 說明迭代還未結(jié)束
? ? ? ? ? ? return this.nextIndex < ArrayList.this.size;
? ? ? ? }
? ? ? ? @Override
? ? ? ? @SuppressWarnings("unchecked")
? ? ? ? public E next() {
? ? ? ? ? ? //:::當(dāng)前元素指針下標(biāo) = 下一個(gè)元素指針下標(biāo)
? ? ? ? ? ? this.currentIndex = nextIndex;
? ? ? ? ? ? //:::下一個(gè)元素指針下標(biāo)自增,指向下一元素
? ? ? ? ? ? this.nextIndex++;
? ? ? ? ? ? //:::返回當(dāng)前元素
? ? ? ? ? ? return (E)ArrayList.this.elements[this.currentIndex];
? ? ? ? }
? ? ? ? @Override
? ? ? ? public void remove() {
? ? ? ? ? ? //:::刪除當(dāng)前元素
? ? ? ? ? ? ArrayList.this.remove(this.currentIndex);
? ? ? ? ? ? //:::由于刪除了當(dāng)前下標(biāo)元素尺棋，數(shù)據(jù)段整體向前平移一位，因此nextIndex不用自增
? ? ? ? ? ? //:::為了防止用戶在一次迭代(next調(diào)用)中多次使用remove方法，將currentIndex設(shè)置為-1
? ? ? ? ? ? this.currentIndex = -1;
? ? ? ? }
? ? }
5.向量總結(jié)
5.1 向量的性能
空間效率：向量中空間占比最大的就是一個(gè)隨著存儲數(shù)據(jù)規(guī)模增大而不斷增大的內(nèi)部數(shù)組膘螟。而數(shù)組是十分緊湊的成福，因此向量的空間效率非常高。
時(shí)間效率：評估一個(gè)數(shù)據(jù)結(jié)構(gòu)容器的時(shí)間效率荆残，可以從最常用的增刪改查接口來進(jìn)行衡量奴艾。
我們已經(jīng)知道，向量的增加内斯、刪除操作的時(shí)間復(fù)雜度為O(n)蕴潦，效率較低；而向量的隨機(jī)修改俘闯、查詢操作效率則非常高潭苞，為常數(shù)的時(shí)間復(fù)雜度O(1)。對于有序向量真朗，其查找特定元素的時(shí)間復(fù)雜度也能夠被控制在O(logn)對數(shù)時(shí)間復(fù)雜度上此疹。
因此向量在隨機(jī)查詢較多，而刪除和增加較少的場景表現(xiàn)優(yōu)異遮婶，但是并不適合頻繁插入和刪除的場景蝗碎。
5.2 當(dāng)前向量實(shí)現(xiàn)存在的缺陷
到這里，我們已經(jīng)完成了一個(gè)最基礎(chǔ)的向量數(shù)據(jù)結(jié)構(gòu)旗扑。限于個(gè)人水平蹦骑，以及為了代碼盡可能的簡單和易于理解，所以并沒有做進(jìn)一步的改進(jìn)臀防。
下面是我認(rèn)為當(dāng)前實(shí)現(xiàn)版本的主要缺陷：
1.不支持并發(fā)
java是一門支持多線程的語言眠菇，因此容器也必然會在多線程并發(fā)的環(huán)境下運(yùn)行。
jdk的向量數(shù)據(jù)結(jié)構(gòu)清钥，Vector主要通過對方法添加synchronized關(guān)鍵字琼锋，用悲觀鎖來實(shí)現(xiàn)線程安全，效率較低祟昭。而另一個(gè)向量的實(shí)現(xiàn)缕坎，ArrayList則是采用了快速失敗的，基于版本號的樂觀鎖對并發(fā)提供一定的支持篡悟。
2.沒有站在足夠高的角度構(gòu)建數(shù)據(jù)結(jié)構(gòu)容器的關(guān)系
java在設(shè)計(jì)自身的數(shù)據(jù)結(jié)構(gòu)容器的架構(gòu)時(shí)谜叹，高屋建瓴的設(shè)計(jì)出了一個(gè)龐大復(fù)雜的集合類型關(guān)系。這使得java的數(shù)據(jù)結(jié)構(gòu)容器API接口非常的靈活搬葬，各種內(nèi)部實(shí)現(xiàn)迥然不同的容器可以很輕松的互相轉(zhuǎn)化荷腊，使用者可以無負(fù)擔(dān)的切換所使用的數(shù)據(jù)結(jié)構(gòu)容器。同時(shí)急凰，這樣的設(shè)計(jì)也使編寫出抽象程度很高的API接口成為可能女仰，減少了大量的重復(fù)代碼。
3.接口不夠豐富
限于篇幅，這里僅僅列舉和介紹了主要的向量接口疾忍，還有許多常見的需求接口沒有實(shí)現(xiàn)乔外。其實(shí)，在理解了前面內(nèi)容的基礎(chǔ)之上一罩，實(shí)現(xiàn)一些其它常用的接口也并不困難杨幼。
4.異常處理不夠嚴(yán)謹(jǐn)
在當(dāng)前版本的下標(biāo)越界校驗(yàn)中，沒有對容器可能產(chǎn)生的各種異常進(jìn)行仔細(xì)的歸類和設(shè)計(jì)聂渊，拋出的是最基礎(chǔ)的RunTimeException差购，這使得用戶無法針對容器拋出的異常類型進(jìn)行更加細(xì)致的處理。
5.3 "自己動手實(shí)現(xiàn)java數(shù)據(jù)結(jié)構(gòu)"系列博客后續(xù)
這是"自己動手實(shí)現(xiàn)java數(shù)據(jù)結(jié)構(gòu)"系列的第一篇博客汉嗽，因此選擇了相對比較簡單的"向量"數(shù)據(jù)結(jié)構(gòu)入手欲逃。
我的目標(biāo)并不在于寫出非常完善的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，而是嘗試著用最易于接受的方式使大家熟悉常用的數(shù)據(jù)結(jié)構(gòu)诊胞。如果讀者能夠在閱讀這篇博客之后暖夭，在理解思路，原理的基礎(chǔ)之上撵孤，自己動手實(shí)現(xiàn)一個(gè)初級，原始的向量數(shù)據(jù)結(jié)構(gòu)竭望，以及在此基礎(chǔ)上進(jìn)行優(yōu)化邪码，那么這篇博客的目標(biāo)就完美達(dá)成啦。 需要源碼的朋友可以留言郵箱1
