知识反刍--链表

¶知识反刍–链表

学而不思则惘

¶尝试概念阐述：

链表也是一种线性结构，我们把链表的每个位置称作节点，每个节点存储的是本身的数据信息和指向前后节点的指针，最后一个节点指向NULL
和数组不一样，链表并不需要物理位置上连续的内存空间，因为每个节点通过指针联系在一起，好处就是链表的插入删除操作不需要做数据整体的移动，只需要改变该位置的指针信息；
坏处是，过长的链表很容易造成内存碎片，可能会导致内存利用率降低，而且对CPU缓存机制也不友好
链表的分类：根据链表节点存储信息的区别，和链表是否头尾相连，分为：
1. 单链表：每个节点只持有指向下一个节点的指针，只能向后遍历
2. 双链表：每个节点都持有前后节点的指针，可以双向遍历
3. 循环链表：链表的头尾相连，即链表的最后一个节点持有的指针指向链表头节点的位置，形成一个环状

¶概念简化：

链表的结构类似于：你，你的朋友，你朋友的朋友，你朋友的朋友的朋友，分散在火车的四节车厢，你们都只知道自己朋友所在的车厢，想找他去那节车厢就可以：
链表的删除操作等于你的朋友要下车，临走前还告诉你他有个朋友在7号车：
从上面这个过程来看，这比数组的删除方便太多，那么问题来了，在命运的安排下碰巧一群彼此有联系的人上了同一趟火车，就像这样：
然后坐在第一节车厢的你A听你的朋友B说他的老同学C的前男友D听说大学同学E最近交的女朋友F的双胞胎妹妹G的闺蜜H的男朋友I最近劈腿交的女朋友J名字和你女朋友一样！，**你是不是得去看看？**那怎么去呢，你只认识B，B只认识C，只能一节节车厢问过去，走过10节车厢就能看见那个名字和你女友一样的J了：
**一节车厢假设25米，10节就是250米，是不是很简单？？？当然不是！**因为你不知道J所在的位置，所以你只能用这种方式去找J，和数组的随机访问相比，瞬间弱爆。（找到最后想起来你是单身狗，可能前面已经打起来了:) ）；

¶链表指针：

在链表中最容易出错的地方是指针的指向位置，稍有不慎就会导致链表从某处断开，还是以火车上你的熟人为例：
你是A，后面依次是你只认识的人B和B只认识的人C…直到G ；你们按照顺序在自己手上记了各自认识的人的手机号，你的朋友B下车的时候要去洗手，还想把C的联系方式给你，怎么给呢？先去洗手然后再告诉你手机：“这是我那朋友的联系方式，你看…咦号码呢？”就会发生这种情况，然后B丢失了C的联系方式，也就再也无法通过C去间接认识其他人。所以正确的顺序是：B先把C的联系方式给你，然后他再洗手，下车
也就是在链表的删除操作中：B要先把自己指向的C和A关联起来，就是让A先指向C，然后B再指向空，这样才不会丢失和C的联系，顺序是下图的1，2：

¶双链表：

顾名思义，链表的节点存储了向前的指针，也存储了向后的指针，好处就是可以很方便地进行前后的遍历；坏处就是需要多一个指针的存储空间，但大部分情况下双链表使用地反而要多一些，以空间换时间以及和存储的对象相比，一个引用占用的空间并不大
还是用上面的例子说明一下，假设这样一个场景：你要找到D这个人，D是你的朋友B认识的人C的朋友，一路问过去找到了一个好像是D的人，要怎么确认呢？如果你认识C，那么你可以直接问C这个是不是他的朋友D，但你不认识，你只能描述一下长相然后让B去问他的朋友C：D是不是长这样？ 为什么这个过程这么麻烦？因为D不知道C在车上，所以D没法知道是谁指出了自己的位置：
而双链表的结构就类似于这样：
你们和各自的朋友之间持有联系方式，再出现让你去找D的场景时你顺序问过去，当你找到一个疑似D的生物而又不确定是不是，D也许会问是不是C介绍你来的，这样就能确认这是你的朋友B的朋友C说的那个D，而不需要你再回头叫B去问一次C他的朋友D的外貌特征
双链表的删除操作和单链表一样，只是多了一个要分配的指针；假设你们还是非常奇怪地在手上写了彼此的联系方式，然后下车前都要去洗手，完了还都想把朋友介绍给自己的朋友，例如你的朋友B，想把C介绍给你，B就得给你C的联系方式，B还得提前问下C的意见，然后把你的联系方式给C，自己再洗手下车，那么顺序是怎样的？
B需要先让你拥有C的联系方式，再让C拥有你的联系方式，或者顺序颠倒，然后他才可以去洗手下车，不然你就把车门焊死让他下不了车；你的手上只能写一个号码，所以你把B的号码擦了写了C的，C的手上只能写两个号码，为了记你的号码，她把B的号码擦了，写了你的号码；B洗完手干干净净没有号码；步骤如图：1，2，3