[[421878]]

大家好，我是小風哥。

鏈表是計算機科學中極其經典的一種數據結構，那么作為程序員我們該怎樣理解鏈表呢?

貨車 VS 火車

作為兩大運輸工具，貨車以及火車想必大家都很熟悉，但你想沒想過這兩者的區別?

我們首先來看貨車。

對于貨車的話，如果有一堆貨物想用貨車來運輸，那么你首先要考慮的是什么呢?

[[421879]]

答案顯而易見，載重。因為貨車的載重是有限的，不可變的，你沒辦法把貨車拆了臨時裝上一截，如果貨物的重量是10噸，那么想用貨車運輸則必須找一個載重不小于10噸的車，否則你沒有辦法拉走。

假設你現在選好一輛貨車，但不巧的是，當你把東西都裝到車上以后發現客戶又額外追加一些訂單，因此還有一些貨物需要一并運走，但由于貨車的載重有限，這時你該怎么辦呢?

沒有辦法，你不得不重新去找一輛載重更多的貨車，我們假設載重更大的車為B車，原來的車為A車，這是你需要把A車的貨物搬運到B車，然后再把剩下的裝到B車上拉走。

接著我們再來看火車。

[[421880]]

對于火車的話就很有趣了，與貨車不同的是，對于火車來說你不需要考慮載重的問題，你可以認為火車的載重是無限的，如果有更多貨物要運輸該怎么辦呢?很簡單，找更多車廂過來掛接到火車上就可以了，你根本就不需要像貨車那樣很麻煩的需要把A車的貨物搬運到B車。

這就是火車的妙用。

現在你應該看出來了嗎，貨車就好比數組，火車就好比鏈表。

數據結構與語言無關

注意這里說的數組以及鏈表特指用來組織數據的結構，與任何語言無關，你可以在C/C++中使用數組或鏈表，當然也可以在Java、Python等語言中使用數組或者鏈表。

記住，數據結構是一種組織數據的方式，和語言無關。

無論你用什么語言來使用數組或者鏈表，其在底層的表示都是一樣的，不同點僅僅在于外觀，也就是你看到的那層抽象。

[[421881]]

在C語言中可能需要你自己用指針來等來實現鏈表、C++是使用相關容器、在Java、Python等語言中可能只需要使用語言自帶的鏈表就好了，這就是所謂的外觀，而之所以外觀不同在于抽象層次有高低之分，C/C++抽象層次更低一些，因此你能看到更多細節，而Java、Python等抽象層次更高一點因此你只能知道一個叫做鏈表的東西，拿過來用就好。

但抽象并不是魔法，總要有人來實現細節，要想真正理解鏈表，你需要知道其底層的實現，數據結構，數據結構，既然是組織數據的結構，那么數據存放在哪里呢?

很顯然，內存，數據結構在這一層級就和語言無關了，因此你能更清楚的看到本質。

接下來我們看看數組以及鏈表在內存中是怎么表示的。

內存，最重要的是內存

首先我們來看數組，假設你要裝載的貨物是16個字節，那么如果你想用數組來裝載數據的話該怎么辦呢?

很顯然，你需要從內存中申請16個字節，而且是連續的字節，就像卡車一樣，一上來容量就固定了。

這里一個小方格代表4字節。

這時如果你想在容量16個字節的數組中再裝入8字節數據該怎么辦?沒辦法，原來的數組就不再可用了，你需要再次從內存中申請24字節，并且把原來的數據copy過來，此后再把剩余的8字節裝入數組。

就像這樣：

接下來，我們看鏈表，依然假設需要裝載的貨物是16個字節。

鏈表與數組截然不同的地方在于就像火車一樣，你無須一次性申請40字節的空間，而是可以一節車廂一節車廂的申請，而且更棒的是這些車廂也不需要和數組一樣是連續的，就像這樣：

你可以看到，這些車廂可以很松散的分布在內存的各個角落中，當你裝滿16字節想要再裝8字節怎么辦?很簡單，只需要再從內存中找2個車廂掛接上去就好了，就像這樣：

原來的16字節根本就無需改動。

從這里也能看出來，數組是靜態的，創建好后就不能改動;而鏈表是動態的，你可以根據需求來動態的增加或者減少鏈表的長度。

接下來有同學就會問了，既然鏈表的車廂可以離散的分布在內存中的各個角落，那么你怎么知道一節車廂到底屬于哪個火車(鏈表)呢?你怎么能知道當前車廂的后一截車廂是哪一個呢?

鏈表是如何形成的?

要想明白這個問題，火車依然是為一個絕佳的示例。

想一想火車是如何形成的，火車是由火車頭、火車尾以及一節節車廂組成，火車頭和火車尾以及各節車廂沒有本質區別，因此我們重點關注在一節車廂上。

一節車廂有哪些關鍵因素呢：

一節車廂只知道自己的負重以及它的下一節車廂是誰

這就足夠了。

一節車廂不需要關心一輛火車是如何形成的，它只需要關心自己裝載了什么，以及它的下一節車廂是誰，這就是為什么鏈表的節點可以離散的散落在內存的各個角落的原因，因為盡管車廂是不連續的，但每一節車廂都知道自己的下一節車廂是誰：

現在你應該看到了吧，只要你能找到一個頭節點，你可以拎出整條鏈表。這就是鏈表的奇妙之處。

這也告訴我們為什么增加或者刪除一節車廂這么簡單：你只需要改動節點本身以及該節點的前后鄰居就可以了：

而數組這種一次性的數據結構(創建好后就無法修改)則對改動很不友好，鏈表則無此問題。

但鏈表的這種特性也有自己的缺點，這世界上沒有完美的數據結構。

對于數組來說，只要知道數組下標，我們可以一步從數組中找出該元素，但鏈表則不可以，如果我問你鏈表的第10個節點在哪里?除非從頭到尾數一遍否則在不借助其它方法的情況下你是沒有辦法知道的。

理解了這些你覺得鏈表還難嗎?

Show me your code

接下來我們定義一個節點，叫做node：

struct node { 
    ?   
}; 

那么node里的內容應該是什么呢?

很顯然，有這節車廂裝載的貨物有沒有，我們將其稱作loads，類型是什么呢，這個其實是無所謂的，簡單起見，我們就用int來表示：

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

最后還有一個關鍵點的地方，這節車廂怎么知道下一節車廂在哪里?顯然你得有個地址，也就是address，本質上就是內存地址，那么在C/C++可以看到內存地址的語言中通用的內存地址該怎么表示呢?

很簡單：void*，因此這節車廂就是：

struct node { 
  void* address; // 下一節車廂是誰 
  int loads;     // 裝載的貨物 
}; 

有的同學看到這里可能會問了，這和書上教的不一樣呀?

如果你真的理解了鏈表的本質就不會有這種疑問了，實際上你可以把任意內存塊都用鏈表串在一起，管它這些內存塊中裝的是什么數據!

只不過我們一般都是把同類型內存塊用鏈表鏈接起來：

struct node { 
  struct node* address; // 下一節車廂是誰 
  int loads;           // 裝載的貨物 
}; 

哦!對了，為了讓大家更好的理解鏈表，address這個名字換成next更形象一些，下一節車廂嘛，loads換成value更加教科書一些：

struct node { 
  struct node* next; // 下一節車廂是誰 
  int value;         // 裝載的貨物 
}; 

 這是不是你在書里看到?但是你應該明白，鏈表可以不必這樣寫。

本文轉載自微信公眾號「碼農的荒島求生」，可以通過以下二維碼關注。轉載本文請聯系碼農的荒島求生公眾號。