邏輯結(jié)構(gòu)中的線性表，線性表的順序存儲(chǔ)

一、線性表綜述

本篇博客我們主要介紹的是邏輯結(jié)構(gòu)中的線性表，也就是線性結(jié)構(gòu)。線性結(jié)構(gòu)的特點(diǎn)就好比一串珠子，其特點(diǎn)是第一個(gè)節(jié)點(diǎn)只有一個(gè)后繼，沒(méi)有前驅(qū)，最后一個(gè)節(jié)點(diǎn)是只有一個(gè)前驅(qū)，沒(méi)有后繼。而其余的節(jié)點(diǎn)只有一個(gè)前驅(qū)和一個(gè)后繼。說(shuō)罷了線性表就是一串。下方這個(gè)圖就是線性表的示例圖。中間藍(lán)色的節(jié)點(diǎn)前方的是就是改點(diǎn)對(duì)應(yīng)的前驅(qū)，后邊就是改點(diǎn)對(duì)應(yīng)的后繼。從下方可以明確看出head沒(méi)有前驅(qū)只有后繼，而tail只有前驅(qū)沒(méi)有后繼。

上面這個(gè)是線性表的邏輯結(jié)構(gòu)，接下來(lái)我們來(lái)聊一下線性表的物理結(jié)構(gòu)，也就是存儲(chǔ)結(jié)構(gòu)。線性表的物理結(jié)構(gòu)可分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)之所以稱之為順序存儲(chǔ)結(jié)構(gòu)因?yàn)槊總€(gè)線性表中節(jié)點(diǎn)的內(nèi)存地址是連續(xù)的，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中線性表的節(jié)點(diǎn)的內(nèi)存地址可以是不連續(xù)的。這也就是在C語(yǔ)言實(shí)現(xiàn)順序存儲(chǔ)線性表時(shí)先Malloc一塊連續(xù)的區(qū)域，然后用來(lái)順序的存儲(chǔ)線性表。而鏈表中就可以不是連續(xù)的了，前驅(qū)與后繼間的關(guān)系由指針連接。

下方這個(gè)指示圖中，上面這個(gè)就是鏈?zhǔn)酱鎯?chǔ)，下方這個(gè)就是順序存儲(chǔ)?？梢?jiàn)鏈?zhǔn)酱鎯?chǔ)是有指針域的，也就是前驅(qū)和后繼的關(guān)系有指針來(lái)鏈接。下方這個(gè)鏈?zhǔn)酱鎯?chǔ)就是單向鏈表，因?yàn)橹挥星膀?qū)到后繼的指針，而沒(méi)有后繼到前驅(qū)的指針。關(guān)于雙向鏈表下方會(huì)具體給出詳細(xì)的說(shuō)明。而下面第二個(gè)圖就是順序存儲(chǔ)，前驅(qū)與后繼的關(guān)系是由緊挨的內(nèi)存地址所關(guān)聯(lián)。

上面這兩種存儲(chǔ)方式我們可以換另一種更為形象的方式來(lái)進(jìn)行說(shuō)明，如下所示。順序存儲(chǔ)的內(nèi)存區(qū)塊的內(nèi)存地址是緊挨的，線性關(guān)系有相鄰的內(nèi)存地址所保存。當(dāng)然下方我們是模擬的內(nèi)存地址，就使用了0x1， 0x2等等來(lái)模擬。而鏈?zhǔn)酱鎯?chǔ)的線性表，在物理存儲(chǔ)結(jié)構(gòu)中是不相鄰的，僅僅靠?jī)?nèi)存地址無(wú)法去維持這種線性關(guān)系。所以就需要一個(gè)指針域來(lái)指向后繼或者前驅(qū)節(jié)點(diǎn)的內(nèi)存地址，從而將節(jié)點(diǎn)之間進(jìn)行關(guān)聯(lián)。在單向鏈?zhǔn)酱鎯?chǔ)中，一個(gè)節(jié)點(diǎn)不僅僅需要存儲(chǔ)數(shù)據(jù)，而且還要存儲(chǔ)該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的內(nèi)存地址，以便保持這種線性關(guān)系。具體請(qǐng)看下圖。

原理性質(zhì)的東西先就聊這么多，下面我們會(huì)給出具體實(shí)現(xiàn)。主要包括線性表的順序存儲(chǔ)及其操作，以及線性表的單鏈以及雙鏈存儲(chǔ)及其操作。下方的實(shí)例依然采用Swift面向?qū)ο笳Z(yǔ)言實(shí)現(xiàn)，思想理解后，用什么語(yǔ)言都是可以的呢。

二、線性表的順序存儲(chǔ)

關(guān)于線性表的順序存儲(chǔ)，我們就使用NSMutableArray來(lái)實(shí)現(xiàn)，也就是使用OC中的可變數(shù)組類型來(lái)實(shí)現(xiàn)。我們就假設(shè)其存儲(chǔ)的內(nèi)存地址是連續(xù)的，當(dāng)然數(shù)組中存儲(chǔ)對(duì)象時(shí)要復(fù)雜得多，我們暫且假設(shè)其中的地址是連續(xù)的。下方的list就是我們的順序線性表，count存儲(chǔ)的是已經(jīng)存入到線性表中的元素個(gè)數(shù)，而capacity則是記錄線性表整個(gè)容量的大小。當(dāng)然上述三個(gè)屬性都是private的，而下方的計(jì)算屬性length是internal類型的，供外界訪問(wèn)，返回線性表元素的個(gè)數(shù)。

下方是整體結(jié)構(gòu)，我們下方會(huì)給出線性表具體的關(guān)鍵操作，并分析其時(shí)間復(fù)雜度。

1.往順序線性表中插入數(shù)據(jù)

有時(shí)候我們會(huì)給據(jù)特定的算法往線性表中指定的位置插入數(shù)據(jù)，比如我們常見(jiàn)的插入排序算法，如果你的數(shù)據(jù)是順序存儲(chǔ)的話，那么就需要將數(shù)據(jù)插入到順序表中。接下來(lái)我們就將數(shù)據(jù)插入到指定的位置。

下方該圖中是往順序表中插入一個(gè)元素的原理圖。在下圖中，我們往AB與CD之間插入一個(gè)M。在插入M之前我們需要做的事情就是將CD整體往后移動(dòng)一個(gè)位置，為M騰出一個(gè)位置，然后再將M這個(gè)元素進(jìn)行插入。

順序表的插入還是比較簡(jiǎn)單的，也是非常好理解的，那么用代碼實(shí)現(xiàn)起來(lái)也是用不了幾行代碼的。下方截圖就是是順序線性表的元素插入的具體實(shí)現(xiàn)的代碼。首先檢查index的合法性，檢查index是否在合理范圍內(nèi)，然后將index后的元素依次往后移動(dòng)，然后將元素插入即可。

2. 順序線性表的元素移除

上面介紹完元素的插入后，接下來(lái)要聊一下元素的移除。也就是移除指定索引中的元素。該過(guò)程恰好與上述插入的過(guò)程相反，上述在插入之前是相應(yīng)的元素往后移，騰出index位置。而移除特定索引的元素時(shí)，是相應(yīng)的元素左移，覆蓋掉要?jiǎng)h除的元素，然后將最后一個(gè)元素進(jìn)行移除掉。下方的原理圖對(duì)此過(guò)程進(jìn)行了說(shuō)明。

該部分比較簡(jiǎn)單，下方的代碼段就是將指定索引的元素進(jìn)行移除。在線性表的順序存儲(chǔ)中，前驅(qū)和后繼的關(guān)系由內(nèi)存地址的先后順序所關(guān)聯(lián)，所以插入和刪除元素會(huì)相對(duì)麻煩一些，而查找和修改元素就比較簡(jiǎn)單了，直接由index可以找到相應(yīng)的元素，再次就不做過(guò)多贅述了。github上所分享的Demo中會(huì)有完整示例。

三、線性表的單鏈存儲(chǔ)

介紹完線性表的順序存儲(chǔ)，接下來(lái)我們來(lái)介紹線性表的鏈?zhǔn)酱鎯?chǔ)。當(dāng)然，本部分是對(duì)單向鏈表的介紹，下部分將會(huì)對(duì)雙向鏈表的介紹。下方截圖就是我們單向鏈表相關(guān)示例的運(yùn)行結(jié)果，首先我們先正向的創(chuàng)建鏈表，也就是后來(lái)的元素插入到鏈表的后方。然后在給出逆向創(chuàng)建鏈表，與正向創(chuàng)建鏈表相反，后來(lái)的元素?fù)饺氲筋^結(jié)點(diǎn)的后方。創(chuàng)建鏈表完畢后，我們會(huì)給出鏈表元素的插入和移除的解決方案。

1.單向鏈表的創(chuàng)建

在鏈表創(chuàng)建之前，我們得先創(chuàng)建節(jié)點(diǎn)的類，因?yàn)殒湵硎嵌鄠€(gè)節(jié)點(diǎn)的連接。下方這個(gè)OneDirectionLinkListNote類就是單向鏈表的節(jié)點(diǎn)類。其中的data屬性存儲(chǔ)的是該節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)，而變量next就是指向下一個(gè)節(jié)點(diǎn)的指針，鏈表中節(jié)點(diǎn)間的關(guān)系由next指針?biāo)P(guān)聯(lián)。init和deinit就是該類的構(gòu)造和析構(gòu)函數(shù)了，就不做過(guò)多贅述了。

2.鏈表協(xié)議的創(chuàng)建

在創(chuàng)建鏈表之前，我們可以先創(chuàng)建一個(gè)鏈表協(xié)議ListProtocalType。在ListProtocalType協(xié)議中定義了鏈表所必須的方法，無(wú)論是單向鏈表還是雙向鏈表都要遵循該協(xié)議。其實(shí)這就是“面向接口”的體現(xiàn)。單向鏈表與雙向鏈表都遵循了這協(xié)議，那么說(shuō)明這兩種鏈表對(duì)外的接口是一致的，這樣便于程序的維護(hù)，這也是面向接口編程的好處。下方就是我們事先定義好的ListProtocalType協(xié)議的部分內(nèi)容。

下方協(xié)議中只給出了方法的定義，未給出具體實(shí)現(xiàn)。所有鏈表都要遵循該協(xié)議，ListProtocalType中定義了鏈表結(jié)構(gòu)所必須的方法?？梢哉f(shuō)下方這個(gè)協(xié)議就是鏈表的大綱。

3.單向鏈表的構(gòu)建

下方就是我們單向鏈表類的屬性和構(gòu)造函數(shù)。headNote就是我們鏈表的頭結(jié)點(diǎn)，而tailNote是我們鏈表的尾結(jié)點(diǎn)。length就是我們鏈表的長(zhǎng)度，也就是我們鏈表中元素的個(gè)數(shù)。一個(gè)空鏈表中tailNote = headNote。

下方我們將會(huì)介紹鏈表的正向創(chuàng)建和逆向創(chuàng)建。 下方這個(gè)截圖中就是正向創(chuàng)建鏈表，其實(shí)就是將新創(chuàng)建的數(shù)據(jù)往鏈表的尾部插入，然后更新一下tail的位置即可。關(guān)鍵步驟就兩步，第一步是tail-》next = newNode，第二步是tail = newNode。插入步驟如下所示：

上面這個(gè)示意圖是往鏈表的后方添加元素，接下來(lái)是往鏈表的頭部插入元素。該過(guò)程也是由關(guān)鍵的兩步組成，第一步就是newNode-》next = head-》next，第二步是head-》next = newNode。經(jīng)過(guò)這兩步我們就可以把元素插入到頭結(jié)點(diǎn)的后方了。

下方這段代碼是正向創(chuàng)建鏈表的具體代碼，就是一直往鏈表的尾部插入元素。逆向創(chuàng)建鏈表的代碼就不往上粘貼了，與下方代碼類似，github上會(huì)進(jìn)行完整實(shí)例的分享。上面雖然是往頭結(jié)點(diǎn)和尾部結(jié)點(diǎn)的插入，但是原理是適用于往兩邊中間插入元素的，在此就不做過(guò)多贅述了。

4.單向鏈表元素的移除

上面我們聊完元素的插入，接下來(lái)我們要聊一下元素的移除。要想移除單向鏈表中的一個(gè)元素，首先我們得找到被移除結(jié)點(diǎn)的前驅(qū)的位置，比如是pre。當(dāng)前移除的元素是remove，讓我我們讓pre-》next = remove-》next， 然后再執(zhí)行remove-》next = nil。經(jīng)過(guò)上面這些步驟，remove這個(gè)結(jié)點(diǎn)就與鏈表脫離關(guān)系了。示意圖如下所示。

根據(jù)上述的示意圖，我們就可以給出具體的代碼實(shí)現(xiàn)了。單向鏈表的核心操作就介紹完了，其他更多細(xì)節(jié)請(qǐng)參考在github上分享的源代碼，因?yàn)槠邢?，關(guān)于單向鏈表的更多細(xì)節(jié)就不做過(guò)多贅述了。

四、雙向鏈表

如果你對(duì)單向鏈表已經(jīng)理解的話，那么理解雙向鏈表來(lái)說(shuō)并非難事。雙向鏈表與單向鏈表相比多了一個(gè)指向前驅(qū)的節(jié)點(diǎn)。我們暫且稱為將指向前驅(qū)的節(jié)點(diǎn)命名我pre指針。下方這個(gè)示意圖就是雙向鏈表的示意圖，與單向鏈表相比，多了一個(gè)指向前驅(qū)的指針域。如下所示。接下來(lái)將會(huì)給出雙向鏈表的插入和移除。

1.雙向鏈表元素的插入

雙向鏈表的插入要比單向鏈表的插入要復(fù)雜一些，不過(guò)也是蠻好理解的。下方示意圖中就是往節(jié)點(diǎn)A后方插入一個(gè)節(jié)點(diǎn)D。主要分為四個(gè)步驟，第一步是將D節(jié)點(diǎn)的next指針指向A節(jié)點(diǎn)next指針指向的節(jié)點(diǎn)，也就是D-》next = A-》next。第二步是將D節(jié)點(diǎn)的pre指針指向A節(jié)點(diǎn)，也就是D-》pre = A。第三步是將A的next指針指向D，也就是A-》next = D。最后將D節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的pre指針指向D，也就是D-》next-》pre = D。經(jīng)過(guò)這幾步，我們就可以將節(jié)點(diǎn)D插入到A與B的中間。當(dāng)然這個(gè)順序不是一定的，只要能保證鏈的正確關(guān)聯(lián)即可。

下方是上述元素插入的核心代碼，如下所示。主要將newItem節(jié)點(diǎn)，插入到cursor節(jié)點(diǎn)后方。

2.雙向鏈表元素的刪除

雙向鏈表因?yàn)楸葐蜗蜴湵矶嘁粋€(gè)前驅(qū)指針域，所以元素的刪除要麻煩一下，不過(guò)還是比較好理解的。下方這個(gè)截圖就是刪除B節(jié)點(diǎn)的示意圖。首先將B節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn)的next指針域指向B節(jié)點(diǎn)的后繼，也就是B-》pre-》next = B-》next。 然后將B節(jié)點(diǎn)的后繼節(jié)點(diǎn)的前驅(qū)指針指向B的前驅(qū)節(jié)點(diǎn)，對(duì)應(yīng)著B(niǎo)-》next-pre = B-》pre。最后將B的next和pre指針域置為nil。如下所示：

下方代碼段就是雙向鏈表移除節(jié)點(diǎn)的具體實(shí)現(xiàn)，如下所示。至于鏈表的遍歷等其他操作在此就不做過(guò)多的贅述了，具體內(nèi)容請(qǐng)看github上分享的源代碼。

五、面向接口編程的優(yōu)點(diǎn)

在上述我們實(shí)現(xiàn)兩種鏈表時(shí)，我們先定義了一個(gè)鏈表協(xié)議ListProtocalType。無(wú)論是雙向鏈表還是單向鏈表都遵循這個(gè)協(xié)議，也就是說(shuō)，該協(xié)議就是鏈表對(duì)外統(tǒng)一的接口，該協(xié)議就是操作鏈表的一個(gè)規(guī)范。下方的testLinkedList（）就是我們鏈表的測(cè)試方法，該函數(shù)的參數(shù)是遵循ListProtocalType協(xié)議的所有類的對(duì)象。也就是說(shuō)只要遵循了ListProtocalType這個(gè)協(xié)議的類的對(duì)象，都可以作為該函數(shù)的參數(shù)。至于具體操作，那么不同的類會(huì)給出不同的操作的。

在調(diào)用該函數(shù)時(shí)，第一個(gè)傳入的是單向鏈表的類的對(duì)象，第二個(gè)是雙向鏈表的類的對(duì)象。雖然都是執(zhí)行同一個(gè)方法，但是因?yàn)閭魅氲念惖膶?duì)象不同，所以執(zhí)行的結(jié)果顯然是不同的。這也就是利用了面向?qū)ο蟮亩鄳B(tài)性，在之前設(shè)計(jì)模式系列的博客中介紹過(guò)，下方這種與策略模式類似。

責(zé)任編輯人：CC?