一、線性表的順序存儲設(shè)計(jì)與實(shí)現(xiàn)（順序表）
1.1?? 順序存儲結(jié)構(gòu)的設(shè)計(jì)原理概要
順序存儲結(jié)構(gòu)底層是利用數(shù)組來實(shí)現(xiàn)的，而數(shù)組可以存儲具有相同數(shù)據(jù)類型的元素集合，，當(dāng)我們創(chuàng)建一個數(shù)組時，計(jì)算機(jī)操作系統(tǒng)會為該數(shù)組分配一塊連續(xù)的內(nèi)存塊，這也就意味著數(shù)組中的每個存儲單元的地址都是連續(xù)的，因此只要知道了數(shù)組的起始內(nèi)存地址就可以通過簡單的乘法和加法計(jì)算出數(shù)組中第n-1個存儲單元的內(nèi)存地址，就如下圖所示：
??通過上圖可以發(fā)現(xiàn)為了訪問一個數(shù)組元素，該元素的內(nèi)存地址需要計(jì)算其距離數(shù)組基地址的偏移量，即用一個乘法計(jì)算偏移量然后加上基地址，就可以獲得數(shù)組中某個元素的內(nèi)存地址。其中c代表的是元素數(shù)據(jù)類型的存儲空間大小，而序號則為數(shù)組的下標(biāo)索引。
整個過程需要一次乘法和一次加法運(yùn)算，因?yàn)檫@兩個操作的執(zhí)行時間是常數(shù)時間，所以我們可以認(rèn)為數(shù)組訪問操作能再常數(shù)時間內(nèi)完成，即時間復(fù)雜度為O(1)，這種存取任何一個元素的時間復(fù)雜度為O(1)的數(shù)據(jù)結(jié)構(gòu)稱之為隨機(jī)存取結(jié)構(gòu)。而順序表的存儲原理正如上圖所示，因此順序表的定義如下（引用）：
線性表的順序存儲結(jié)構(gòu)稱之為順序表(Sequential List),它使用一維數(shù)組依次存放從a0到an-1的數(shù)據(jù)元素(a0,a1,…,an-1)，將ai(0< i <> n-1)存放在數(shù)組的第i個元素，使得ai與其前驅(qū)ai-1及后繼ai+1的存儲位置相鄰，因此數(shù)據(jù)元素在內(nèi)存的物理存儲次序反映了線性表數(shù)據(jù)元素之間的邏輯次序。
1.2 順序存儲結(jié)構(gòu)的實(shí)現(xiàn)分析
接著我們來分析一下順序表的實(shí)現(xiàn)，先聲明一個順序表接口類SeqList，然后實(shí)現(xiàn)該接口并實(shí)現(xiàn)接口方法的代碼，SeqList接口代碼如下：
我們創(chuàng)建ArraySeqList一個順序表實(shí)現(xiàn)這個接口。
private final Object[]EMPTY_ELEMENTDATA = {};
private final Object[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY =10;
/*** * 元素的個數(shù) */
private int size;
ArraySeqList的構(gòu)造方法
無參構(gòu)造方法，我們默認(rèn)是空數(shù)組，有參構(gòu)造構(gòu)造方法中，我們新建一個長度為size的空數(shù)組。
get(int index) 實(shí)現(xiàn)分析?
從順序表中獲取值是一種相當(dāng)簡單的操作并且效率很高，這是由于順序表內(nèi)部采用了數(shù)組作為存儲數(shù)據(jù)的容器。因此只要根據(jù)傳遞的索引值，然后直接獲取數(shù)組中相對應(yīng)下標(biāo)的值即可，代碼實(shí)現(xiàn)如下：
set(int index, T data) 實(shí)現(xiàn)分析
在順序表中替換值也是非常高效和簡單的，只要根據(jù)傳遞的索引值index找到需要替換的元素，然后把對應(yīng)元素值替換成傳遞的data值即可，代碼如下：
add(int index, T data)和add(T data)實(shí)現(xiàn)分析
在順序表中執(zhí)行插入操作時，如果其內(nèi)部數(shù)組的容量尚未達(dá)到最大值時，可以歸結(jié)為兩種情況：一種是在頭部插入或者中間插入，這種情況下需要移動數(shù)組中的數(shù)據(jù)元素，效率較低；另一種是在尾部插入，無需移動數(shù)組中的元素，效率高。
但是當(dāng)順序表內(nèi)部數(shù)組的容量已達(dá)到最大值無法插入時，則需要申請另一個更大容量的數(shù)組并復(fù)制全部數(shù)組元素到新的數(shù)組，這樣的時間和空間開銷是比較大的，也就導(dǎo)致了效率更為糟糕了。
因此在插入頻繁的場景下，順序表的插入操作并不是理想的選擇。下面是順序表在數(shù)組容量充足下頭部或中間插入操作示意圖（尾部插入比較簡單就不演示了）：
理解了以上幾種順序表的插入操作后，我們通過代碼來實(shí)現(xiàn)這個插入操作如下。
每次插入元素之前，我們都應(yīng)該判斷數(shù)組是否夠用，如果數(shù)組長度夠用，就將index以后 的元素右移一位，然后將新元素添加到下標(biāo)為index的位置。元素個數(shù)size++
數(shù)組長度不夠的時候，元素的個數(shù)大于當(dāng)前數(shù)組的長度時，我們就應(yīng)該擴(kuò)容數(shù)組。代碼如下：
remove(int index) 實(shí)現(xiàn)分析
順序表的刪除操作和前的插入操作情況是類似的，如果是在中間或者頭部刪除順序表中的元素，那么在刪除位置之后的元素都必須依次往前移動，效率較低，如果是在順序表的尾部直接刪除的話，則無需移動元素，此情況下刪除效率高。如下圖所示在順序表中刪除元素ai時，ai之后的元素都依次往前移動：
刪除操作的代碼實(shí)現(xiàn)如下：
remove(E e) 實(shí)現(xiàn)分析
在順序表中根據(jù)數(shù)據(jù)data找到需要刪除的數(shù)據(jù)元素和前面分析的根據(jù)index刪除順序表中的數(shù)據(jù)元素是一樣的道理，因此我們只要通過比較找到與data相等的數(shù)據(jù)元素并獲取其下標(biāo)，然后調(diào)用前面實(shí)現(xiàn)的remove(int index)方法來移除即可。代碼實(shí)現(xiàn)如下：
源碼實(shí)現(xiàn)：源碼
1.3 順序存儲結(jié)構(gòu)的效率分析
數(shù)組的訪問操作能在常數(shù)時間內(nèi)完成，即順序表的訪問操作(獲取和修改元素值)的時間復(fù)雜為O(1)。
對于在順序表中插入或者刪除元素，從效率上則顯得不太理想了，由于插入或者刪除操作是基于位置的，需要移動數(shù)組中的其他元素，所以順序表的插入或刪除操作，算法所花費(fèi)的時間主要是用于移動元素，如在順序表頭部插入或刪除時，效率就顯得相當(dāng)糟糕了。若在最前插入或刪除，則需要移動n（這里假設(shè)長度為n）個元素；若在最后插入或刪除，則需要移動的元素為0。這里我們假設(shè)插入或刪除值為第i(0）。
也就是說，在等概率的情況下，插入或者刪除一個順序表的元素平均需要移動順序表元素總量的一半，其時間復(fù)雜度是O(n)。當(dāng)然如果在插入時，內(nèi)部數(shù)組容量不足時，也會造成其他開銷，如復(fù)制元素的時間開銷和新建數(shù)組的空間開銷。
因此總得來說順序表有以下優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)
使用數(shù)組作為內(nèi)部容器簡單且易用；
在訪問元素方面效率高；
數(shù)組具有內(nèi)存空間局部性的特點(diǎn)，由于本身定義為連續(xù)的內(nèi)存塊，所以任何元素與其相鄰的元素在物理地址上也是相鄰的。
缺點(diǎn)
內(nèi)部數(shù)組大小是靜態(tài)的，在使用前必須指定大小，如果遇到容量不足時，需動態(tài)拓展內(nèi)部數(shù)組的大小，會造成額外的時間和空間開銷
在內(nèi)部創(chuàng)建數(shù)組時提供的是一塊連續(xù)的空間塊，當(dāng)規(guī)模較大時可能會無法分配數(shù)組所需要的內(nèi)存空間
順序表的插入和刪除是基于位置的操作，如果需要在數(shù)組中的指定位置插入或者刪除元素，可能需要移動內(nèi)部數(shù)組中的其他元素，這樣會造成較大的時間開銷，時間復(fù)雜度為O(n)
二、線性表的鏈?zhǔn)酱鎯υO(shè)計(jì)與實(shí)現(xiàn)（鏈表）
2.1 鏈表的鏈?zhǔn)酱鎯Y(jié)構(gòu)設(shè)計(jì)原理概要
通過前面對線性順序表的分析，我們知道當(dāng)創(chuàng)建順序表時必須分配一塊連續(xù)的內(nèi)存存儲空間，而當(dāng)順序表內(nèi)部數(shù)組的容量不足時，則必須創(chuàng)建一個新的數(shù)組，然后把原數(shù)組的的元素復(fù)制到新的數(shù)組中，這將浪費(fèi)大量的時間。而在插入或刪除元素時，可能需要移動數(shù)組中的元素，這也將消耗一定的時間。
鑒于這種種原因，于是鏈表就出場了，鏈表在初始化時僅需要分配一個元素的存儲空間，并且插入和刪除新的元素也相當(dāng)便捷，同時鏈表在內(nèi)存分配上可以是不連續(xù)的內(nèi)存，也不需要做任何內(nèi)存復(fù)制和重新分配的操作，由此看來順序表的缺點(diǎn)在鏈表中都變成了優(yōu)勢，實(shí)際上也是如此，當(dāng)然鏈表也有缺點(diǎn)，主要是在訪問單個元素的時間開銷上，這個問題留著后面分析，我們先通過一張圖來初步認(rèn)識一下鏈表的存儲結(jié)構(gòu)，如下：
從圖可以看出線性鏈表的存儲結(jié)構(gòu)是用若干個地址分散的存儲單元存放數(shù)據(jù)元素的，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，因此每個存儲單元中都會有一個地址指向域，這個地址指向域指明其后繼元素的位置。在鏈表中存儲數(shù)據(jù)的單元稱為結(jié)點(diǎn)(Node)，從圖中可以看出一個結(jié)點(diǎn)至少包含了數(shù)據(jù)域和地址域，其中數(shù)據(jù)域用于存儲數(shù)據(jù)，而地址域用于存儲前驅(qū)或后繼元素的地址。
前面我們說過鏈表的插入和刪除都相當(dāng)便捷，這是由于鏈表中的結(jié)點(diǎn)的存儲空間是在插入或者刪除過程中動態(tài)申請和釋放的，不需要預(yù)先給單鏈表分配存儲空間的，從而避免了順序表因存儲空間不足需要擴(kuò)充空間和復(fù)制元素的過程，提高了運(yùn)行效率和存儲空間的利用率。
2.2 單鏈表的儲結(jié)構(gòu)實(shí)現(xiàn)分析
同樣地，先來定義一個頂級的鏈表接口:ILinkedList和存儲數(shù)據(jù)的結(jié)點(diǎn)類Node，該類是代表一個最基本的存儲單元，Node代碼如下：
接著頂級的鏈表接口ILinkedList，該接口聲明了我們所有需要實(shí)現(xiàn)的方法。
boolean isEmpty()實(shí)現(xiàn)分析
需要判斷鏈表是否為空的依據(jù)是頭結(jié)點(diǎn)head是否為null，當(dāng)head=null時鏈表即為空鏈表，因此我們只需判斷頭結(jié)點(diǎn)是否為空即可，isEmpty方法實(shí)現(xiàn)如下：
int length()實(shí)現(xiàn)分析
獲取鏈表的長度，我們提供2種方法，第一種就是增加一個變量size，用它倆記錄鏈表的長度。
第二種方法，因此我們只要遍歷整個鏈表并獲取結(jié)點(diǎn)的數(shù)量即可獲取到鏈表的長度。遍歷鏈表需要從頭結(jié)點(diǎn)HeadNode開始，為了不改變頭結(jié)點(diǎn)的存儲單元，聲明變量p指向當(dāng)前頭結(jié)點(diǎn)和局部變量length，然后p從頭結(jié)點(diǎn)開始訪問，沿著next地址鏈到達(dá)后繼結(jié)點(diǎn)，逐個訪問，直到最后一個結(jié)點(diǎn)，每經(jīng)過一個結(jié)點(diǎn)length就加一，最后length的大小就是鏈表的大小。實(shí)現(xiàn)代碼如下：
E get(int index)實(shí)現(xiàn)分析
在單鏈表中獲取某個元素的值是一種比較費(fèi)時間的操作，需要從頭結(jié)點(diǎn)開始遍歷直至傳入值index指向的位置，其查詢獲取值的過程如下圖所示：
代碼如下：
T set(int index, T data)實(shí)現(xiàn)分析?
根據(jù)傳遞的index查找某個值并替換其值為data，其實(shí)現(xiàn)過程的原理跟get(int index)是基本一樣的，先找到對應(yīng)值所在的位置然后刪除即可，不清晰可以看看前面的get方法的圖解，這里直接給出代碼實(shí)現(xiàn)：
add(int index, T data)實(shí)現(xiàn)分析?
單鏈表的插入操作分四種情況:?
a.空表插入一個新結(jié)點(diǎn)，插語句如下：
head=new Node(x,null);
b.在鏈表的表頭插入一個新結(jié)點(diǎn)(即鏈表的開始處)，此時表頭head!=null，因此head后繼指針next應(yīng)該指向新插入結(jié)點(diǎn)p，而p的后繼指針應(yīng)該指向head原來的結(jié)點(diǎn)，代碼如下：
以上代碼可以合并為如下代碼：
執(zhí)行過程如下圖：
c.在鏈表的中間插入一個新結(jié)點(diǎn)p，需要先找到給定插入位置的前一個結(jié)點(diǎn)，假設(shè)該結(jié)點(diǎn)為front，然后改變front的后繼指向?yàn)樾陆Y(jié)點(diǎn)p，同時更新新結(jié)點(diǎn)p的后繼指向?yàn)閒ront原來的后繼結(jié)點(diǎn)，即front.next，其執(zhí)行過程如下圖所示：
代碼實(shí)現(xiàn)如下：
d.在鏈表的表尾插入一個新結(jié)點(diǎn)(鏈表的結(jié)尾)在尾部插入時，同樣需要查找到插入結(jié)點(diǎn)P的前一個位置的結(jié)點(diǎn)front（假設(shè)為front），該結(jié)點(diǎn)front為尾部結(jié)點(diǎn)，更改尾部結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)P，新結(jié)點(diǎn)P的后繼指針設(shè)置為null，執(zhí)行過程如下：
具體代碼如下：
T remove(int index) 刪除結(jié)點(diǎn)實(shí)現(xiàn)分析
在單向鏈表中，根據(jù)傳遞index位置刪除結(jié)點(diǎn)的操作分3種情況，并且刪除后返回被刪除結(jié)點(diǎn)的數(shù)據(jù)：
a.刪除鏈表頭部（第一個）結(jié)點(diǎn)，此時需要刪除頭部head指向的結(jié)點(diǎn)，并更新head的結(jié)點(diǎn)指向，執(zhí)行圖示如下：
代碼如下：
b.刪除鏈表的中間結(jié)點(diǎn)，與添加是同樣的道理，需要先找到要刪除結(jié)點(diǎn)r（假設(shè)要刪除的結(jié)點(diǎn)為r）位置的前一個結(jié)點(diǎn)front(假設(shè)為front)，然后把front.next指向r.next即要刪除結(jié)點(diǎn)的下一個結(jié)點(diǎn)，執(zhí)行過程如下：
代碼如下：
void clear() 實(shí)現(xiàn)分析
清空鏈表是一件非常簡單的事，直接將所有的節(jié)點(diǎn)置空。代碼如下：
ok~,到此單鏈表主要的添加、刪除、獲取值、設(shè)置替換值、獲取長度等方法已分析完畢，其他未分析的方法都比較簡單這里就不一一分析了，單鏈表的整體代碼最后會分享到github給大家。
2.3 帶頭結(jié)點(diǎn)的單鏈表以及循環(huán)單鏈表的實(shí)現(xiàn)
帶頭結(jié)點(diǎn)的單鏈表
前面分析的單鏈表是不帶特殊頭結(jié)點(diǎn)的，所謂的特殊頭結(jié)點(diǎn)就是一個沒有值的結(jié)點(diǎn)即：
此時空鏈表的情況如下：
那么多了頭結(jié)點(diǎn)的單向鏈表有什么好處呢？通過對沒有帶頭結(jié)點(diǎn)的單鏈表的分析，我們可以知道，在鏈表插入和刪除時都需要區(qū)分操作位，比如插入操作就分頭部插入和中間或尾部插入兩種情況（中間或尾部插入視為一種情況對待即可），如果現(xiàn)在有不帶數(shù)據(jù)的頭結(jié)點(diǎn)，那么對于單鏈表的插入和刪除不再區(qū)分操作的位置，也就是說頭部、中間、尾部插入都可以視為一種情況處理了，這是因?yàn)榇藭r頭部插入和頭部刪除無需改變head的指向了，頭部插入如下所示：
代碼如下所示：
接著再看看在頭部刪除的情況：
代碼如下：
帶頭結(jié)點(diǎn)遍歷從head.next開始：
因此無論是插入還是刪除，在有了不帶數(shù)據(jù)的頭結(jié)點(diǎn)后，在插入或者刪除時都無需區(qū)分操作位了，好~，到此我們來小結(jié)一下帶頭結(jié)點(diǎn)的單鏈表特點(diǎn)：
a.空單鏈表只有一個結(jié)點(diǎn)，head.next=null。
b.遍歷的起點(diǎn)為p=head.next。
c.頭部插入和頭部刪除無需改變head的指向。
??同時為了使鏈表在尾部插入時達(dá)到更加高效，我們可在鏈表內(nèi)增加一個尾部指向的結(jié)點(diǎn)rear（代碼中使用的是last,上面代碼中已經(jīng)使用），如果我們是在尾部添加結(jié)點(diǎn)，那么此時只要通過尾部結(jié)點(diǎn)rear進(jìn)行直接操作即可，無需從表頭遍歷到表尾，帶尾部結(jié)點(diǎn)的單鏈表如下所示：
從尾部直接插入的代碼實(shí)現(xiàn)如下：
下面看看根據(jù)index插入的代碼實(shí)現(xiàn)，由于有了頭結(jié)點(diǎn)，頭部、中間、尾部插入無需區(qū)分操作位都視為一種情況處理。
代碼如下：
??最后在看看刪除的代碼實(shí)現(xiàn)，由于刪除和插入的邏輯和之前不帶頭結(jié)點(diǎn)的單鏈表分析過的原理的是一樣的，因此我們這里不重復(fù)了，主要注意遍歷的起始結(jié)點(diǎn)變化就行。
ok~，關(guān)于帶頭結(jié)點(diǎn)的單向鏈表就分析到這，這里貼出實(shí)現(xiàn)源碼，同樣地，稍后在github上也會提供。。文章末尾提供下載地址。
循環(huán)單鏈表
有上述的分析基礎(chǔ)，循環(huán)單鏈表(Circular Single Linked List)相對來說就比較簡單了，所謂的循環(huán)單鏈表是指鏈表中的最后一個結(jié)點(diǎn)的next域指向了頭結(jié)點(diǎn)head，形成環(huán)形的結(jié)構(gòu)，我們通過圖示來理解：?
此時的循環(huán)單鏈表有如下特點(diǎn)：?
a.當(dāng)循環(huán)鏈表為空鏈表時，head指向頭結(jié)點(diǎn)，head.next=head。?
b.尾部指向rear代表最后一個結(jié)點(diǎn)，則有rear.next=head。?
在處理循環(huán)單鏈表時，我們只需要注意在遍歷循環(huán)鏈表時，避免進(jìn)入死循環(huán)即可，也就是在判斷循環(huán)鏈表是否到達(dá)結(jié)尾時，由之前的如下判斷：
//從head.next開始遍歷
Node item=head.next;
while (item!=null){
? ? item=item.next;
}
在循環(huán)單鏈表中改為如下判斷：
Node p=head;
while (p!=head){
p=p.next;
}
具體代碼實(shí)現(xiàn)，詳見github地址，文章末尾給出。
查找CircleHeadILinkedList.java文件。
2.3 單鏈表的效率分析
由于單鏈表并不是隨機(jī)存取結(jié)構(gòu)，即使單鏈表在訪問第一個結(jié)點(diǎn)時花費(fèi)的時間為常數(shù)時間，但是如果需要訪問第i(0），也就是說get(i)和set(i,x)的時間復(fù)雜度都為O(n)。
由于鏈表在插入和刪除結(jié)點(diǎn)方面十分高效的，因此鏈表比較適合那些插入刪除頻繁的場景使用。如果是單鏈表的話，插入和刪除的時間復(fù)雜度都是O(n)。
問題是大部分情況下查找所需時間比移動短多了，還有就是鏈表不需要連續(xù)空間也不需要擴(kuò)容操作，因此即使時間復(fù)雜度都是O(n)，所以相對來說鏈表更適合插入刪除操作。
參考文章：順序表和鏈表的深入分析。
