对单链表的理解

链表的理解"/>

对单链表的理解

        本文旨在谈论个人对单链表使用上的感悟。鉴于网络上有很多人已经系统地讲述了单链表的使用，我个人想着重谈论初学者在学习单链表时可能出现的难点。可能有些是语法上的难点，有些是逻辑上的难点。

 1.单链表的引入

        单链表的引入，就是为了解决以往用数组结构存储线性表时需要连续分配大量内存时的问题。众所周知，LInux等操作系统是多任务的，每个任务运行时都会占用一部分内存，结束时又会将内存释放出来，而每个任务到来的时间，任务结束的时间是异步的，根本无法在事前统筹规划，因此操作系统只能随缘的分配内存，哪里有空分哪里，最大程度地利用内存资源。这就会导致空闲的内存呈碎片化的分布，因此指望用数组来存储大量的数据是不现实的。

       为了存储大量的线性结构数据，人们很直观地就会想到将数据存储在内存的不同位置上，哪里有空闲就存到哪里。但是这就引发了一个问题，数据之间的逻辑关系怎么体现呢？如何从一个数据元素出发找到它的前驱和后继呢？这个问题在数组中很好解决。数组，或者说顺序表的本质就是用地址的关系体现逻辑的关系，地址的相邻实际上就反映了逻辑的相邻，地址的大小关系就反映了逻辑上的前驱后继关系。但是链表就不一样了，由于内存的碎片化分布，操作系统为数据元素分配内存时都是“随缘的”，有可能逻辑上靠前的元素在地址上却是靠后的，而且地址本身也是毫无规律可循，根本不可能通过地址的关系推导逻辑的关系。

       为了解决这个问题，就只能手动记录逻辑上存在后继或者前驱关系的数据元素的地址，并且将有本数据元素有前驱后继关系的数据元素的地址与该元素“打包”存储，形成一个整体。对外只提供第一个元素的地址，外部访问者通过地址链条可以访问线性表中所有的元素，并且还能知晓元素之间的前驱后继关系。因此个人认为，链表的本质，就是在手动记录具有某种逻辑关系的数据的地址，既然无法从地址关系推倒逻辑关系，那就只能破费一点内存空间，手动地将这种关系记录下来了。

2.单链表的数据声明

      前面已经说过了，链表就是要把数据元素本身和与之具有某种逻辑关系的数据元素的地址“打包”存储，形成一个整体。那么怎么叫“打包”，怎么叫整体呢？这就要看不同的编程语言本身如何实现“打包”机制了，C语言是用的结构体，C++或者Java用的是类，其他语言可能也有自己的机制。本文主要从C语言语法出发，用结构体的方式实现打包存储。结构体的声明如下：

typedef struct node{data_t data;struct node * next;
}linked_list_t;

       关于C语言的语法，本文就不具体细说了，网上的博客多的是。从结构体的声明可以看出，这个结构体包含数据元素本身和它后继元素的地址，确实实现了数据元素有前驱或后继关系的数据元素的地址与该元素“打包”存储。数据元素就是data_t类型的成员data，这里面的data_t可以是原有的基本数据类型，也可以是我们根据实际需求自定义的数据类型，而next就是后继数据元素存放的地址。当然，选择前驱还是后继的地址是可以自己规定的，也可以两个都存储，根据习惯大家一般存储后继元素的地址，这就是单链表；如果前驱和后继都想存储，那就是双向链表。其实大家也能发现，存的地址越多，操作起来就更方便，逻辑关系也就更容易找到，但是就得耗费更多的内存空间。实际上，数据结构和算法研究的目的就是不断地在为计算机程序在时间和空间上取得平衡进行优化，螺蛳壳里做道场，看你具体的取舍了。

       说一句题外话，链表不仅能存储线性的结构，包括树形的结构，图结构都能用链表来存储。因为前文提到过，链表的本质，就是在手动记录具有某种逻辑关系的数据的地址。这种关系，之于线性结构就是前驱后继，之于树形结构就是左子树，右子树，父节点，之于图结构，就变成了节点之间的邻接关系等等。因此只要把逻辑关系往某种逻辑结构上一套，链表就能表示相应的数据结构。因此，链表的功能是非常强大的，学好它真的是收获颇丰。

      说回上面的结构体声明，这种写法可能就会让初学者感到困惑：我明明定义的是struct node类型，怎么里面又包含了struct node类型呢？结构体能这样嵌套吗？链表的这种写法往往能劝退一大波人，因此在这里我着重说一下这个问题。结构体本身是不能嵌套的，因为编译器无法得知结构体占用的内存大小，也就无法为结构体变量分配内存。像下面的写法就是错误的：

typedef struct node{data_t data;struct node next; //错误的，这样就变成无限套娃了
}link_list_t;

     但是，最上面的写法却是正确的，结构体里面不能嵌套结构体本身，但是却能嵌套指向结构体的指针，为何？因为指针类型的大小永远是固定的，不管是指向什么东西的指针，在64位系统中就是八个字节，在32位系统中就是四个字节，因此在结构体里面包括一个指向该结构体的指针是不影响编译器判断结构体所占用的内存大小的，这样写是没有任何问题的。

       这样又引发了一个新的写法，定义一个指向结构体的指针p，也就是link_list_t *p，它的类型与p中指向的next成员，也就是p->next的类型是一样的，理解这一点非常重要！！！，这就意味着这两者之间是可以相互赋值的，也就是会出现p=p->next的写法，很多人能理清链表的逻辑操作，但是却写不出看不懂代码，说白了，就是对类似p=p->next的语法感到困惑，一个结构体变量怎么能用它成员进行赋值呢？但是链表是可以这样做的，而且是经常这样做的，因为二者都是指针，所以就是能这样操作。对于初学者而言，要想玩转链表，就必须能看得懂写得出这种语句，而且不能觉得别扭，而且这还涉及到结构体与指针的操作，所以说白了，链表也是对结构体和指针的综合运用，非常考验大家的C语言基础功底，而这些功底，就不是本文要说的了。大家可以看各种网课和博客，那里讲得会非常详细。

3.单链表的创建

       这一点本文不想着墨太多，无非就是在堆区动态分配一块link_list_t类型的内存作为头节点，然后在栈区设立一个指针变量存储其地址，这里说一下有头链表和无头链表的区别。

       链表根据其头节点是否存储数据可以分为有头链表和无头链表，有头链表的头结点是不存放数据的，而无头链表的头节点是存放数据的，应用较多的是有头链表。有些人会好奇，不存放数据的节点是干什么的？答曰为了统一插入和删除操作，减少对外接口的变化。试想，对于一个头节点就存放数据的链表来说，一旦在表头插入或删除数据，势必就要重新创建节点，这样单链表头结点的地址就会不断发生变化，而头结点的地址就是链表对外的接口，是进入整个链表的入口。就像一个公共场所一样，不管公共场所内部发生了什么，它的入口的位置一般是不会发生改变的，不然外面的人就很难进去。有头链表中的头节点就起到了“中流砥柱”的作用，无论链表内部发生了怎样的插入删除修改操作，头节点在内存中的位置都不会发生改变，改变的只是头结点中指针成员next的值，有一种“任尔东西南北风，我自岿然不动”的境界。因此在实际开发中，有头链表应用更多，后面讲解的也是有头链表。

4.单链表结点的插入

       如果是无头链表，那么插入操作就得分成头插入和其他位置插入两种，因为头插法会引起头结点指针值的改变，带来开发上的麻烦。不过有头链表的头结点省去了这个麻烦，不管是在哪里操作，逻辑都是一样的，很便利对吧。当然代价就是多了一块不存数据的内存空间，有点浪费。不过我前面也说了，程序都是在空间和时间上进行取舍，现在的趋势是用空间换时间，毕竟根据摩尔定律，硬件越来越便宜，那当然是多用硬件节省时间为妙，这就是使用有头链表的本质原因。

      插入操作的本质是什么？是将原来相邻的具有前驱后继的两个节点分开，将原来前驱节点的后继，后继节点的前驱变成新节点，使之不再具备前驱后继关系。而前驱和后继的关系在链表中是手动记录的，所以改变原有的前驱后继就是改变节点中的指针域。单链表中由于不记录节点的前驱信息，因此只需要的是原有前驱的后继信息，之于后继节点的前驱信息，我们没有记录自然改变不了，但是我们可以改新节点的后继信息对吧，因为原有后继节点的的前驱变成新节点了嘛，所以新节点的后继就是原来的后继节点。看着像绕口令，但实际上逻辑很简单，我这里画一张图大家就懂了。

     假定我们想把新节点N插入到头节点H和地址为0x123的节点之间。怎么操作呢？实际上就套我前面说的话就行了，原来的前驱节点就是头节点H，原来的后继节点就是地址为0x123的节点。可是链表对外的接口只有头结点的地址，那么如何才能找到地址为0x123的节点呢？当然是访问头节点的指针域next也就是H->next，H->next就是原来的后继节点。那好，按照前面所说的，将原来前驱节点的后继改成新节点的具体操作就是

H->next = N;

       将原有后继节点的前驱信息改成新节点的话，我们没办法操作前驱信息，因为压根就没记录，所以这一条我们得反着做，也就是将新节点的后继信息改成原有后继节点，具体操作就是

N->next = H->next;

        看起来可以了对吧？但是大家有没有发现问题呢？H->next信息已经被我改了！也就是说我先将原有前驱节点的后继改成了新节点，我找不到原有的后继节点了！我通过上面的操作实际上把新节点的后继节点变成了自己，而不是原来的后继节点！这样做毫无疑问是错误的，本质上是因为我先修改了原有前驱节点的后继信息，让整个链表发生了断裂。而插入操作肯定不能破坏原有的逻辑关系，所以这两步实际上需要反着执行，而且顺序绝不能颠倒：

N->next = H -> next;
H->next = N;

       这里有一个经验之谈。我们如果想修改原有链表的指针链条的话，往往需要先修改新节点的信息，尽量不破坏原有链表的结构，等新节点的指针域信息修改完备之后再修改原有链表的信息。因为原有链表的指针链一旦断裂就很难愈合，我们不能为了一个节点而破坏原来的很多节点对吧。这一点经验后面的双向链表和二叉树链表会非常有用，因为那里指针域的信息更多，需要修改的地方也更多，所以一定要明晰修改顺序，不然就会发生链表的断裂。

5.单链表节点的删除

       与插入操作相对应，删除操作的本质是通过删除某个节点，将原来不具备前驱后继关系的两个节点变得具有前驱后继关系。所以删除操作就是修改某个节点的指针域，使之与另外一个原本不具备逻辑关系的节点建立前驱后继关系。这里依然通过图片说明：

      假如我们想删除地址为0x999的节点，本质上，就是让原本不具备前驱后继关系的0x123和0x72c节点建立前驱后继关系。由于单链表只维护后继关系，因此只需要改变0x123的后继信息即可。

      问题的关键是，我们怎么找到0x123，0x999，0x72c这几个节点呢？我们现在只知道头结点的地址H。从图中我们发现要删除的节点0x999的前驱节点是0x123节点，而0x123节点是H的后继，所以0x123实际上就是H->next，这个地址我们用一个指针变量p来保存，也就是

link_list_t *p = H->next;

       有些人会问，明明要删除0x999节点，为什么要把指针移动到它的前驱0x123呢？为什么不一步到位指向0x999本身呢？因为我刚说了，删除某个节点的本质是让该节点的前驱和后继建立直接的联系，而单链表只维护后继关系，因此需要改变该节点的前驱中的信息。可是如果我把指针移动到要删除的节点本身，我就找不到它的前驱了，因此指针必须指向要删除节点的前驱，这样的话，要删除的节点，和要删除的节点的后继信息我都能通过指针链找到，分别是

p->next;     //要删除的节点
p->next->next;   //要删除节点的后继节点

        这样一来，让被删除节点的前驱后继直接建立联系的操作就变成了

p->next = p->next->next;

       通过以上代码，就实现了让被删除的节点的前驱和后继建立直接的联系的操作了。不过这还有个问题，逻辑上是把0x999节点删除了，可实际上那块节点还在内存中使用，并没有得到释放，而删除之后理应将该区域释放掉供别的任务使用。可是经过刚才的操作，被删除的那块空间已经找不到了，因为链表已经重构了。那么怎么办呢？实际上可以在重新构建指针链之前，将被删除的节点的地址缓存，缓存之后在重构指针链，之后将那块地址释放掉。因此删除链表的操作如下：

link_list_t *q=p->next;//q就是要删除的节点，将其地址缓存
p->next = q->next; //指针链重构
free(q); //释放被删除节点的地址

        这里依然有个经验之谈，就是在删除某个位置上的节点时，需要从头节点遍历指针，但是遍历的终点并不是要被删除的节点，而是它的前驱，原因刚才说了，因为单链表只有后继信息，如果一步到位你是找不到被删除节点的前驱的，也就无从谈起将前驱和后继直接建立联系。如果操作的是双向链表，则不存在这种限制。

6.总结

        本文简单地将我对链表的感悟说了一通，洋洋洒洒几千字也没啥逻辑，很多都是废话甚至有可能误人子弟，还希望各位大佬们指正，这也是我第一次写技术博客。对链表的操作，我有个形象的比喻就是针线活，对指针链的改变不就像是穿针引线吗？而且改变指针链就像有些针线活一样，每一步走线的位置是不能错的，错了就得推倒重来了。所以对链表的操作需要开发人员拥有做针线活一样的细心和耐心。昔日诸葛亮让张飞绣花，就是为了锻炼张飞粗中有细的性格，这对打仗来说非常重要，而在这里对链表的操作也需要各位“粗中有细”，方能在操作链表的时候游刃有余。