接觸過數(shù)據(jù)結(jié)構(gòu)的小伙伴應(yīng)該都知道程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法守屉。數(shù)據(jù)結(jié)構(gòu)乃組織組織數(shù)據(jù)的結(jié)構(gòu)，算法就是對這些結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行操作心剥，可見數(shù)據(jù)結(jié)構(gòu)的重要性征堪，就連算法也是依賴于數(shù)據(jù)結(jié)構(gòu)的瘩缆。

在博客的開頭，我們先簡單的聊些數(shù)據(jù)結(jié)構(gòu)整體的東西佃蚜。數(shù)據(jù)結(jié)構(gòu)整體可以分為物理結(jié)構(gòu)和邏輯結(jié)構(gòu)咳榜，物理結(jié)構(gòu)指的是數(shù)據(jù)在磁盤、內(nèi)存等硬件上的存儲結(jié)構(gòu)爽锥，主要包括順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)涌韩。而邏輯結(jié)構(gòu)是數(shù)據(jù)本身所形成的結(jié)構(gòu)，包括集合結(jié)構(gòu)氯夷、線性結(jié)構(gòu)臣樱、樹形結(jié)構(gòu)以及圖形結(jié)構(gòu)。針對不同的數(shù)據(jù)結(jié)構(gòu)我們可以依據(jù)算法接決不同的問題腮考，如我們在以后博客中要介紹的最小生成樹雇毫，就是根據(jù)算法將帶權(quán)的連通圖轉(zhuǎn)換成最小生成樹，在轉(zhuǎn)換這個過程中我們就用到了Prim算法和克魯斯卡爾算法踩蔚。當(dāng)然各種排序算法棚放，最短路徑等等也是算法與數(shù)據(jù)結(jié)構(gòu)的結(jié)晶體。

一馅闽、線性表綜述

本篇博客我們主要介紹的是邏輯結(jié)構(gòu)中的線性表飘蚯，也就是線性結(jié)構(gòu)馍迄。線性結(jié)構(gòu)的特點就好比一串珠子，其特點是第一個節(jié)點只有一個后繼局骤，沒有前驅(qū)攀圈，最后一個節(jié)點是只有一個前驅(qū)，沒有后繼峦甩。而其余的節(jié)點只有一個前驅(qū)和一個后繼赘来。說罷了線性表就是一串。下方這個圖就是線性表的示例圖凯傲。中間藍(lán)色的節(jié)點前方的是就是改點對應(yīng)的前驅(qū)犬辰，后邊就是改點對應(yīng)的后繼。從下方可以明確看出head沒有前驅(qū)只有后繼冰单，而tail只有前驅(qū)沒有后繼忧风。

上面這個是線性表的邏輯結(jié)構(gòu)，接下來我們來聊一下線性表的物理結(jié)構(gòu)球凰，也就是存儲結(jié)構(gòu)。線性表的物理結(jié)構(gòu)可分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)腿宰。順序存儲結(jié)構(gòu)之所以稱之為順序存儲結(jié)構(gòu)因為每個線性表中節(jié)點的內(nèi)存地址是連續(xù)的呕诉，而鏈?zhǔn)酱鎯Y(jié)構(gòu)中線性表的節(jié)點的內(nèi)存地址可以是不連續(xù)的。這也就是在C語言實現(xiàn)順序存儲線性表時先Malloc一塊連續(xù)的區(qū)域吃度，然后用來順序的存儲線性表甩挫。而鏈表中就可以不是連續(xù)的了，前驅(qū)與后繼間的關(guān)系由指針連接椿每。

下方這個指示圖中伊者，上面這個就是鏈?zhǔn)酱鎯Γ路竭@個就是順序存儲间护∫嗌可見鏈?zhǔn)酱鎯κ怯兄羔樣虻模簿褪乔膀?qū)和后繼的關(guān)系有指針來鏈接汁尺。下方這個鏈?zhǔn)酱鎯褪菃蜗蜴湵矸ň驗橹挥星膀?qū)到后繼的指針，而沒有后繼到前驅(qū)的指針痴突。關(guān)于雙向鏈表下方會具體給出詳細(xì)的說明搂蜓。而下面第二個圖就是順序存儲，前驅(qū)與后繼的關(guān)系是由緊挨的內(nèi)存地址所關(guān)聯(lián)辽装。

上面這兩種存儲方式我們可以換另一種更為形象的方式來進(jìn)行說明帮碰，如下所示。順序存儲的內(nèi)存區(qū)塊的內(nèi)存地址是緊挨的拾积，線性關(guān)系有相鄰的內(nèi)存地址所保存殉挽。當(dāng)然下方我們是模擬的內(nèi)存地址丰涉，就使用了0x1, 0x2等等來模擬。而鏈?zhǔn)酱鎯Φ木€性表此再，在物理存儲結(jié)構(gòu)中是不相鄰的昔搂，僅僅靠內(nèi)存地址無法去維持這種線性關(guān)系。所以就需要一個指針域來指向后繼或者前驅(qū)節(jié)點的內(nèi)存地址输拇，從而將節(jié)點之間進(jìn)行關(guān)聯(lián)摘符。在單向鏈?zhǔn)酱鎯χ校粋€節(jié)點不僅僅需要存儲數(shù)據(jù)策吠，而且還要存儲該節(jié)點下一個節(jié)點的內(nèi)存地址逛裤，以便保持這種線性關(guān)系。具體請看下圖猴抹。

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

二、線性表的順序存儲

關(guān)于線性表的順序存儲前普，我們就使用NSMutableArray來實現(xiàn)肚邢，也就是使用OC中的可變數(shù)組類型來實現(xiàn)。我們就假設(shè)其存儲的內(nèi)存地址是連續(xù)的拭卿，當(dāng)然數(shù)組中存儲對象時要復(fù)雜得多骡湖，我們暫且假設(shè)其中的地址是連續(xù)的。下方的list就是我們的順序線性表峻厚，count存儲的是已經(jīng)存入到線性表中的元素個數(shù)响蕴，而capacity則是記錄線性表整個容量的大小。當(dāng)然上述三個屬性都是private的惠桃，而下方的計算屬性length是internal類型的换途，供外界訪問，返回線性表元素的個數(shù)刽射。

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

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

有時候我們會給據(jù)特定的算法往線性表中指定的位置插入數(shù)據(jù)懈息，比如我們常見的插入排序算法，如果你的數(shù)據(jù)是順序存儲的話摹恰，那么就需要將數(shù)據(jù)插入到順序表中辫继。接下來我們就將數(shù)據(jù)插入到指定的位置怒见。

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

順序表的插入還是比較簡單的，也是非常好理解的瘦穆，那么用代碼實現(xiàn)起來也是用不了幾行代碼的纪隙。下方截圖就是是順序線性表的元素插入的具體實現(xiàn)的代碼。首先檢查index的合法性扛或，檢查index是否在合理范圍內(nèi)绵咱，然后將index后的元素依次往后移動，然后將元素插入即可熙兔。

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

上面介紹完元素的插入后悲伶，接下來要聊一下元素的移除。也就是移除指定索引中的元素住涉。該過程恰好與上述插入的過程相反麸锉，上述在插入之前是相應(yīng)的元素往后移，騰出index位置秆吵。而移除特定索引的元素時，是相應(yīng)的元素左移五慈，覆蓋掉要刪除的元素纳寂，然后將最后一個元素進(jìn)行移除掉。下方的原理圖對此過程進(jìn)行了說明泻拦。

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

三展辞、線性表的單鏈存儲

介紹完線性表的順序存儲，接下來我們來介紹線性表的鏈?zhǔn)酱鎯ν蛭．?dāng)然罗珍，本部分是對單向鏈表的介紹洽腺，下部分將會對雙向鏈表的介紹。下方截圖就是我們單向鏈表相關(guān)示例的運行結(jié)果覆旱，首先我們先正向的創(chuàng)建鏈表蘸朋，也就是后來的元素插入到鏈表的后方。然后在給出逆向創(chuàng)建鏈表扣唱，與正向創(chuàng)建鏈表相反藕坯，后來的元素?fù)饺氲筋^結(jié)點的后方。創(chuàng)建鏈表完畢后画舌，我們會給出鏈表元素的插入和移除的解決方案堕担。

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

在鏈表創(chuàng)建之前，我們得先創(chuàng)建節(jié)點的類曲聂，因為鏈表是多個節(jié)點的連接霹购。下方這個OneDirectionLinkListNote類就是單向鏈表的節(jié)點類。其中的data屬性存儲的是該節(jié)點所存儲的數(shù)據(jù)朋腋，而變量next就是指向下一個節(jié)點的指針齐疙，鏈表中節(jié)點間的關(guān)系由next指針?biāo)P(guān)聯(lián)。init和deinit就是該類的構(gòu)造和析構(gòu)函數(shù)了旭咽，就不做過多贅述了贞奋。

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

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

下方協(xié)議中只給出了方法的定義癌蚁，未給出具體實現(xiàn)幻梯。所有鏈表都要遵循該協(xié)議，ListProtocalType中定義了鏈表結(jié)構(gòu)所必須的方法努释〉馍遥可以說下方這個協(xié)議就是鏈表的大綱。

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

下方就是我們單向鏈表類的屬性和構(gòu)造函數(shù)伐蒂。headNote就是我們鏈表的頭結(jié)點痘系，而tailNote是我們鏈表的尾結(jié)點。length就是我們鏈表的長度饿自，也就是我們鏈表中元素的個數(shù)汰翠。一個空鏈表中tailNote = headNote龄坪。

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

上面這個示意圖是往鏈表的后方添加元素呈宇，接下來是往鏈表的頭部插入元素好爬。該過程也是由關(guān)鍵的兩步組成，第一步就是newNode->next = head->next甥啄，第二步是head->next = newNode存炮。經(jīng)過這兩步我們就可以把元素插入到頭結(jié)點的后方了。

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

4.單向鏈表元素的移除

上面我們聊完元素的插入，解下來我們要聊一下元素的移除巍佑。要想移除單向鏈表中的一個元素茴迁，首先我們得找到被移除結(jié)點的前驅(qū)的位置，比如是pre句狼。當(dāng)前移除的元素是remove笋熬，讓我我們讓pre->next = remove->next, 然后再執(zhí)行remove->next = nil热某。經(jīng)過上面這些步驟腻菇，remove這個結(jié)點就與鏈表脫離關(guān)系了。示意圖如下所示昔馋。

根據(jù)上述的示意圖筹吐，我們就可以給出具體的代碼實現(xiàn)了。單向鏈表的核心操作就介紹完了秘遏，其他更多細(xì)節(jié)請參考在github上分享的源代碼丘薛，因為篇幅有限，關(guān)于單向鏈表的更多細(xì)節(jié)就不做過多贅述了邦危。

四洋侨、雙向鏈表

如果你對單向鏈表已經(jīng)理解的話舍扰，那么理解雙向鏈表來說并非難事。雙向鏈表與單向鏈表相比多了一個指向前驅(qū)的節(jié)點希坚。我們暫且稱為將指向前驅(qū)的節(jié)點命名我pre指針边苹。下方這個示意圖就是雙向鏈表的示意圖，與單向鏈表相比裁僧，多了一個指向前驅(qū)的指針域个束。如下所示。接下來將會給出雙向鏈表的插入和移除聊疲。

1.雙向鏈表元素的插入

雙向鏈表的插入要比單向鏈表的插入要復(fù)雜一些茬底，不過也是蠻好理解的。下方示意圖中就是往節(jié)點A后方插入一個節(jié)點D获洲。主要分為四個步驟阱表，第一步是將D節(jié)點的next指針指向A節(jié)點next指針指向的節(jié)點，也就是D->next = A->next昌妹。第二步是將D節(jié)點的pre指針指向A節(jié)點捶枢，也就是D->pre = A。第三步是將A的next指針指向D飞崖，也就是A->next = D烂叔。最后將D節(jié)點的下一個節(jié)點的pre指針指向D，也就是D->next->pre = D固歪。經(jīng)過這幾步蒜鸡，我們就可以將節(jié)點D插入到A與B的中間。當(dāng)然這個順序不是一定的牢裳，只要能保證鏈的正確關(guān)聯(lián)即可逢防。

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

2.雙向鏈表元素的刪除

雙向鏈表因為比單向鏈表多一個前驅(qū)指針域判帮，所以元素的刪除要麻煩一下局嘁，不過還是比較好理解的。下方這個截圖就是刪除B節(jié)點的示意圖晦墙。首先將B節(jié)點前驅(qū)節(jié)點的next指針域指向B節(jié)點的后繼悦昵，也就是B->pre->next = B->next。 然后將B節(jié)點的后繼節(jié)點的前驅(qū)指針指向B的前驅(qū)節(jié)點晌畅，對應(yīng)著B->next-pre = B->pre但指。最后將B的next和pre指針域置為nil。如下所示：

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

五剩岳、面向接口編程的優(yōu)點

在上述我們實現(xiàn)兩種鏈表時贪婉，我們先定義了一個鏈表協(xié)議ListProtocalType。無論是雙向鏈表還是單向鏈表都遵循這個協(xié)議卢肃，也就是說疲迂，該協(xié)議就是鏈表對外統(tǒng)一的接口，該協(xié)議就是操作鏈表的一個規(guī)范莫湘。下方的testLinkedList()就是我們鏈表的測試方法尤蒿，該函數(shù)的參數(shù)是遵循ListProtocalType協(xié)議的所有類的對象。也就是說只要遵循了ListProtocalType這個協(xié)議的類的對象幅垮，都可以作為該函數(shù)的參數(shù)腰池。至于具體操作，那么不同的類會給出不同的操作的忙芒。

在調(diào)用該函數(shù)時示弓，第一個傳入的是單向鏈表的類的對象，第二個是雙向鏈表的類的對象呵萨。雖然都是執(zhí)行同一個方法奏属，但是因為傳入的類的對象不同，所以執(zhí)行的結(jié)果顯然是不同的潮峦。這也就是利用了面向?qū)ο蟮亩鄳B(tài)性囱皿，在之前設(shè)計模式系列的博客中介紹過，下方這種與策略模式類似忱嘹。