数据结构——单链表详解（超详细）（1）

前言：

  小编在近日学习了单链表的知识，为了加强记忆，于是诞生了这一篇文章，单链表是数据结构比较重要的知识，读者朋友们一定要去好好的学习！这个可以说是比顺序表更好用的线性表，下面废话不多说，开始进入单链表的学习喽！

目录：

1.单链表

1.1.链表的概念与单链表

1.2.单链表的结构

1.3.单链表的性质

2.单链表功能的代码实现

2.1.单链表的打印

2.2.单链表的尾插

2.3.单链表的头插

2.4.单链表的尾删

2.5.单链表的头删

3.还有一些函数没写，由于小编不想让篇幅太大，所以分成了两部分

正文：

1.单链表

1.1.链表的概念

  链表是一种物理结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表也有很多的种类，比如单链表，双链表等等，小编今天讲述的就是单链表，下面小编来讲述一下单链表的结构！

1.2.单链表的结构

引例：

  对于单链表的结构，小编先给出一个引例：火车我相信各位读者朋友都坐过，没坐过也应该见过，火车是由车头和一节一节的车厢组成，如下图所示：

  在人们乘车少的时候，火车可以减少车厢，具体减少哪个车厢，这是可以随机指出的，并不一定就是去掉最后一个车厢，我们也可以把中间的给删除，在旅游旺季的时候，我们同样也可以加上几节车厢来应对人多车少的情况。

1.2.1.结点的概念

  单链表就类似火车车厢一样，它也可以随时的减少，随时的增加，我们把单链表中的每一表称之为结点，所以可以这么说，单链表是由一个一个结点构成的，单链表和顺序表最大的不同，就是单链表当中的结点是一个一个动态内存申请出来的，不是和顺序表一样基于数组来进行书写的，下面小编将会给各位讲述一下单链表的结构：

·1.2.2.单链表的结构

  

  小编在上图给各位读者朋友了单链表的结构图，细细一看，我们可以看出每一个结点，里面都存储着数据类型和一个地址，不难发现，结点里面的地址都对应着下一个结点，所以单链表就是靠地址来进行连接的，那么肯定有读者朋友会感到疑惑，这么一看，单链表的物理结构不还是连续的？其实这个说法是错误的，可能每一个单链表都隔着很远才进行的链接，所以单链表是不连续的，不和顺序表的一样，我们可以看到，单链表中最后一个结点指向的是NULL，这里展示了单链表也是有始有终的，下面我们来简单介绍一下单链表的性质

1.3.单链表的性质

  单链表的性质可以分为三个：

1.单链表在逻辑上是连续的（线性表统一的性质）在物理结构是不连续的。

2.结点一般都是从堆上申请的。

3.从堆上申请的空间，是按照一定策略分配出来的，每次申请的空间可能连续，也可能不连续

  其实性质我们用多了，自然也会记住了，对于编程的学习，我们不是靠死记硬背下来的，而是不断的去应用，应用多了自然就熟悉了！ 

  我们已经讲述了单链表的概念和性质，我们可不能纸上谈兵，下面，小编将带着大家手动的一步一步的去实现单链表！

2.单链表功能的代码实现

  在讲述那些单链表的增删查改之前，我们现在肯定要先创建一个单链表，我们已经学习了顺序表和单链表的知识，单链表的结构图也在上面进行展示了，那么下面我们就可以实现单链表的创建了，对于数据部分，我们不一定是存储整型，浮点型等等，所以我们可以类似顺序表用typedef关键字来对类型改名，后面我们可以统一进行替换。下面是代码的实现：

typedef int SLdate;   //方便后面整体类型的改变//创立一个单链表
typedef struct Slist {//先设置一个类型SLdate date;struct Slist* next;   //存放下一个节点的地址
}SLTNode;

  此外，对于单链表代码的书写，小编同样是分成了三个文件，与顺序表一样，这三个文件分别是头文件（用于单链表的创建，各种函数的声明），源文件（函数的实现），源文件（代码的测试），我们每写完一个函数，一定一定记着先测试，免得到后面在慢慢改，这样显得太麻烦了，下面，我们开始实现一一函数的功能！

  2.1.单链表的打印

  虽然我们还没有开始放置数据，但我们一定要先学会单链表的打印，这个与我们正常的打印是不同的！  首先，我们肯定要创建一个函数，下面是代码呈现：

  

void SLTprintf(SLTNode* phead);//此时phead代表的是头节点，就是第一个节点

  正如代码解释所说，phead属于头结点，我们想要打印每一个结点的数据，肯定要先知道它的头节点，之后我们可以通过它的头结点来开始对下一个节点进行遍历直到遇到NULL，这样我们便可以停止打印，所以不难想到，这里我们用到了循环的知识，通过每一次循环来打印数据，之后再让下一个结点代替当前结点，不过在这之前，我们应该做到对于头结点不让它做出改变，因为我们倘若任由头节点进行改变，那么之后我们在这个函数中会再也不会找到链表的头，这样就得不偿失了，所以我们用一个新的结点来存放头节点，让它做出对应的的改变，下面是代码的呈现：

void SLTprintf(SLTNode* phead)
{SLTNode* pour = phead;    //这么做是为了保证头节点不会发生改变while (pour){printf("%d->", pour->date);pour = pour->next;}printf("NULL\n");
}   //这个操作是打印单链表的数据

  2.2.单链表的尾插

  我们在简述完打印后，肯定要讲述单链表的增删查改了，我们先从单链表的尾插说起，对于单链表的尾插，这其实和顺序表的尾插有点类似的，不过在顺序表中，在顺序表中，我们是扩容操作，而在单链表中，我们实现的是插入结点操作，在插入结点之前，我们是肯定先要创建一个新的结点，作为我们要插入的结点，不过我们在实现尾插之前，肯定是要先创建一个函数的，这里有我们值得注意的一个点，那就是我们传过去的应该是单链表指针的地址，也就是传一个二级指针过去，这是一个重要的点，因为我们要对单链表指针进行改变，对于内容的改变我们需要传址调用来实现，下面是函数的创建：

void SLTPushBack(SLTNode** pphead, SLdate x);

  首先，我们需要先分装出一个函数，用来作为新结点的创建，这里我们需要用到malloc函数来对开辟出一个新的空间来作为新节点空间，之后我们再将数据转化为我们想要的数据，再让下一个结点置为空就好，这个操作可以类似于顺序表的扩容操作，下面是代码实现：

SLTNode* SLTbuynode(SLdate x)
{SLTNode* pour = (SLTNode*)malloc(sizeof(SLTNode));assert(pour);pour->date = x;pour->next = NULL;return pour;
}

  之后我们就开始进行插入操作，这里我们分为两种情况：

  第一种情况是头节点为空，这个就很简单了，我们将新节点的内容直接给予头节点就好了，这对于屏幕前的你当然是小case，尾插的大头就是下一个情况了：

  第二种情况就是头节点不为空，正式进行尾插操作，这个操作其实是蛮简单的，我们只需要先进行循环，找到尾结点，让尾结点的next指针指向新结点就好了，下面我们用图文进行解释（这里用pcur当作尾结点！）：

   这样我们便可以实现尾插操作，下面是代码实现：

void SLTPushBack(SLTNode** pphead, SLdate x)
{//首先可以先建一个函数，这个函数是来开辟一个新节点的（后面想要插入直接调用就好了）assert(pphead);SLTNode * p = SLTbuynode(x);if (*pphead == NULL)  //首先判断{*pphead = p;}else{SLTNode* pour = *pphead;   //保证头节点不做出改变while (pour -> next){pour = pour->next;}pour->next = p;}
}

2.3.单链表的头插

//头插
void SLTPushFront(SLTNode** pphead, SLdate x);

  我们在看完尾插操作以后，紧接着头插就来了，同样的，头插函数也需要先有一个新的结点的建立去，小编在上面已经叙述了，就不再多谢了，同样的，头插也同样分为了两种情况：

  第一种情况是是头结点是不存在的，这时候只需要将新节点设置为头节点就好了。

  第二种情况是头节点是存在的，这时候需要我们将新节点的下一个结点指向为原来的头节点，再将头节点更改为新节点就好了。具体情况小编用图文进行解释：

  不过此时不难看拿出，头插函数似乎是不需要分两种情况讨论的，因为两种情况都涉及了将新节点的下一个结点变为头节点，所以我们将两种情况合并下来就好了，下面是代码呈现：

void SLTPushFront(SLTNode** pphead, SLdate x)
{assert(pphead);SLTNode* newnode = SLTbuynode(x);newnode->next = *pphead;*pphead = newnode;
}

2.3.单链表的尾删

//尾删
void SLTPopBack(SLTNode** pphead);

  简单的插入函数就先告一段落了，下面我们来进行删除操作，首先登场的就是尾删，尾删操作，与顺序表的尾删一个概念，就是把单链表的尾结点置为空，首先，我们需要保证头节点是存在的，不然单链表都是空的，我们删来删去也没什么意思了，这里可以用assert断言来判断下头节点是否为空，之后我们就可以进行删除操作·。

  首先，我们要先定义两个指针一个指向头节点，这个的作用是找到尾结点，一个为空（这个的作用我们稍后就知道），之后我们采用循环，让空指针在刚开始指向第一个指针，再让第一个指针一直往后走，我们是要找到尾结点，所以我们循环结束的条件就是第一个指针的下一个结点不指向空，之后第一个指针变成了尾结点，第二个指针变成了尾结点之前的结点，这样，我们就可以让第二个指针的下一个置为空，然后再让第一个指针释放掉，这样我们就完成了尾删操作，不过此时，细心的读者朋友可能会发现，如果单链表只有头节点的话，这时候上面就不成立了，我们这里就对空指针进行解引用了，所以尾删操作，我们同样也是分为两种情况！：

  第一种是如果只有头节点的话，我们直接将头节点变为空，这里就完成了尾删操作。

  第二种情况就是正常情况，方法就是上面所讲，下面是图文解释+代码呈现：

 

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead)->next == NULL){*pphead = NULL;}else{SLTNode* pour = *pphead;SLTNode* plist = NULL;while (pour->next){plist = pour;pour = pour->next;}plist->next = NULL;free(pour);pour = NULL;}
}

2.5.单链表的头删 

  尾删我们讲完了，下面是头删环节，与尾删一样，我们首先要判断头节点是否为空，如果为空直接报错就好了，之后我们就要进行正常的头删操作了，头删操作我们也要创建一个指针·，这个指针表示头节点，之后我们直接让现头节点变成原头节点的下一个结点，然后我们再将指针释放，这里我们便完成了单链表的头删操作，是不是很简单呢？下面小编给出图文解释和代码呈现：

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pour = *pphead;*pphead = (*pphead)->next;free(pour);pour = NULL;
}

总结：

  正如小编上面所说，小编不想让文章的篇幅太大，于是小编就把博客分装成了两部分来进行书写，单链表的操作当然不仅限于这些了，下一篇将会是重点，如果文章有错误，恳请在评论区指出，小编肯定会改正，下面小编将要肝下篇文章了，那我们下一篇文章见喽！