[[421878]]

大家好，我是小風(fēng)哥。

鏈表是計(jì)算機(jī)科學(xué)中極其經(jīng)典的一種數(shù)據(jù)結(jié)構(gòu)，那么作為程序員我們?cè)撛鯓永斫怄湵砟?

貨車(chē) VS 火車(chē)

作為兩大運(yùn)輸工具，貨車(chē)以及火車(chē)想必大家都很熟悉，但你想沒(méi)想過(guò)這兩者的區(qū)別?

我們首先來(lái)看貨車(chē)。

對(duì)于貨車(chē)的話，如果有一堆貨物想用貨車(chē)來(lái)運(yùn)輸，那么你首先要考慮的是什么呢?

[[421879]]

答案顯而易見(jiàn)，載重。因?yàn)樨涇?chē)的載重是有限的，不可變的，你沒(méi)辦法把貨車(chē)拆了臨時(shí)裝上一截，如果貨物的重量是10噸，那么想用貨車(chē)運(yùn)輸則必須找一個(gè)載重不小于10噸的車(chē)，否則你沒(méi)有辦法拉走。

假設(shè)你現(xiàn)在選好一輛貨車(chē)，但不巧的是，當(dāng)你把東西都裝到車(chē)上以后發(fā)現(xiàn)客戶又額外追加一些訂單，因此還有一些貨物需要一并運(yùn)走，但由于貨車(chē)的載重有限，這時(shí)你該怎么辦呢?

沒(méi)有辦法，你不得不重新去找一輛載重更多的貨車(chē)，我們假設(shè)載重更大的車(chē)為B車(chē)，原來(lái)的車(chē)為A車(chē)，這是你需要把A車(chē)的貨物搬運(yùn)到B車(chē)，然后再把剩下的裝到B車(chē)上拉走。

接著我們?cè)賮?lái)看火車(chē)。

[[421880]]

對(duì)于火車(chē)的話就很有趣了，與貨車(chē)不同的是，對(duì)于火車(chē)來(lái)說(shuō)你不需要考慮載重的問(wèn)題，你可以認(rèn)為火車(chē)的載重是無(wú)限的，如果有更多貨物要運(yùn)輸該怎么辦呢?很簡(jiǎn)單，找更多車(chē)廂過(guò)來(lái)掛接到火車(chē)上就可以了，你根本就不需要像貨車(chē)那樣很麻煩的需要把A車(chē)的貨物搬運(yùn)到B車(chē)。

這就是火車(chē)的妙用。

現(xiàn)在你應(yīng)該看出來(lái)了嗎，貨車(chē)就好比數(shù)組，火車(chē)就好比鏈表。

數(shù)據(jù)結(jié)構(gòu)與語(yǔ)言無(wú)關(guān)

注意這里說(shuō)的數(shù)組以及鏈表特指用來(lái)組織數(shù)據(jù)的結(jié)構(gòu)，與任何語(yǔ)言無(wú)關(guān)，你可以在C/C++中使用數(shù)組或鏈表，當(dāng)然也可以在Java、Python等語(yǔ)言中使用數(shù)組或者鏈表。

記住，數(shù)據(jù)結(jié)構(gòu)是一種組織數(shù)據(jù)的方式，和語(yǔ)言無(wú)關(guān)。

無(wú)論你用什么語(yǔ)言來(lái)使用數(shù)組或者鏈表，其在底層的表示都是一樣的，不同點(diǎn)僅僅在于外觀，也就是你看到的那層抽象。

[[421881]]

在C語(yǔ)言中可能需要你自己用指針來(lái)等來(lái)實(shí)現(xiàn)鏈表、C++是使用相關(guān)容器、在Java、Python等語(yǔ)言中可能只需要使用語(yǔ)言自帶的鏈表就好了，這就是所謂的外觀，而之所以外觀不同在于抽象層次有高低之分，C/C++抽象層次更低一些，因此你能看到更多細(xì)節(jié)，而Java、Python等抽象層次更高一點(diǎn)因此你只能知道一個(gè)叫做鏈表的東西，拿過(guò)來(lái)用就好。

但抽象并不是魔法，總要有人來(lái)實(shí)現(xiàn)細(xì)節(jié)，要想真正理解鏈表，你需要知道其底層的實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，既然是組織數(shù)據(jù)的結(jié)構(gòu)，那么數(shù)據(jù)存放在哪里呢?

很顯然，內(nèi)存，數(shù)據(jù)結(jié)構(gòu)在這一層級(jí)就和語(yǔ)言無(wú)關(guān)了，因此你能更清楚的看到本質(zhì)。

接下來(lái)我們看看數(shù)組以及鏈表在內(nèi)存中是怎么表示的。

內(nèi)存，最重要的是內(nèi)存

首先我們來(lái)看數(shù)組，假設(shè)你要裝載的貨物是16個(gè)字節(jié)，那么如果你想用數(shù)組來(lái)裝載數(shù)據(jù)的話該怎么辦呢?

很顯然，你需要從內(nèi)存中申請(qǐng)16個(gè)字節(jié)，而且是連續(xù)的字節(jié)，就像卡車(chē)一樣，一上來(lái)容量就固定了。

這里一個(gè)小方格代表4字節(jié)。

這時(shí)如果你想在容量16個(gè)字節(jié)的數(shù)組中再裝入8字節(jié)數(shù)據(jù)該怎么辦?沒(méi)辦法，原來(lái)的數(shù)組就不再可用了，你需要再次從內(nèi)存中申請(qǐng)24字節(jié)，并且把原來(lái)的數(shù)據(jù)copy過(guò)來(lái)，此后再把剩余的8字節(jié)裝入數(shù)組。

就像這樣：

接下來(lái)，我們看鏈表，依然假設(shè)需要裝載的貨物是16個(gè)字節(jié)。

鏈表與數(shù)組截然不同的地方在于就像火車(chē)一樣，你無(wú)須一次性申請(qǐng)40字節(jié)的空間，而是可以一節(jié)車(chē)廂一節(jié)車(chē)廂的申請(qǐng)，而且更棒的是這些車(chē)廂也不需要和數(shù)組一樣是連續(xù)的，就像這樣：

你可以看到，這些車(chē)廂可以很松散的分布在內(nèi)存的各個(gè)角落中，當(dāng)你裝滿16字節(jié)想要再裝8字節(jié)怎么辦?很簡(jiǎn)單，只需要再?gòu)膬?nèi)存中找2個(gè)車(chē)廂掛接上去就好了，就像這樣：

原來(lái)的16字節(jié)根本就無(wú)需改動(dòng)。

從這里也能看出來(lái)，數(shù)組是靜態(tài)的，創(chuàng)建好后就不能改動(dòng);而鏈表是動(dòng)態(tài)的，你可以根據(jù)需求來(lái)動(dòng)態(tài)的增加或者減少鏈表的長(zhǎng)度。

接下來(lái)有同學(xué)就會(huì)問(wèn)了，既然鏈表的車(chē)廂可以離散的分布在內(nèi)存中的各個(gè)角落，那么你怎么知道一節(jié)車(chē)廂到底屬于哪個(gè)火車(chē)(鏈表)呢?你怎么能知道當(dāng)前車(chē)廂的后一截車(chē)廂是哪一個(gè)呢?

鏈表是如何形成的?

要想明白這個(gè)問(wèn)題，火車(chē)依然是為一個(gè)絕佳的示例。

想一想火車(chē)是如何形成的，火車(chē)是由火車(chē)頭、火車(chē)尾以及一節(jié)節(jié)車(chē)廂組成，火車(chē)頭和火車(chē)尾以及各節(jié)車(chē)廂沒(méi)有本質(zhì)區(qū)別，因此我們重點(diǎn)關(guān)注在一節(jié)車(chē)廂上。

一節(jié)車(chē)廂有哪些關(guān)鍵因素呢：

一節(jié)車(chē)廂只知道自己的負(fù)重以及它的下一節(jié)車(chē)廂是誰(shuí)

這就足夠了。

一節(jié)車(chē)廂不需要關(guān)心一輛火車(chē)是如何形成的，它只需要關(guān)心自己裝載了什么，以及它的下一節(jié)車(chē)廂是誰(shuí)，這就是為什么鏈表的節(jié)點(diǎn)可以離散的散落在內(nèi)存的各個(gè)角落的原因，因?yàn)楸M管車(chē)廂是不連續(xù)的，但每一節(jié)車(chē)廂都知道自己的下一節(jié)車(chē)廂是誰(shuí)：

現(xiàn)在你應(yīng)該看到了吧，只要你能找到一個(gè)頭節(jié)點(diǎn)，你可以拎出整條鏈表。這就是鏈表的奇妙之處。

這也告訴我們?yōu)槭裁丛黾踊蛘邉h除一節(jié)車(chē)廂這么簡(jiǎn)單：你只需要改動(dòng)節(jié)點(diǎn)本身以及該節(jié)點(diǎn)的前后鄰居就可以了：

而數(shù)組這種一次性的數(shù)據(jù)結(jié)構(gòu)(創(chuàng)建好后就無(wú)法修改)則對(duì)改動(dòng)很不友好，鏈表則無(wú)此問(wèn)題。

但鏈表的這種特性也有自己的缺點(diǎn)，這世界上沒(méi)有完美的數(shù)據(jù)結(jié)構(gòu)。

對(duì)于數(shù)組來(lái)說(shuō)，只要知道數(shù)組下標(biāo)，我們可以一步從數(shù)組中找出該元素，但鏈表則不可以，如果我問(wèn)你鏈表的第10個(gè)節(jié)點(diǎn)在哪里?除非從頭到尾數(shù)一遍否則在不借助其它方法的情況下你是沒(méi)有辦法知道的。

理解了這些你覺(jué)得鏈表還難嗎?

Show me your code

接下來(lái)我們定義一個(gè)節(jié)點(diǎn)，叫做node：

struct node { 
    ?   
}; 

那么node里的內(nèi)容應(yīng)該是什么呢?

很顯然，有這節(jié)車(chē)廂裝載的貨物有沒(méi)有，我們將其稱作loads，類型是什么呢，這個(gè)其實(shí)是無(wú)所謂的，簡(jiǎn)單起見(jiàn)，我們就用int來(lái)表示：

struct node { 
  ?   
  int loads; // 裝載的貨物 
}; 

最后還有一個(gè)關(guān)鍵點(diǎn)的地方，這節(jié)車(chē)廂怎么知道下一節(jié)車(chē)廂在哪里?顯然你得有個(gè)地址，也就是address，本質(zhì)上就是內(nèi)存地址，那么在C/C++可以看到內(nèi)存地址的語(yǔ)言中通用的內(nèi)存地址該怎么表示呢?

很簡(jiǎn)單：void*，因此這節(jié)車(chē)廂就是：

struct node { 
  void* address; // 下一節(jié)車(chē)廂是誰(shuí) 
  int loads;     // 裝載的貨物 
}; 

有的同學(xué)看到這里可能會(huì)問(wèn)了，這和書(shū)上教的不一樣呀?

如果你真的理解了鏈表的本質(zhì)就不會(huì)有這種疑問(wèn)了，實(shí)際上你可以把任意內(nèi)存塊都用鏈表串在一起，管它這些內(nèi)存塊中裝的是什么數(shù)據(jù)!

只不過(guò)我們一般都是把同類型內(nèi)存塊用鏈表鏈接起來(lái)：

struct node { 
  struct node* address; // 下一節(jié)車(chē)廂是誰(shuí) 
  int loads;           // 裝載的貨物 
}; 

哦!對(duì)了，為了讓大家更好的理解鏈表，address這個(gè)名字換成next更形象一些，下一節(jié)車(chē)廂嘛，loads換成value更加教科書(shū)一些：

struct node { 
  struct node* next; // 下一節(jié)車(chē)廂是誰(shuí) 
  int value;         // 裝載的貨物 
}; 

 這是不是你在書(shū)里看到?但是你應(yīng)該明白，鏈表可以不必這樣寫(xiě)。

本文轉(zhuǎn)載自微信公眾號(hào)「碼農(nóng)的荒島求生」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼農(nóng)的荒島求生公眾號(hào)。