從基本資料結構-表，淺析Collection中表實作（Arraylist（數組表）和Linkedlist（雙連結清單））

表是一種最簡單和最基本的資料結構，實際上，每個有意義的程式都将顯式的使用這樣的資料結構。

帶有一組操作的一些對象的集合被稱為抽象資料類型（ADT），表就是一種抽象資料類型。表ADT也有一些常用的操作，printList，find，insert，remove等等，其功能是顯而易見的。下面進入正題。

表的簡單數組實作

像剛才描述的所有操作，都可以通過數組實作。雖然數組長度是固定的，但是在必要時可以對數組進行擴容。類似這樣：

int[] arr = new int[];
        //擴大arr
        int[] newArr = new int[arr.length * ];
        for (int i = ; i < arr.length; i++) {
            newArr[i] = arr[i];
        }
        arr = newArr;
           

數組對表的實作可以使printList以線性的時間執行，而且查找的速度也很快，花費常數時間。但是插入和删除卻可能存在巨大的開銷。假設所有的操作都發生在0索引，那麼無論插入和删除都會使得剩下的元素集體移動一個位置，時間複雜度為O(N)。即使平均的來看，也需要花費線性的時間。當然，假如插入和删除發生在最後一個索引，那麼就啥也不用移動，則隻花費O(1)的時間。

這樣看來，當插入和删除隻發生在表的末尾，和之後隻發生查找之類的操作，那麼表的數組實作的确是一個不錯的選擇。但是插入和删除的發生位置無法确定，特别要是發生在前端，那麼數組對表的實作就不是很恰當了。

簡單連結清單

結合上部分的描述，為了避免插入和删除的線性開銷，我們需要保證表可以不連續的存儲。這就是另一種資料結構，連結清單。

連結清單由一系列節點組成，這些節點不需要在記憶體中連續。每個節點隻需要包含目前元素和指向下一個節點的引用，稱之為鍊，最後一個節點引用null。

對于printList或find，隻需要從表的第一個節點開始，利用鍊周遊表即可。這些操作的時間顯然是線性的，和數組實作一樣（同樣是花費線性時間，這種方式花費的時間是可能大于數組實作的）。但是對于remove（删除）這種操作，完全可以用修改一個鍊的引用實作。而對于insert（插入）而言，可以從系統中獲得一個新的節點，然後執行兩次引用的調整。這些是常數時間的操作。在删除操作中，删除最後一項相對複雜，因為必須找出指向最後節點的項，把它的鍊改為null，然後再更新持有最後節點的鍊。在經典的連結清單中，目前節點不會提供上上一節點的資訊。

我們的做法是讓目前節點不僅持有指向下一節點的鍊，還持有指向上一節點的鍊，這種連結清單被稱之為雙連結清單。

Collection中的表

Collection接口

表ADT是Collections API中實作的資料結構之一。Collections API在util包中，集合的概念在Collection接口中得到抽象，collection中有很多可以見名知意的屬性和方法。

Iterator接口

實作Iterable接口的集合必須要實作一個稱為iterator的方法，該方法傳回一個Iterator類型（這裡的Iterator是一個接口）的對象。

Iterator接口的思路是：每次傳回iterator方法，每隔集合均可建立并傳回一個實作Iterator接口的對象，并将目前位置的資料在對象内部存儲下來。每次對hasNext的調用都會驗證是否存在下一項，對next的調用會給出下一項。

Iterator接口還提供了一個remove的方法，用來删除next最新傳回的項。Collection接口同樣也提供了remove方法，但是Iterator提供的remove可能有更多的優點。

其一，Collocation的remove必須先找到要被删除的項。Iterator的remove是删除next最新傳回的項（目前項）。Iterator的remove方法潛藏着更高的效率和更小的開銷。

其二，合法性。使用Iterator是一個基本法則，正在被疊代的集合如果發生了結構上的改變（即使用了add，remove等方法），那麼這個疊代器就不在合法。然而，如果調用Iterator的remove方法，那麼這個疊代器依舊是是合法的。

其三，感覺說着說着跑題了，但是一說到集合，就繞不開Iterator。2333333333

可能有些大兄弟會疑惑為什麼一定要實作Iterable接口，為什麼不直接實作Iterator接口呢。其實我也有這疑惑，後來看了一些大神的分析明白了。（ 因為Iterator接口的核心方法next()或者hasNext() 是依賴于疊代器的目前疊代位置的。如果Collection直接實作Iterator接口，勢必導緻集合對象中包含目前疊代位置的資料。當集合在不同方法間被傳遞時，由于目前疊代位置不可預置，那麼next()方法的結果會變成不可預知。除非再為Iterator接口添加一個reset()方法，用來重置目前疊代位置。但即時這樣，Collection也隻能同時存在一個目前疊代位置。而Iterable則不然，每次調用都會傳回一個從頭開始計數的疊代器。多個疊代器是互不幹擾的。）這個過程就是小白的進階之路吧。

ArraList和LinkedList

在Collection API中我們主要讨論表（List），它對應的是java.util中的List接口。List接口繼承了Collection接口，是以它包含Collection的所有方法，外加一些其他方法。列舉幾個常用的，無非就是增删改查。

listIterator方法會傳回一個ListIterator（也是個接口）類型的對象，ListIterator繼承了Iterator接口，實作了對List集合的反向疊代。有興趣可以去看下源碼，就不介紹了。

List ADT有兩種流行的實作方式：ArraList和LinkedList。

• ArraList：ArraList提供了一種可增長數組的實作。使用ArrayList的優點在于，對于get和set的調用花費常數時間。其缺點是删除和增加的代價昂貴（除非發生在末尾）。
• LinkedList：LinkedList則提供了一種雙連結清單的實作。它對删除和增加的開銷很小（而且這個類還直接提供了對表兩端直接操作的方法，例如addFirst、removeLast等等）。它的缺點是不容易做索引（前面提到過，因為它在記憶體上不連續），是以他對于get的調用是昂貴的。

下面舉例說明：

public void addFirst(List<Integer> list,int N) {
        list.clear();
        for (int i = ; i < N; i++) 
            list.add(, i);
    }
           

這段代碼對于LinkedList來說，運作時間是O(N)。但是對于ArrayList來說是O(N*2)，因為在ArrayList中在前端的add操作是O(N)。

public int sum(List<Integer> list,int N) {
        int sum = ;
        //假設N=list.size(),用N看時間複雜度明顯些
        for (int i = ; i < N; i++) 
            sum += list.get(i);
        return sum;
    }
           

對于這段代碼，ArrayList的運作時間是O(N)，而LinkedList的運作時間是O(N*2)，因為LinkedList對get的操作是O(N)。

public int sum(List<Integer> list) {
        int sum = ;
        for (int tem:list) 
            sum += tem;
        return sum;
    }
           

之前說了些Iterator，有些跑題，那就在拉回來點。這段代碼，對于兩種List運作時間都是O(N)。因為增強for是對疊代器的使用，疊代器可以有效地從一項推進到另一項。

另外，這兩種List的搜尋都是低效的，對于contains和remove方法的調用均花費線性時間。這裡的remove方法指的是傳回值是boolean的remove(Object)方法。

emmmmmm

本來接下來是想分析下ArrayList和LinkedList的源碼的，emmmmmm，寫的不少了也，有機會再說吧。再補充一些。

最基本的三種資料結構是表，棧和隊列。但是棧和隊列其實也是表。棧是限制添加和删除都隻能在末端的表，隊列是插入和删除分别在兩端的表。也就是說，一切實作表的方法都能實作隊列和棧。那麼自然ArrayList和LinkedList同樣能實作棧和列隊，而且隻需要兩個集合現有的功能就能實作，有興趣的話可以自己試試。