本文內(nèi)容取自于小甲魚(yú)的數(shù)據(jù)結(jié)構(gòu)與算法。http://www.itdecent.cn/p/230e6fde9c75

1. 線(xiàn)性表

線(xiàn)性表（List）：由零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列。

這里需要強(qiáng)調(diào)幾個(gè)關(guān)鍵的地方：

首先它是一個(gè)序列，也就是說(shuō)元素之間是有個(gè)先來(lái)后到的。若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，而最后一個(gè)元素?zé)o后繼，其他元素都有且只有一個(gè)前驅(qū)和后繼。另外，線(xiàn)性表強(qiáng)調(diào)是有限的，事實(shí)上無(wú)論計(jì)算機(jī)發(fā)展到多強(qiáng)大，它所處理的元素都是有限的。

若將線(xiàn)性表記為（a1,…,ai-1,ai,ai+1,…an）,則表中ai-1領(lǐng)先于ai,ai領(lǐng)先于ai+1,稱(chēng)ai-1是ai的直接前驅(qū)元素,ai+1是ai的直接后繼元素。

所以線(xiàn)性表元素的個(gè)數(shù)n(n>=0)定義為線(xiàn)性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱(chēng)為空表。

1.1 線(xiàn)性表之?dāng)?shù)組

1.1.1 操作

(1) 定義線(xiàn)性表

線(xiàn)性表存儲(chǔ)結(jié)構(gòu)定義：

大家看到了，這里我們封裝了一個(gè)結(jié)構(gòu)，事實(shí)上就是對(duì)數(shù)組進(jìn)行封裝，增加了個(gè)當(dāng)前長(zhǎng)度的變量罷了。

總結(jié)下，順序存儲(chǔ)結(jié)構(gòu)封裝需要三個(gè)屬性：

存儲(chǔ)空間的起始位置，數(shù)組data，它的存儲(chǔ)位置就是線(xiàn)性表存儲(chǔ)空間的存儲(chǔ)位置。

線(xiàn)性表的最大存儲(chǔ)容量：數(shù)組的長(zhǎng)度MaxSize。

線(xiàn)性表的當(dāng)前長(zhǎng)度：length。

注意，數(shù)組的長(zhǎng)度與線(xiàn)性表的當(dāng)前長(zhǎng)度需要區(qū)分一下：

數(shù)組的長(zhǎng)度是存放線(xiàn)性表的存儲(chǔ)空間的總長(zhǎng)度，一般初始化后不變。

而線(xiàn)性表的當(dāng)前長(zhǎng)度是線(xiàn)性表中元素的個(gè)數(shù)，是會(huì)變化的。

(2) 獲取元素

實(shí)現(xiàn)GetElem的具體操作，即將線(xiàn)性表L中的第i個(gè)位置元素值返回。就程序而言非常簡(jiǎn)單了，我們只需要把數(shù)組第i-1下標(biāo)的值返回即可。

(3) 插入元素

1. 如果插入位置不合理，拋出異常；

2. 如果線(xiàn)性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度，則拋出異?；騽?dòng)態(tài)增加數(shù)組容量；

3. 從最后一個(gè)元素開(kāi)始向前遍歷到第i個(gè)位置，分別將它們都向后移動(dòng)一個(gè)位置；

4. 將要插入元素填入位置i處；

5. 線(xiàn)性表長(zhǎng)+1。

(4) 刪除元素

1. 如果刪除位置不合理，拋出異常；

2. 取出刪除元素；

3. 從刪除元素位置開(kāi)始遍歷到最后一個(gè)元素位置，分別將它們都向前移動(dòng)一個(gè)位置；

4. 表長(zhǎng)-1。

1.1.2 優(yōu)缺點(diǎn)

線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，在存、讀數(shù)據(jù)時(shí)，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是O(1)。而在插入或刪除時(shí)，時(shí)間復(fù)雜度都是O(n)。這就說(shuō)明，它比較適合元素個(gè)數(shù)比較穩(wěn)定，不經(jīng)常插入和刪除元素，而更多的操作是存取數(shù)據(jù)的應(yīng)用。

(1) 優(yōu)點(diǎn)

無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間。

可以快速地存取表中任意位置的元素。

(2) 缺點(diǎn)

插入和刪除操作需要移動(dòng)大量元素。

當(dāng)線(xiàn)性表長(zhǎng)度變化較大時(shí)，難以確定存儲(chǔ)空間的容量。

容易造成存儲(chǔ)空間的“碎片”。

1.2 線(xiàn)性表之鏈表

前面我們講的線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，它最大的缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量元素，這顯然就需要耗費(fèi)時(shí)間。那我們能不能針對(duì)這個(gè)缺陷或者說(shuō)遺憾提出解決的方法呢？要解決這個(gè)問(wèn)題，我們就得考慮一下導(dǎo)致這個(gè)問(wèn)題的原因！為什么當(dāng)插入和刪除時(shí)，就要移動(dòng)大量的元素？原因就在于相鄰兩元素的存儲(chǔ)位置也具有鄰居關(guān)系，它們?cè)趦?nèi)存中的位置是緊挨著的，中間沒(méi)有間隙，當(dāng)然就無(wú)法快速插入和刪除。

線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以存在內(nèi)存中未被占用的任意位置。比起順序存儲(chǔ)結(jié)構(gòu)每個(gè)數(shù)據(jù)元素只需要存儲(chǔ)一個(gè)位置就可以了。

1.2.1 單鏈表

現(xiàn)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，除了要存儲(chǔ)數(shù)據(jù)元素信息外，還要存儲(chǔ)它的后繼元素的存儲(chǔ)地址（指針）。也就是說(shuō)除了存儲(chǔ)其本身的信息外，還需存儲(chǔ)一個(gè)指示其直接后繼的存儲(chǔ)位置的信息。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱(chēng)為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱(chēng)為指針域。指針域中存儲(chǔ)的信息稱(chēng)為指針或鏈。這兩部分信息組成數(shù)據(jù)元素稱(chēng)為存儲(chǔ)映像，稱(chēng)為結(jié)點(diǎn)(Node)。n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線(xiàn)性表(a1, a2, a3, …, an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以叫做單鏈表。

對(duì)于線(xiàn)性表來(lái)說(shuō)，總得有個(gè)頭有個(gè)尾，鏈表也不例外。我們把鏈表中的第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針，最后一個(gè)結(jié)點(diǎn)指針為空(NULL)。

頭指針：

1. 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針。

2. 頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字（指針變量的名字）。

3. 無(wú)論鏈表是否為空，頭指針均不為空。

4. 頭指針是鏈表的必要元素。

頭結(jié)點(diǎn)：

1. 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一個(gè)元素的結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義（但也可以用來(lái)存放鏈表的長(zhǎng)度）。

2. 有了頭結(jié)點(diǎn)，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)起操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了。

3. 頭結(jié)點(diǎn)不一定是鏈表的必須要素。

1.2.1.1 操作

(1) 定義單鏈表

我們看到結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成。假設(shè)p是指向線(xiàn)性表第i個(gè)元素的指針，則該結(jié)點(diǎn)ai的數(shù)據(jù)域我們可以用p->data的值是一個(gè)數(shù)據(jù)元素。結(jié)點(diǎn)ai的指針域可以用p->next來(lái)表示，p->next的值是一個(gè)指針。那么p->next指向誰(shuí)呢？當(dāng)然指向第i+1個(gè)元素！也就是指向ai+1的指針。

問(wèn)題：如果p->data = ai，那么p->next->data = ?

答案：p->next->data = ai+1。

(2) 讀取元素

在線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)中，我們要計(jì)算任意一個(gè)元素的存儲(chǔ)位置是很容易的。但在單鏈表中，由于第i個(gè)元素到底在哪？我們壓根兒沒(méi)辦法一開(kāi)始就知道，必須得從第一個(gè)結(jié)點(diǎn)開(kāi)始挨個(gè)兒找。因此，對(duì)于單鏈表實(shí)現(xiàn)獲取第i個(gè)元素的數(shù)據(jù)的操作GetElem，在算法上相對(duì)要麻煩一些。

1. 聲明一個(gè)結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j從1開(kāi)始；

2. 當(dāng)j<i, 就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j+1

3. 若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；

4. 否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)。

(3) 插入元素

我們先來(lái)看下單鏈表的插入。假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)結(jié)點(diǎn)p、p->next和s之間邏輯關(guān)系的變化，大家參考下圖思考一下：

我們思考后發(fā)覺(jué)根本用不著驚動(dòng)其他結(jié)點(diǎn)，只需要讓s->next和p->next的指針做一點(diǎn)改變。

s->next = p->next;

p->next = s;

我們通過(guò)圖片來(lái)解讀一下這兩句代碼。

那么我們考慮一下大部分初學(xué)者最容易搞壞腦子的問(wèn)題：這兩句代碼的順序可不可以交換過(guò)來(lái)？先 p->next = s;再 s->next = p->next;

大家發(fā)現(xiàn)沒(méi)有？如果先執(zhí)行p->next的話(huà)會(huì)先被覆蓋為s的地址，那么s->next = p->next其實(shí)就等于s->next = s了。所以這兩句是無(wú)論如何不能弄反的，這點(diǎn)初學(xué)者一定要注意咯~

思路：

1. 聲明一結(jié)點(diǎn)p指向鏈表頭結(jié)點(diǎn)，初始化j從1開(kāi)始；

2. 當(dāng)j<1時(shí)，就遍歷鏈表，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)，j累加1；

3. 若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；

4. 否則查找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn)s；

5. 將數(shù)據(jù)元素e賦值給s->data；

6. 單鏈表的插入剛才兩個(gè)標(biāo)準(zhǔn)語(yǔ)句；

7. 返回成功。

(4) 刪除元素

現(xiàn)在我們?cè)賮?lái)看單鏈表的刪除操作。

假設(shè)元素a2的結(jié)點(diǎn)為q，要實(shí)現(xiàn)結(jié)點(diǎn)q刪除單鏈表的操作，其實(shí)就是將它的前繼結(jié)點(diǎn)的指針繞過(guò)指向后繼結(jié)點(diǎn)即可。那我們所要做的，實(shí)際上就是一步：

可以這樣：p->next = p->next->next; 也可以是：q=p->next; p->next=q->next。

思路：

1. 聲明結(jié)點(diǎn)p指向鏈表第一個(gè)結(jié)點(diǎn)，初始化j=1；

2. 當(dāng)j<1時(shí)，就遍歷鏈表，讓P的指針向后移動(dòng)，不斷指向下一個(gè)結(jié)點(diǎn)，j累加1；

3. 若到鏈表末尾p為空，則說(shuō)明第i個(gè)元素不存在；

4. 否則查找成功，將欲刪除結(jié)點(diǎn)p->next賦值給q；

5. 單鏈表的刪除標(biāo)準(zhǔn)語(yǔ)句p->next = q->next；

6. 將q結(jié)點(diǎn)中的數(shù)據(jù)賦值給e，作為返回；

7. 釋放q結(jié)點(diǎn)。

1.2.1.2 單鏈表的整表建立

對(duì)于順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表的整表創(chuàng)建，我們可以用數(shù)組的初始化來(lái)直觀(guān)理解。

而單鏈表和順序存儲(chǔ)結(jié)構(gòu)就不一樣了，它不像順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)這么集中，它的數(shù)據(jù)可以是分散在內(nèi)存各個(gè)角落的，他的增長(zhǎng)也是動(dòng)態(tài)的。對(duì)于每個(gè)鏈表來(lái)說(shuō)，它所占用空間的大小和位置是不需要預(yù)先分配劃定的，可以根據(jù)系統(tǒng)的情況和實(shí)際的需求即時(shí)生成。

創(chuàng)建單鏈表的過(guò)程是一個(gè)動(dòng)態(tài)生成鏈表的過(guò)程，從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)并逐個(gè)插入鏈表。

思路：

1. 聲明一結(jié)點(diǎn)p和計(jì)數(shù)器變量i；

2. 初始化一空鏈表L；

3. 讓L的頭結(jié)點(diǎn)的指針指向NULL，即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表；

4. 循環(huán)實(shí)現(xiàn)后繼結(jié)點(diǎn)的賦值和插入。

(1) 頭插法建立

頭插法從一個(gè)空表開(kāi)始，生成新結(jié)點(diǎn)，讀取數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到結(jié)束為止。簡(jiǎn)單來(lái)說(shuō)，就是把新加進(jìn)的元素放在表頭后的第一個(gè)位置：先讓新節(jié)點(diǎn)的next指向頭節(jié)點(diǎn)之后，然后讓表頭的next指向新節(jié)點(diǎn)。

(2) 尾插法建立

頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。就像現(xiàn)實(shí)社會(huì)我們鄙視插隊(duì)不遵守紀(jì)律的孩子，那編程中我們也可以不這么干，我們可以把思維逆過(guò)來(lái)：把新結(jié)點(diǎn)都插入到最后，這種算法稱(chēng)之為尾插法。

1.2.1.3 單鏈表的整表刪除

當(dāng)我們不打算使用這個(gè)單鏈表時(shí)，我們需要把它銷(xiāo)毀（真狠，不要就給別人嘛，還銷(xiāo)毀~）。

其實(shí)也就是在內(nèi)存中將它釋放掉，以便于留出空間給其他程序或軟件使用。

思路：

1. 聲明結(jié)點(diǎn)p和q；

2. 將第一個(gè)結(jié)點(diǎn)賦值給p，下一結(jié)點(diǎn)賦值給q；

3. 循環(huán)執(zhí)行釋放p和將q賦值給p的操作；

這段算法代碼里，常見(jiàn)的錯(cuò)誤就是有同學(xué)會(huì)覺(jué)得q變量沒(méi)有存在的必要，只需要在循環(huán)體內(nèi)直接寫(xiě)free(p); p = p->next; 即可？

可這個(gè)世上沒(méi)有無(wú)緣無(wú)故的愛(ài)，這樣做會(huì)帶來(lái)什么問(wèn)題呢？

要知道p是一個(gè)結(jié)點(diǎn)，它除了有數(shù)據(jù)域，還有指針域。當(dāng)我們做free(p);時(shí)候，其實(shí)是對(duì)它整個(gè)結(jié)點(diǎn)進(jìn)行刪除和內(nèi)存釋放的工作。而我們整表刪除

是需要一個(gè)個(gè)結(jié)點(diǎn)刪除的，所以我們就需要q來(lái)記載p的下一個(gè)結(jié)點(diǎn)。

1.2.1.4 優(yōu)缺點(diǎn)

我們分別從存儲(chǔ)分配方式、時(shí)間性能、空間性能三方面來(lái)做對(duì)比。

(1) 存儲(chǔ)分配方式

順序存儲(chǔ)結(jié)構(gòu)用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素。

單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線(xiàn)性表的元素。

(2) 時(shí)間性能

查找:?順序存儲(chǔ)結(jié)構(gòu)O(1), 單鏈表O(n)

插入和刪除:

順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一半的元素，時(shí)間為O(n)

單鏈表在計(jì)算出某位置的指針后，插入和刪除時(shí)間僅為O(1)

(3) 空間性能

順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了，容易造成空間浪費(fèi)，分小了，容易發(fā)生溢出。

單鏈表不需要分配存儲(chǔ)空間，只要有就可以分配，元素個(gè)數(shù)也不受限制。

總而言之，

若線(xiàn)性表需要頻繁查找，很少進(jìn)行插入和刪除操作時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)。

若需要頻繁插入和刪除時(shí)，宜采用單鏈表結(jié)構(gòu)。

比如說(shuō)游戲開(kāi)發(fā)中，對(duì)于用戶(hù)注冊(cè)的個(gè)人信息，除了注冊(cè)時(shí)插入數(shù)據(jù)外，絕大多數(shù)情況都是讀取，所以應(yīng)該考慮用順序存儲(chǔ)結(jié)構(gòu)。

而游戲中的玩家的武器或者裝備列表，隨著玩家的游戲過(guò)程中，可能會(huì)隨時(shí)增加或刪除，此時(shí)再用順序存儲(chǔ)就不太合適了，單鏈表結(jié)構(gòu)就可以大展拳腳了。

當(dāng)線(xiàn)性表中的元素個(gè)數(shù)變化較大或者根本不知道有多大時(shí)，最好用單鏈表結(jié)構(gòu)，這樣可以不需要考慮存儲(chǔ)空間的大小問(wèn)題。

而如果事先知道線(xiàn)性表的大致長(zhǎng)度，比如一年12個(gè)月，一周就是星期一至星期日共七天，這種用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高很多。

1.2.2 靜態(tài)鏈表

用數(shù)組描述的鏈表叫做靜態(tài)鏈表，這種描述方法叫做游標(biāo)實(shí)現(xiàn)法。

1.2.2.1 定義靜態(tài)鏈表

我們對(duì)數(shù)組的第一個(gè)和最后一個(gè)元素做特殊處理，他們的data不存放數(shù)據(jù)。我們通常把未使用的數(shù)組元素稱(chēng)為備用鏈表。數(shù)組的第一個(gè)元素，即下標(biāo)為0的那個(gè)元素的cur就存放備用鏈表的第一個(gè)結(jié)點(diǎn)的下標(biāo)。數(shù)組的最后一個(gè)元素，即下標(biāo)為MAXSIZE-1的cur則存放第一個(gè)有數(shù)值的元素的下標(biāo)，相當(dāng)于單鏈表中的頭結(jié)點(diǎn)作用。

1.2.2.2 插入

1.2.2.3 刪除

回收空閑游標(biāo)。

1.2.2.4 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

在插入和刪除操作時(shí)，只需要修改游標(biāo)，不需要移動(dòng)元素，從而改進(jìn)了在順序存儲(chǔ)結(jié)構(gòu)中的插入和刪除操作需要移動(dòng)大量元素的缺點(diǎn)。

缺點(diǎn)：

沒(méi)有解決連續(xù)存儲(chǔ)分配（數(shù)組）帶來(lái)的表長(zhǎng)難以確定的問(wèn)題。

失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的特性。

總的來(lái)說(shuō)，靜態(tài)鏈表其實(shí)是為了給沒(méi)有指針的編程語(yǔ)言設(shè)計(jì)的一種實(shí)現(xiàn)單鏈表功能的方法。

盡管我們可以用單鏈表就不用靜態(tài)鏈表了，但這樣的思考方式是非常巧妙的，應(yīng)該理解其思想，以備不時(shí)之需。

1.2.2.5 單鏈表面試題

題目：快速找到未知長(zhǎng)度單鏈表的中間節(jié)點(diǎn)。

既然是面試題就一定有普通方法和高級(jí)方法。

普通的方法很簡(jiǎn)單，首先遍歷一遍單鏈表以確定單鏈表的長(zhǎng)度L。然后再次從頭節(jié)點(diǎn)出發(fā)循環(huán)L/2次找到單鏈表的中間節(jié)點(diǎn)。

算法復(fù)雜度為：O(L+L/2)=O(3L/2)。

高級(jí)的方法：利用快慢指針！

利用快慢指針原理：設(shè)置兩個(gè)指針*search、*mid都指向單鏈表的頭節(jié)點(diǎn)。其中* search的移動(dòng)速度是*mid的2倍。當(dāng)*search指向末尾節(jié)點(diǎn)的時(shí)候，mid正好就在中間了。這也是標(biāo)尺的思想。

1.2.3 循環(huán)鏈表

對(duì)于單鏈表，由于每個(gè)結(jié)點(diǎn)只存儲(chǔ)了向后的指針，到了尾部標(biāo)識(shí)就停止了向后鏈的操作。也就是說(shuō)，按照這樣的方式，只能索引后繼結(jié)點(diǎn)不能索引前驅(qū)結(jié)點(diǎn)。這會(huì)帶來(lái)什么問(wèn)題呢？例如不從頭結(jié)點(diǎn)出發(fā)，就無(wú)法訪(fǎng)問(wèn)到全部結(jié)點(diǎn)。

事實(shí)上要解決這個(gè)問(wèn)題也并不麻煩，只需要將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，問(wèn)題就結(jié)了。將單鏈表中終端結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)，這種頭尾相接的單鏈表成為單循環(huán)鏈表，簡(jiǎn)稱(chēng)循環(huán)鏈表。

注：這里并不是說(shuō)循環(huán)鏈表一定要有頭結(jié)點(diǎn)。

其實(shí)循環(huán)鏈表的單鏈表的主要差異就在于循環(huán)的判斷空鏈表的條件上，原來(lái)判斷head->next是否為null，現(xiàn)在則是head->next是否等于head。回到剛才的問(wèn)題，由于終端結(jié)點(diǎn)用尾指針rear指示，則查找終端結(jié)點(diǎn)是O(1)，而開(kāi)始結(jié)點(diǎn)是rear->next->next，當(dāng)然也是O(1)。

1.2.3 帶環(huán)單鏈表

有環(huán)的定義是，鏈表的尾節(jié)點(diǎn)指向了鏈表中的某個(gè)節(jié)點(diǎn)。

那么要判斷單鏈表中是否有環(huán)，主要有以下兩種方法：

方法一：使用p、q兩個(gè)指針，p總是向前走，但q每次都從頭開(kāi)始走，對(duì)于每個(gè)節(jié)點(diǎn)，看p走的步數(shù)是否和q一樣。如圖，當(dāng)p從6走到3時(shí)，用了6步，此時(shí)若q從head出發(fā)，則只需兩步就到3，因而步數(shù)不等，出現(xiàn)矛盾，存在環(huán)。

方法二：使用p、q兩個(gè)指針，p每次向前走一步，q每次向前走兩步，若在某個(gè)時(shí)候p == q，則存在環(huán)。

1.2.4 雙向鏈表

大家都知道，任何事物出現(xiàn)的初期都顯得有些不完善。例如我們的火車(chē)剛發(fā)明的時(shí)候是只有一個(gè)“頭”的，所以如果它走的線(xiàn)路是如下：

A->B->C->D->E->F->G->H->I->J->K->L->A

假設(shè)這會(huì)兒火車(chē)正停在K處呢，要他送一批貨到J處，那么它將走的路線(xiàn)是：

K->L->A->B->C->D->E->F->G->H->I->J

嗯，所以后來(lái)我們的火車(chē)就都有兩個(gè)頭了。看完這個(gè)例子，大家就明白雙向鏈表的必要性了吧。

1.2.4.1 建立雙向鏈表

1.2.4.2 插入

1.2.4.3 刪除

1.2.4 雙向循環(huán)鏈表

2. 棧

官方定義：棧（Stack）是一個(gè)后進(jìn)先出（Last in first out,LIFO）的線(xiàn)性表，它要求只在表尾進(jìn)行刪除和插入操作。

小甲魚(yú)定義：所謂的棧，其實(shí)也就是一個(gè)特殊的線(xiàn)性表（順序表、鏈表），但是它在操作上有一些特殊的要求和限制：棧的元素必須“后進(jìn)先出”。棧的操作只能在這個(gè)線(xiàn)性表的表尾進(jìn)行。

注：對(duì)于棧來(lái)說(shuō)，這個(gè)表尾稱(chēng)為棧的棧頂（top），相應(yīng)的表頭稱(chēng)為棧底（bottom）。

棧的插入操作（Push），叫做進(jìn)棧，也稱(chēng)為壓棧，入棧。類(lèi)似子彈放入彈夾的動(dòng)作。

棧的刪除操作（Pop），叫做出棧，也稱(chēng)為彈棧。如同彈夾中的子彈出夾。

2.1 棧的順序存儲(chǔ)結(jié)構(gòu)

因?yàn)闂５谋举|(zhì)是一個(gè)線(xiàn)性表，線(xiàn)性表有兩種存儲(chǔ)形式，那么棧也有分為棧的順序存儲(chǔ)結(jié)構(gòu)和棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。最開(kāi)始棧中不含有任何數(shù)據(jù)，叫做空棧，此時(shí)棧頂就是棧底。然后數(shù)據(jù)從棧頂進(jìn)入，棧頂棧底分離，整個(gè)棧的當(dāng)前容量變大。數(shù)據(jù)出棧時(shí)從棧頂彈出，棧頂下移，整個(gè)棧的當(dāng)前容量變小。

入棧操作:?入棧操作又叫壓棧操作，就是向棧中存放數(shù)據(jù)。

入棧操作要在棧頂進(jìn)行，每次向棧中壓入一個(gè)數(shù)據(jù)，top指針就要+1，知道棧滿(mǎn)為止。

出棧操作:?出棧操作就是在棧頂取出數(shù)據(jù)，棧頂指針隨之下移的操作。

每當(dāng)從棧內(nèi)彈出一個(gè)數(shù)據(jù)，棧的當(dāng)前容量就-1。

2.1.1 清空棧

所謂清空一個(gè)棧，就是將棧中的元素全部作廢，但棧本身物理空間并不發(fā)生改變（不是銷(xiāo)毀）。因此我們只要將s->top的內(nèi)容賦值為s->base即可，這樣s->base等于s->top，也就表明這個(gè)棧是空的了。這個(gè)原理跟高級(jí)格式化一樣只是但單純地清空文件列表而沒(méi)有覆蓋硬盤(pán)的原理是一樣的。

2.1.2 銷(xiāo)毀棧

銷(xiāo)毀一個(gè)棧與清空一個(gè)棧不同，銷(xiāo)毀一個(gè)棧是要釋放掉該棧所占據(jù)的物理內(nèi)存空間，因此不要把銷(xiāo)毀一個(gè)棧與清空一個(gè)棧這兩種操作混淆。

2.1.3 計(jì)算棧的當(dāng)前容量

計(jì)算棧的當(dāng)前容量也就是計(jì)算棧中元素的個(gè)數(shù)，因此只要返回s.top-s.base即可。

注意，棧的最大容量是指該棧占據(jù)內(nèi)存空間的大小，其值是s.stackSize，它與棧的當(dāng)前容量不是一個(gè)概念哦。

2.2 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

現(xiàn)在我們來(lái)看下棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱(chēng)棧鏈。（通常我們用的都是棧的順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)我們作為一個(gè)知識(shí)點(diǎn)，大家知道就好?。?br>

棧因?yàn)橹皇菞ｍ攣?lái)做插入和刪除操作，所以比較好的方法就是將棧頂放在單鏈表的頭部，棧頂指針和單鏈表的頭指針合二為一。

2.2.1 建立棧

2.2.2 進(jìn)棧

2.2.3 出棧

3. 隊(duì)列

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線(xiàn)性表。

與棧相反，隊(duì)列是一種先進(jìn)先出（First In First Out, FIFO）的線(xiàn)性表。

與棧相同的是，隊(duì)列也是一種重要的線(xiàn)性結(jié)構(gòu)，實(shí)現(xiàn)一個(gè)隊(duì)列同樣需要順序表或鏈表作為基礎(chǔ)。

3.1 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

隊(duì)列既可以用鏈表實(shí)現(xiàn)，也可以用順序表實(shí)現(xiàn)。跟棧相反的是，棧一般我們用順序表來(lái)實(shí)現(xiàn)，而隊(duì)列我們常用鏈表來(lái)實(shí)現(xiàn)，簡(jiǎn)稱(chēng)為鏈隊(duì)列。

3.1.1 建立隊(duì)列

我們將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)，而隊(duì)尾指針指向終端結(jié)點(diǎn)。（注：頭結(jié)點(diǎn)不是必要的，但為了方便操作，我們加上了。）

空隊(duì)列時(shí)，front和rear都指向頭結(jié)點(diǎn)。

3.1.2 入隊(duì)列

3.1.3 出隊(duì)列

出隊(duì)列操作是將隊(duì)列中的第一個(gè)元素移出，隊(duì)頭指針不發(fā)生改變，改變頭結(jié)點(diǎn)的next指針即可。出隊(duì)列的操作過(guò)程如下：

如果原隊(duì)列只有一個(gè)元素，那么我們就應(yīng)該處理一下隊(duì)尾指針。

3.1.4 銷(xiāo)毀隊(duì)列

由于鏈隊(duì)列建立在內(nèi)存的動(dòng)態(tài)區(qū)，因此當(dāng)一個(gè)隊(duì)列不再有用時(shí)應(yīng)當(dāng)把它及時(shí)銷(xiāo)毀掉，以免過(guò)多地占用內(nèi)存空間。

3.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

我們先按照應(yīng)有的思路來(lái)考慮下如何構(gòu)造隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)，然后發(fā)掘都遇到了什么麻煩。

我們假設(shè)一個(gè)隊(duì)列有n個(gè)元素，則順序存儲(chǔ)的隊(duì)列需建立一個(gè)大于n的存儲(chǔ)單元，并把隊(duì)列的所有元素存儲(chǔ)在數(shù)組的前n個(gè)單元，數(shù)組下標(biāo)為0的一端則是隊(duì)頭。

入隊(duì)列操作其實(shí)就是在隊(duì)尾追加一個(gè)元素，不需要任何移動(dòng)，時(shí)間復(fù)雜度為O(1)。

出隊(duì)列則不同，因?yàn)槲覀円呀?jīng)架設(shè)下標(biāo)為0的位置是隊(duì)列的隊(duì)頭，因此每次出隊(duì)列操作所有元素都要向前移動(dòng)。

在現(xiàn)實(shí)中也是如此，一群人在排隊(duì)買(mǎi)火車(chē)票，前邊的人買(mǎi)好了離開(kāi)，后面的人就要全部向前一步補(bǔ)上空位?？墒俏覀冄芯繑?shù)據(jù)結(jié)構(gòu)和算法的一個(gè)根本目的就是要想方設(shè)法提高我們的程序的效率，按剛才的方式，出隊(duì)列的時(shí)間復(fù)雜度是O(n)，效率大打折扣！

如果我們不去限制隊(duì)頭一定要在下標(biāo)為0的位置，那么出隊(duì)列的操作就不需要移動(dòng)全體元素。

但是這樣也會(huì)出現(xiàn)一些問(wèn)題，例如按下邊的情形繼續(xù)入隊(duì)列，就會(huì)出現(xiàn)數(shù)組越界的錯(cuò)誤。

3.2.1 循環(huán)隊(duì)列

要解決假溢出的辦法就是如果后面滿(mǎn)了，就再?gòu)念^開(kāi)始，也就是頭尾相接的循環(huán)。

循環(huán)隊(duì)列它的容量是固定的，并且它的隊(duì)頭和隊(duì)尾指針都可以隨著元素入出隊(duì)列而發(fā)生改變，這樣循環(huán)隊(duì)列邏輯上就好像是一個(gè)環(huán)形存儲(chǔ)空間。但要注意的是，在實(shí)際的內(nèi)存當(dāng)中，不可能有真正的環(huán)形存儲(chǔ)區(qū)，我們只是用順序表模擬出來(lái)的邏輯上的循環(huán)。

于是我們發(fā)覺(jué)了，似乎循環(huán)隊(duì)列的實(shí)現(xiàn)只需要靈活改變front和rear指針即可。

也就是讓front或rear指針不斷加1，即時(shí)超出了地址范圍，也會(huì)自動(dòng)從頭開(kāi)始。我們可以采取取模運(yùn)算處理：

(rear+1) % QueueSize

(front+1) % QueueSize

取模就是取余數(shù)的意思，他取到的值永遠(yuǎn)不會(huì)大于除數(shù)。

3.2.1.1 定義循環(huán)隊(duì)列

3.2.1.2 入隊(duì)列

3.2.1.3 出隊(duì)列