链表，画几下就整明白了！

　　大家好呀，我是帅蛋。
　　数组 的文章中给大家伙儿说过，连续的内存使得数组在进行插入和删除时需要移动大量元素，这就意味着要耗费时间。
　　在数据结构与算法中，快男才是大家的最爱，像插入和删除这么持久的蓝孩子显然不受待见。
　　后来，大家就想方设法帮助它们变快。
　　那么有没有这么一种数据结构可以达成这一目的呢？
　　链表就这么被整出来了。
　　相比于数组，链表是稍微复杂一些的数据结构，但是不难，只要跟着本蛋就能学会。
　　文章导读链表
　　首先什么是链表？
　　线性表的链式存储结构生成的表，叫做链表。
　　那么什么是链式存储结构咧？
　　链式存储结构是指 用一组任意的存储单元存储线性表的数据元素，通过指针连接串联起来。
　　这里的＂任意＂指的就是， 存储单元可以连续也可以不连续， 这就意味着 它们可以是内存中任何未被占用的地方。 有味儿点讲就是只要内存这个厕所里空着的茅坑，你就随便蹲。
　　链表中的存储单元叫做 节点 。它和数组中只存数据信息不同，每个节点分为两部分： 数据域和指针域 。数据域存储的数据，指针域存储着同一个表里下一个节点的位置。
　　因为链表家族里的兄弟姐妹太多，在这里咧我只讲常见的几种链表结构：单链表、双向链表。
　　毕竟再多，我写的就累死了… 单链表
　　n 个节点可以链接成一个链表，如果 链表中的每个节点只包含一个指针域，这个链表就叫做单链表。
　　单链表的指针域指向的是下一个节点的地址，我们把指向下个节点地址的指针叫做 后继指针 。
　　单链表的第一个节点的存储位置叫做 头指针 ， 最后一个节点的后继指针为空 ，一般用 NULL 或者 ＂^＂ 表示。
　　除了上面的，有时候为了操作方便，会在单链表的第一个节点前面加一个节点，称之为 头节点 。这个头节点一般不存储任何内容，它的指针域指向单链表的第一个节点。
　　臭宝：停停停！又是头指针又是头节点的，有点懵…
　　帅蛋：莫慌，有我。
　　头指针与头节点的区别
　　头指针 ，顾名思义，是指向链表第一个结点的指针，如果有头结点的话，那么就是指向头结点的指针。
　　它是链表的必备元素且无论链表是否为空，头指针都不能为空 ，因为在访问链表的时候你总得知道它在什么位置，这样才能通过它的指针域找到下一个结点的位置，也就是说知道了头指针，整个链表的元素我们都是可以访问的。
　　所以头指针必须要存在，这也就是我们常说的 标识 ，这也就是为什么我们一般用头指针来表示链表。
　　头结点 ，是放在第一个元素的节点之前，它的数据域一般没有意义，并且它本身也不是链表必须要带的。
　　它的设立是单纯是为了操作的统一和方便 ，其实就是为了在某些时候可以更方便的对链表进行操作，有了头结点，我们在对第一个元素前插入或者删除结点的时候，它的操作与其它结点的操作就统一了。
　　除此以外，还有一种啥也没有，空空空空～ 空链表 。
　　不知道大家发现了没，不管是带头节点，还是不带头节点，或者是空的链表，它们都是有头指针的，这正印证了我在上面提到过的＂ 头指针是链表的必备元素，无论链表是否为空，头指针都不能为空 ＂。
　　别说话，夸我~
　　单链表的操作
　　和数组一样，单链表也有查找、插入和删除等操作。因为链表的存储空间是不连续的，所以链表的插入和删除操作是很快速的。
　　1、插入操作
　　假设我们要完成一个插入操作：在节点 p 后面插入节点 s。
　　正确的做法是，只需要将节点 s 插入到节点 p 和节点 p.next 之间就可以，说起来很简单，具体操作请看下图。
　　从上图中可以看出，单链表的插入其实根本不需要惊动其它的节点，只需要让 s.next 的指针和 p.next 的指针稍作改变。 让节点 s 的后继指针指向 p 的后继节点，然后 p 的后继指针指向节点 s，这里切记，插入操作的顺序一定不能改变。
　　可以看出插入操作的时间复杂度是 O(1)。
　　2、删除操作
　　假设我们要完成一个删除操作：删除节点 p 的后继节点 q。
　　其实也简单，就是将 p 的后继指针绕过 q，直接指向 q 的后继节点即可，具体操作如下图。
　　由上图看出，同样只需要一步就可以实现删除操作，直接让 p.next 指向 q.next 即可，所以删除操作的时间复杂度为 O(1)。
　　3、查找操作
　　当然啦，有快的地方就有慢的地方，元素的查找就是链表美中不足的地方。
　　数组在内存中排排坐不同，链表的在内存中的地址是分散的，只能通过前一个节点的 next 才知道当前节点的位置，所以在链表中想要找第 i 个元素，只能傻傻的从头开始找，直到找到第 i 个元素位置。
　　从这可以看出，链表中查找操作的时间复杂度是 O(n)。
　　单链表实际应用场景
　　单链表说了这么多也差不多了，辣么有个问题，我学了这个玩意能用在哪呢？
　　easy！
　　单链表的应用的话一般能用在  2 种场景 下：
　　(1) 第 1 种基操。 在你应用的场景中，插入和删除的操作特别多，你不想因为这俩操作浪费你太多的时间，此时用单链表，可以改善插入和删除操作浪费的时间。
　　(2) 第 2 种骚操。在你应用的场景种，不知道有多少个元素，那这个时候你用单链表，每来一个新的元素你就链在表里，这种情况是用链表处理的绝佳方式。也是很容易被大家忽略的。
　　双向链表
　　双向链表 ，顾名思义，两个方向向的链表。 相比起单链表来说，它多了一个前驱指针 prev，指向前驱节点。 这样双向链表既可以往前走，也可以往后走。
　　从上面两张图看，双向链表多了一个前驱指针，使得在内存上比单链表占用更多的空间，但是 双向链表在查询链表元素的时候会更加方便 ，比如可以在 O(1) 的时间内超找到当前节点的前驱节点，这是典型的用空间换时间。
　　空间换时间 ，在内存够用的情况下，为了追求更快的执行速度，选择空间复杂度较高，时间复杂度较低的数据结构或者算法。
　　既然用了时间换空间，那双向链表比单链表快在哪个地方呢？那这个还是从插入、删除操作说起。
　　可能在这臭宝们拿起键盘会说，单链表的插入和删除都已经是 O(1) 了，还要怎么快？
　　其实准确点来说， 插入和删除是 O(1)，更多的是针对插入或删除这单个动作来说的，在实际情况下，一切都有前置条件。 在某些前置条件下的实际应用场景，双向链表比单链表更快。
　　下面开始表演。
　　插入操作优势
　　插入操作，无非就是 2 种情况： 在 ＂data域等于某个特定值＂的节点前或者后插入一个新的节点。 在给定的节点前或者后插入一个新的节点。
　　针对第 1 种，这俩时间复杂度都差不多。都是分两个步骤：
　　第一步找到 data 域等于某个特定值的节点，无论单链表还是双向链表都需要从头开始一个一个的遍历，这一步的时间复杂度都是 O(n)。
　　第二步就是插入操作。如果都是向后插入的话，那时间复杂度都是 O(1)，如果是向前插入的话，那单链表慢一些，它需要再重新找到特定值节点的前驱节点，这个时间又花费 O(n)，而双向链表不用，因为它有前驱节点，直接就能找到特定值节点的前驱节点，这个时间花费的是 O(1) 。
　　针对第 2 种情况，其实他就是第 1 种情况中的第二步，已经找到了要插入的节点，如果都是向后插入的话，单链表和双链表的时间复杂度都一样，都是 O(1)。差别就差向前插入，向前插入的话就需要知道当前节点的前驱节点，单链表需要重新遍历到当前节点的前驱节点，总的时间复杂度是 O(n)，而双向链表一下子就能找到它的前驱节点，时间复杂度是 O(1)。
　　这就是双向链表优势于单链表的地方。
　　删除操作优势
　　删除操作，和插入操作差不多，也基本上是 2 种情况： 删除 ＂data域等于某个特定值＂的节点。 删除给定的节点。
　　第 1 种情况就不说了，单链表和双向链表都一样，都是从头开始一个个的遍历，时间复杂度都是 O(n)。
　　第 2 种情况，删除给定的节点，这就要求需要知道这个节点的前驱节点。单链表需要从头开始找，直到＂node.next = 当前节点＂的适合，才是找到了当前节点的前驱节点 node，这个过程的时间复杂度是 O(n)。而双向链表直接就知道它的前驱节点，只需要时间复杂度是 O(1) 就可以搞定。
　　常见的链表到这就讲完啦，当然在这基础上衍生出来的像循环链表、循环双向链表都还没说，一次整太多怕你们消化不良。
　　链表这东西呢，不要怕，虽然看起来有些复杂，但其实就那几板斧，学链表的时候多在纸上画画，各种关系无所遁形，啥都就整明白了，不信你试试。
　　当然啦，能看到这的都是真爱， 麻烦动动小手帮我点个赞呀 ～
　　我是帅蛋，我们下次见！