链表
今天来了解下数据结构中的链表含义。
1 链表和数组的区别
数组是需要一块连续的内存空间来存储，对内存的要求比较高。
而链表却相反，它并不需要一块连续的内存空间。链表是通过指针将一组零散的内存块串联在一起。
相比数组，链表是一种稍微复杂一点的数据结构。当然，两者没有好坏之分，各有各的优缺点。
数组可以快速的查找某个元素，但是在插入和删除时就要移动大量元素。原因就在于相邻元素的存储位置也具有邻居关系。他们的编号是 0，1，2，3，4，...，n，它们在内存中的位置也是紧挨着的，中间没有空隙，所以就无法快速添加元素。而当删除后，当中就会留出空隙，自然需要弥补。
所以我们需要这样一种数据结构：
我们反正也是要让相邻元素间留有足够余地，那干脆所有的元素都不要考虑相邻位置了，哪有空位就到哪里，只是让每个元素知道它下一个元素的位置在哪里。我们可以在第一个元素时，就知道第二个元素的位置在哪；在第二个元素时，再找到第三个元素的位置。这样，所有的元素都可以遍历而找到。
因此，为了表示每个数据元素 n 和后继元素 n+1 之间的逻辑关系，对数据元素 n 来说，除了存储本身的信息之外，还需要存储一个指示其后继的信息。我们把存储元素的域称之为 数据域，把存储直接后继位置的域称之为 指针域。指针域中存储的信息称做 指针或链。这两部分信息组成数据元素 n 的存储映像，称为 结点。
而由 n 个结点链结成一个链表，称之为 链式存储结构。
2 单链表
最简单最常用的是 单链表，此链表的每个结点只包含一个指针域。
image
如上图，就是一个简单的单链表示意图。其中有两个结点是比较特殊的。他们分别是第一个结点和最后一个节点。我们习惯性地把第一个结点叫做头结点，把最后一个结点叫做尾结点。头结点是用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊地方它的指针不是指向下一个地方，而是指向一个空地址 NULL，表示这是链表上最后一个结点。
我们可以判断当前结点的 next 是否为空，就知道循环是否结束。
就像一家三口并排的手牵手去逛街，爸爸牵着妈妈，妈妈牵着孩子。此时的爸爸就可以当做头结点，而孩子就是尾结点。
与数组一样，链表也支持数据的增删改查。
对比插入和删除操作，为了保持内存数据的连续性，数据需要进行大量的数据搬移工作，所以时间复杂度为 O(n)。而在链表中插入和删除数据，并不需要担心此事，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。
image
对比查找操作，链表就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据下标等方法查找，链表需要根据指针依次遍历，直到找到对应的结点。
3 循环链表
屏幕前的你都还很年轻，不会觉得日月如梭。可上了点年纪的人，比如我---的父辈们，就会常常感叹，要是能回到从前该多好，向天再借 500 年可好。也有人说，所谓的成功男人就是 3 岁时不尿裤子，5 岁时能自己吃饭....80 岁能自己吃饭，90 岁能不尿裤子。人生是不是在循环呢。
image
对于单链表，由于每个结点只存储了向后的指针，到了尾结点就停止了向后链的操作。这样，当中的某一结点就无法找到它的前驱结点了，就如上图一样，不能回到从前了。
比如说，我们的市场销售同学家在北京，需要经常到上海出差。行程就是去两地之间的各个城市。从北京出发，乘坐高铁经过多个城市后，再乘坐灰机返回北京。
北京 --> 济南 --> 蚌埠 --> 南京 --> 苏州 --> 上海
有一次，他先到南京开会，接下来还要把以上的城市再走一遍。此时有人对他说，不行，你得从上海开始，因为北京是第一站。这时他会对这人说什么？神经病。他从南京开始，到苏州，上海，然后再回北京然后去济南的几个城市就可以了。显然这表示是你从当中某一个结点开始遍历整个链表，这是原来的单链表结构不能解决的问题。
事实上，把北京和上海连起来，行成一个环就解决了前面所面临的问题。这就是 循环链表。
将单链表中尾结点的指针由空指针指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表就简称为循环链表。
image
其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断当前结点的 next 是否为空，现在则是判断当前结点的 next 是否等于头结点。
就像一家三口围成一个圈做游戏，爸爸牵着妈妈，妈妈牵着孩子，孩子又牵着爸爸。
4 双向链表
今天我们销售又得出差了，平时都是从北京一路停留到上海的。可是这一次，他得先到上海开会，开完后，然后又得需要例行公事，走访各个城市，此时他该怎么办？
这个时候，那人又出主意了，你可以先飞回北京，然后再一路乘坐火车走遍这几个城市。
哎，人生中总会避免不了这样给你出馊主意的人存在。哪有这么麻烦，他一路再乘坐高铁回去不就完事了嘛。
就如单链表，总是从头到尾找结点，难道就不可以正反遍历吗？
所以这个时候双向链表就登场了。双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
image
从上图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但是可以支持双向遍历，这样也带来了双向链表操作的灵活性。
5 双向循环链表
既然单链表可以有循环链表，那么双向链表当然也可以是循环链表。你可以停下来想想双向循环链表长什么样子。
image
6 链表和数组的性能对比
image
数组和链表的对比，并不能局限于时间复杂度。而且，在实际开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。针对不同的类型项目来权衡。当然，在大前端，还是数组用的最多。
重点
各位大佬，初碰水面，不喜勿喷。如有错误，还请指出，谢谢。
下一篇总结下如何写好链表代码。
我们下期见。
image
网友评论