大家好，我是小风哥。链表是计算机科学中非常经典的数据结构，那么我们作为程序员应该如何理解链表呢？卡车和火车作为两大交通工具想必大家都不陌生，但是大家有没有想过这两者的区别呢？我们先来看看面包车。对于卡车来说，如果要用卡车运输一堆货物，首先应该考虑什么？答案很明显，负载。由于货车载重有限且不可改变，不能拆车临时装一段。如果货物的重量是10吨，那么如果要用卡车运输，就必须要找载重不低于10吨的卡车。不然拉不开。假设你现在选择了一辆卡车，但是不幸的是，当你把所有的东西都装上卡车的时候，你发现客户增加了一些额外的订单，所以还有一些货物需要一起运送，但是由于装载量有限卡车，这个时候你该怎么办？没办法，得找载重高一点的卡车。假设载重较重的货车是B，原来的货车是A，你需要把A车里的货物运到B车上，然后把剩下的装上B车拉走。然后我们看火车。这对火车来说非常有趣。与货车不同，您无需考虑火车的负载。你可以认为火车的负载是无限的。如果要运输的货物更多怎么办？很简单，多找几节车厢挂在火车上就可以了。你不需要像卡车那样把货物从A车运到B车那么麻烦。这就是火车的魅力。现在你应该看到卡车就像一个数组，而火车就像一个链表。数据结构与语言无关。注意这里所说的数组和链表指的是用来组织数据的结构。它与任何语言无关。在C/C++中可以使用数组或者链表，当然在Java、Python等语言中也可以使用数组。或者链表。请记住，数据结构是一种组织数据的方式，而不是语言。不管你用什么语言来使用数组或链表，底层的表示都是一样的。区别仅在于外观，即您看到的抽象层。在C语言中，你可能需要使用指针来自己实现链表。C++使用相关的容器。在Java、Python等语言中，可能只需要使用语言自带的链表即可。这就是所谓的外表。所以外观上的区别在于抽象的层次。C/C++的抽象层次较低，可以看到更多的细节，而Java、Python等抽象层次较高，只能知道一个叫链表的东西。拿走并使用它。但抽象不是魔法。必须有人实施细节。真正理解链表，需要知道它的底层实现，数据结构，数据结构。既然是组织数据的结构，那么数据存放在哪里呢？显然，Memory和数据结构在这个层次上和语言没有任何关系，所以你可以更清楚地看到本质。接下来我们看看数组和链表在内存中是如何表示的。内存，最重要的是内存首先我们来看数组，假设你要加载的商品是16个字节，那么如果要用数组加载数据怎么办呢？显然，你需要从内存字节中申请16个字节，而且是连续的字节，就像卡车一样，一上来容量就固定了。这里一个小方块代表4个字节。这时候如果想把8个字节的数据加载到一个容量为16字节的数组中怎么办呢？没办法，原来的数组已经没有了，需要重新从内存中申请24个字节，把原来的数据复制过来，然后把剩下的8个字节加载到数组中。是这样的：接下来我们看链表，仍然假设需要装载的货物是16字节。链表和数组的区别在于，就像火车一样，不需要一次申请40个字节的空间，而是一次可以申请一节车厢，更棒的是这些车厢不需要和数组一样连续，像这样：可以看到这些隔间可以松散地分布在内存的各个角落。当你填满16个字节，想重新加载8个字节时，你应该怎么做？很简单，只要从内存中找到2个车厢，把它们挂起来就行了，就这样：原来的16个字节，根本不用改。从这里也可以看出，数组是静态的，创建后不能更改；而链表是动态的，你可以根据需要动态增加或减少链表的长度。接下来，有同学会问，既然链表的车可以离散地分布在内存的各个角落，那么怎么知道一辆车是属于哪一列火车（链表）呢？你怎么知道当前汽车的最后一部分？是哪辆车？链表是如何形成的？要理解这个问题，火车仍然是一个很好的例子。想一想火车是如何形成的。火车由机车、火车尾部和一段车厢组成。机车、火车尾部和每一节车厢没有本质区别，所以我们重点说一节车厢。一辆车的关键因素是什么：一辆车只知道自己的负载和下一辆车是谁就够了。一辆汽车不需要关心一列火车是怎么组成的，它只需要关心它装载的是什么，它的下一辆车是谁，这就是为什么链表的节点可以离散地分散在内存的各个角落，因为虽然车是不连续的，但是每辆车都知道自己的下一辆车是谁：现在应该看到了，只要能找到头节点，就可以把整个链表pick起来。这就是链表的魔力。这也告诉我们为什么添加或删除汽车如此简单：只需要??改变节点本身和节点前后的邻居；并且数组的一次性数据结构（创建后不可修改）对变化没有影响。很不友好，链表没有这个问题。但是链表的这个特性也有其自身的缺点。这个世界上没有完美的数据结构。对于数组，只要知道数组的下标，就可以一步从数组中找出元素，而链表则不行。如果我问你链表的第10个节点在哪里？除非你从头到尾数一遍，否则你不用帮助就可以使用其他方法，你无从知晓。了解了这些，你觉得链表还难吗？给我看你的代码接下来，我们定义一个名为node的节点：structnode{?};那么节点中的内容应该是什么？很显然，这节车厢里装的是货物。不，我们称之为负载。它是什么类型并不重要。为了简单起见，我们用int来表示：structnode{?intloads;//加载的商品};最后还有一个关键点，这辆车怎么知道下一辆车在哪里呢？很明显，你要有一个地址，也就是ad??dress，本质上就是一个内存地址，那么一般的内存地址怎么用C/C++中可以看到内存地址的语言来表达就很简单了：void*，所以这个carriageis:structnode{void*address;//下一车厢intloads;//装载的货物};有同学看到这里可能会问，这和书上讲的一样吗？如果你真正理解了链表的本质，你就不会有这样的疑惑。其实你可以把任意一个内存块用一个链表串起来，不管这些内存块里面装的是什么数据！只是我们通常把相同类型的内存块用一个链表链接起来：哦！为了更好的理解链表，把address的名字改成next更形象。对于下一辆车，将loads改成value比较教科书：structnode{structnode*next;//下一辆车是谁intvalue;//loadedGoods};你在书上看到这个了吗？但是你应该明白，链表并不需要这样写。本文转载自微信公众号《码农的荒岛求生》，可通过以下二维码关注。转载本文请联系码农荒岛求生公众号。
