36.彻底理解链表

大家好，我是小风哥。

链表是计算机科学中极其经典的一种数据结构，那么作为程序员我们该怎样理解链表呢？

货车 VS 火车

作为两大运输工具，货车以及火车想必大家都很熟悉，但你想没想过这两者的区别？

我们首先来看货车。

对于货车的话，如果有一堆货物想用货车来运输，那么你首先要考虑的是什么呢？

36.彻底理解链表 - 图1

答案显而易见，载重。因为货车的载重是有限的，不可变的，你没办法把货车拆了临时装上一截，如果货物的重量是10吨，那么想用货车运输则必须找一个载重不小于10吨的，否则你没有办法拉走。

假设你现在选好一辆货车，但不巧的是，当你把东西都装到车上以后发现客户又额外追加一些订单，因此还有一些货物需要一并运走，但由于货车的载重有限，这是你该怎么办呢？

没有办法，你不得不重新去找一辆载重更多的货车，我们假设载重更大的车位B车，原来的车为A车，这是你需要把A车的货物搬运到B车，然后再把剩下的装到B车上拉走。

接着我们再来看火车。

36.彻底理解链表 - 图2

对于火车的话就很有趣了，与货车不同的是，对于火车来说你不需要考虑载重的问题，你可以认为火车的载重是无限的，如果有更多货物要运输该怎么办呢？很简单，找更多车厢过来挂接到火车上就可以了，你根本就不需要像货车那样很麻烦的需要把A车的货物搬运到B车。

这就是火车的妙用。

现在你应该看出来了吗，货车就好比数组，火车就好比链表。

数据结构与语言无关

注意这里说的数组以及链表特指用来组织数据的结构，与任何语言无关，你可以在C/C++中使用数组或链表，当然也可以在Java、Python等语言中使用数组或者链表。

记住，数据结构是一种组织数据的方式，和语言无关。

无论你用什么语言来使用数组或者链表，其在底层的表示都是一样的，不同点仅仅在于外观，所谓外观就是你看到的样子。

36.彻底理解链表 - 图3

在C/C++中可能需要你自己用指针来等来实现链表、在Java、Python等语言中可能只需要使用自带的链表就好了，这就是所谓的外观，而之所以外观不同在于抽象层次有高低之分，C/C++抽象层次更低一些，因此你能看到更多细节，而Java、Python等抽象层次更高一点因此你只能知道一个叫做链表的东西，拿过来用就好。

但抽象并不是魔法，总要有人来实现细节，要想真正理解链表，你需要知道其底层的实现，数据结构，数据结构，既然是组织数据的结构，那么数据存放在哪里呢？

很显然，内存，数据结构在这一层级就和语言无关了，因此你能更清楚的看到本质。

接下来我们看看数组以及链表在内存中是怎么表示的。

内存，最重要的是内存

首先我们来看数组，假设你要装载的货物是16个字节，那么如果你想用数组来装载数据的话该怎么办呢？

很显然，你需要从内存中申请16个字节，而且是连续的字节，就像卡车一样，一上来容量就固定了。

36.彻底理解链表 - 图4

这里一个小方格代表一个4字节。

这时如果你想在容量16个字节的数组中再装入8字节数据该怎么办？没办法，原来的数组就不再可用了，你需要再次从内存中申请24字节，并且把原来的数据copy过来，此后再把剩余的8字节装入数 组。

就像这样：

36.彻底理解链表 - 图5

图：带copy以及装入额外20字节。

接下来，我们看链表，依然假设需要装载的货物是40个字节。

链表与数组截然不同的地方在于就像火车一样，你无须一次性申请40字节的空间，而是一节车厢一节车厢的申请，而且更棒的是这些车厢也不需要和数组一样是连续的，就像这样：

36.彻底理解链表 - 图6

你可以看到，这些车厢可以很松散的分布在内存的各个角落中，当你装满16字节想要再装8字节怎么办？很简单，只需要再从内存中找2个车厢挂接上去就好了，就像这样：

36.彻底理解链表 - 图7

原来的16字节根本就无需改动。

从这里也能看出来，数组是静态的，创建好后就不能改动；而链表是动态的，你可以根据需求来动态的增加或者减少链表的长度。

接下来有同学就会问了，既然链表的车厢可以离散的分布在内存中的各个角落，那么你怎么知道一节车厢到底属于哪个火车(链表)呢？你怎么能知道当前车厢的后一截车厢是哪一个呢？

链表是如何形成的？

要想明白这个问题，火车依然是为一个绝佳的示例。

想一想火车是如何形成的，火车是由火车头、火车尾以及一节节车厢组成，火车头和火车尾以及各节车厢没有本质区别，因此我们重点关注在一节车厢上。

一节车厢有哪些关键因素呢：

  1. 一节车厢只知道自己的负重以及它的下一节车厢是谁

这就足够了。

一节车厢不需要关心一辆火车是如何形成的，它只需要关心自己装载了什么，以及它的下一节车厢是谁，这就是为什么链表的节点可以离散的散落在内存的各个角落，因为尽管车厢是不连续的，但每一节车厢都知道自己的下一节车厢是谁：

36.彻底理解链表 - 图8

现在你应该看到了吧，只要你能找到一个头节点，你可以拎出整条链表。这就是链表的奇妙之处。

这也告诉我们为什么增加或者删除一节车厢这么简单了：你只需要改动节点本身以及该节点的前后临 近就可以了：

36.彻底理解链表 - 图9

而数组这种一次性的数据结构(创建好后就无法修改)则对改动很不友好，链表则无此问题。

但链表的这种特性也有自己的缺点，这世界上没有完美的数据结构。

对于数组来说，只要知道数组下标，我们可以一步从数组中找出该元素，但链表则不可以，如果我问你链表的第10个节点在哪里？除非从头到尾数一遍否则在不借助其它方法的情况下你是没有办法知道的。

理解了这些你觉得链表还难吗？

Show me your code

接下来我们定义一个节点，叫做node：

  1. struct node {
  2.  ?  
  3. };

那么node里的内容应该是什么呢？

很显然，有这节车厢装载的货物有没有，我们将其称作loads，类型是什么呢，这个其实是无所谓的，简单起见，我们急用int来表示：

  1. struct node {
  2.  ?  
  3.  int loads; // 装载的货物
  4. };

最后还有一个关键点的地方，这节车厢怎么知道下一节车厢在哪里？显然你得有个地址，也就是address，本质上就是内存地址，那么在C/C++可以看到内存地址的语言中通用的内存地址该怎么表示呢？

很简单void*，因此这节车厢就是：

  1. struct node {
  2.  void* address; // 下一节车厢是谁
  3.  int loads; // 装载的货物
  4. };

有的同学看到这里可能会问了，这和书上教的不一样呀？

如果你真的理解了链表的本质就不会有这种疑问了，实际上你可以把任意内存块都用链表串在一起，管它这些内存块中装的是什么数据！

只不过我们一般都是把同类型内存块用链表链接起来：

  1. struct node {
  2.  struct node* address; // 下一节车厢是谁
  3.  int loads; // 装载的货物
  4. };

哦！对了，为了让大家更好的理解链表，address这个名字换成next更形象一些，下一节车厢嘛，loads换成value更加教科书一些：

  1. struct node {
  2.  struct node* next; // 下一节车厢是谁
  3.  int value; // 装载的货物
  4. };

这是不是你在书里看到？但是你应该明白，链表可以不必这样写。

总结

这是小风哥第一篇系统讲解数据结构与算法的系列文章，由于数据结构与算法内容较多，因此特意开了一个新的号叫做“小风算法”，哈哈，“小风算法”也是小风哥亲自操刀哈，欢迎大家多多关注。

以后“码农的荒岛求生”这个号主要关注计算机底层技术，“小风算法”这个号主要关注数据结构与算法，欢迎大家去关注。