链表

什么是链表

链表和数组是两种最基本的数据结构，两者具有本质上的差别：数组使用一块连续的内存保存数据；链表则使用多个零散的内存，并用指针将他们相连。

我们看一下两者在内存上的区别：

数组和链表的存储.jpg

你会发现，一个链表由多个节点相连，每个节点都会有两部分：一部分用于保存数据，另一部分用于保存指针，这个指针会指向下一个节点。

单链表.jpg

链表由多个节点组成，它在内存中大多是分散的，这导致了它与数组具有完全不同的性质。

链表的特性

链表的优势

我们知道，数组为了保持内存的连续性，在执行插入、删除等操作的时候需要做大量的数据搬移工作其时间复杂度是O(n)，而在链表中插入或者删除数据是非常快速的：

链表的插入和删除.jpg

链表的缺点

好和坏是一枚硬币的两面，链表因为零散的存储让插入删除变得简单，但是也无法通过计算获得数据地址，也就无法拥有“随机访问”的特性。如果链表想要访问第 k 个元素，就只能一个节点一个节点地依次遍历。所以，链表的查询会比较慢。

链表的类型

单链表

单链表是最基础的链表结构，你可以查看上面关于单链表的示意图。

循环链表

循环链表.jpg

当需要处理的数据中含有环的时候，循环链表非常有用

双向链表

双向链表.jpg

双向链表在开发中更加常见，从结构上看，双向链表可以支持O(1)时间复杂度的情况下找到前驱节点，由于这个特性，双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

你会发现，由于使用了两个指针，所以双向链表的储存效率不如单链表，但是这为数据操作提供了便利。这就是用空间换时间的设计思想，当内存空间充足的时候，如果我们追求代码执行速度就可以选择使用空间复杂度相对较高，时间复杂度相对较低的数据结构，反之亦然。

数组VS链表

我们看一下数组和链表的复杂度对比：

数组VS链表.jpg

你可以看到数组和链表在执行相关操作时在时间复杂度上的差别，但是我们并不能将目光局限于时间复杂度。而且，在实际的编程中，时间复杂度也不是选择数据结构的位移指标。

数组简单易用，使用连续的存储空间，如果你了解计算机的硬件知识，就会知道数组可以很好地利用CPU中的缓存（cache）。而链表不是连续存储，就无法使用cache提升性能。

数组的大小需要事先声明，尽管我们可以使用扩容操作扩大容量，但是这会带来额外的工作，并且如果内存中没有符合数组容量的存储空间，内存申请会失败。而链表是分散存储的，天然适合扩容和利用内存。

总结一下：和数组相比，链表更适合插入、删除操作频繁的场景，但是查询的时间复杂度较高。但是数据结构的选择依然要综合考量。

编写链表代码的技巧

链表结构虽然简单，但是编写代码却非常困难。一方面，代码大量使用指针操作，各个指针的含义经常被弄得乱七八糟，另一方面，使用指针操作需要非常细心，一不留神就会造成数据丢失或内存泄露。

在这里，专栏作者为大家梳理了编写链表的若干技巧：
1.理解指针或应用的含义：
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变啦ing的内存地址，指向了这个变量，通过指针就能找到这个变量。

2.警惕指针丢失和内存泄露：
插入节点时，要注意操作的顺序
删除链表节点时，记得手动释放内存空间

3.利用哨兵简化实现的难度：
对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样的代码实现起来非常繁琐，我们可以为链表设置一个头节点和尾节点（哨兵），从而降低代码的难度。

4.重点留意边界条件处理：
你要考虑这几个问题：
如果一个链表为空，代码能否正常工作？
如果一个链表只有一个节点，代码能否正常工作？
若干一个链表只有两个节点，代码能否正常工作？
代码逻辑在处理头节点和尾节点的时候，是否能正常工作？

5.举例画图，辅助思考：
在可能设计复杂的指针操作的时候，通过画图来帮助自己思考。

6.多写多练

---

上面就是关于链表的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间