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

　　大家好呀，我是帅蛋。
　　数组的文章中给大家伙儿说过，连续的内存使得数组在进行插入和删除时需要移动大量元素，这就意味着要耗费时间。
　　在数据结构与算法中，快男才是大家的最爱，像插入和删除这么持久的蓝孩子显然不受待见。
　　后来，大家就想方设法帮助它们变快。
　　那么有没有这么一种数据结构可以达成这一目的呢？
　　链表就这么被整出来了。
　　相比于数组，链表是稍微复杂一些的数据结构，但是不难，只要跟着本蛋就能学会。
　　文章导读链表
　　首先什么是链表？
　　线性表的链式存储结构生成的表，叫做链表。
　　那么什么是链式存储结构咧？
　　链式存储结构是指用一组任意的存储单元存储线性表的数据元素，通过指针连接串联起来。
　　这里的任意指的就是，存储单元可以连续也可以不连续，这就意味着它们可以是内存中任何未被占用的地方。有味儿点讲就是只要内存这个厕所里空着的茅坑，你就随便蹲。
　　链表中的存储单元叫做节点。它和数组中只存数据信息不同，每个节点分为两部分：数据域和指针域。数据域存储的数据，指针域存储着同一个表里下一个节点的位置。
　　因为链表家族里的兄弟姐妹太多，在这里咧我只讲常见的几种链表结构：单链表、双向链表。
　　毕竟再多，我写的就累死了单链表
　　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）就可以搞定。
　　常见的链表到这就讲完啦，当然在这基础上衍生出来的像循环链表、循环双向链表都还没说，一次整太多怕你们消化不良。
　　链表这东西呢，不要怕，虽然看起来有些复杂，但其实就那几板斧，学链表的时候多在纸上画画，各种关系无所遁形，啥都就整明白了，不信你试试。
　　当然啦，能看到这的都是真爱，麻烦动动小手帮我点个赞呀
　　我是帅蛋，我们下次见！