【数据结构】单链表

前言：我的上一篇数据结构中给大家讲解了线性表中的一种结构顺序表，它存在一些缺点，比如，我们在扩容的时候总是以二倍的形式扩容这就会造成空间的浪费，再比如，顺序表进行头插的时候，时间复杂度是O(n)。那么这些问题如何解决呢？，本期这篇博客就让我们学习一种新的数据结构单链表。

一、什么是链表？

1、 定义

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
你可以把链表理解成一个火车，火车由火车头，及一节节车厢组成，而指针就把一节节车厢连在了一起。

在火车运行高峰期，我们可以多拉几个车厢，而在人流量少的时候，我们可以摘下几节车厢，链表也可以这样操作，因此链表没有空间浪费的顾虑。

链表中每个结点，也就是每节车厢都是独立申请的，即需要插入数据时才去申请一块节点的空间，我们需要通过指针变量保存下一个结点的位置才能从当前结点找到下一个结点。

2、链表的分类

链表会根据是否带头结点、是否是循环链表以及是否是双向链表进行分类组合，因此链表一共分为8种形式，分别是：

• 不带头结点单向非循环链表
• 不带头结点双向非循环链表
• 不带头结点单向循环链表
• 不带头结点双向循环链表
• 带头结点单向非循环链表
• 带头结点双向非循环链表
• 带头结点单向循环链表
• 带头结点双向循环链表
  

以上就是链表的全部分类，我们本篇博客主要讲解单链表中的不带头结点单向非循环链表。

二、无头单向非循环链表

1、结构

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;//储存的数据struct SListNode* next;//指向下一个结点
}SLTNode;

这里依旧效仿顺序表对int取别名SLTDataType便于以后的一键修改。
无头单向非循环链表的结构可以只由一个储存数据的变量以及一个指针构成。由于指针所指向的是下一个结构体，所以它的类型是结构体指针类型。这里对struct SListNode取别名SLTNode，方便后面的代码书写。

2、单链表数据的打印

在知晓单链表的结构后，我们就要对链表进行增、删、查、改操作了，在进行它们之前呢，我们要知道如何遍历整个链表。

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur)//当当前结点不为空{printf("%d - > ", pcur->data);pcur = pcur->next;//移动到下一个结点}printf("NULL\n");
}

我们看到上面的函数，首先形参接收到链表中第一个结点的地址，然后我们定义一个结构体指针类型的变量pcur来接收它，当pcur指向的结构体指针类型不为NULL，进入循环打印该结点的数据，之后pcur移动到下一个结构体指针，直到pcur指向的结构体指针类型为NULL，结束循环，打印NULL，完成链表的遍历。好了，熟悉链表的遍历操作，我们就可以对链表进行增、删、查、改了。

3、创建结点并初始化

SLTNode* SLTbuyNode(SLTDataType x)
{//根据x创建结点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");return 1;//表示异常返回}newnode->data = x;newnode->next = NULL;return newnode;
}

这样我们根据数据x创建新节点的过程就封装在函数SLTbuyNode中了，后面将会直接调用这个函数进行新节点的创建。

4、尾插

尾插这个部分是很多人深度理解传值与传址的地方，为什么这么说呢？因为这里很多人会出错。

错误的尾插示范：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = SLTbuyNode(x);//链表为空if (phead == NULL){phead = newnode;}else{//找尾SLTNode* tail = phead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

要执行的代码：

#include "SList.h"int main()
{SLTNode* plist = NULL;//首先创建一个链表SLTPrint(plist);//打印空链表SLTPushBack(plist,1);//尾插一个数字1SLTPrint(plist);//再次打印return 0;
}

大家或许认为第一次打印的会是NULL，而第二次打印的结果将会是1->NULL
实际结果：

函数打印了两个NULL！
大家可能会认为这不就是传址调用吗？我们在调试后发现在第一次尾插时形参的链表的首地址的确发生了改变，但实参的链表首地址仍旧是0x00000000(NULL)，也就是说这不是传址调用而是传值调用。
很多人对此就表示很不理解，他们的观点一般是plist储存的不就是地址吗？所以这不就是传址调用吗？
其实并不是这样，plist它的确储存的确是某一个指针变量的地址，但是它也有它自己的地址！以上错误示范中传递的是指针中的内容，而不是指针的地址，无法改变指针的指向。就像我们在初步学习指针时学习的那样，形参只是实参的一份临时拷贝，你没有获得实参的地址你就不能改变实参。

• 解决方法一：
  在以上代码的基础上添加返回值，返回的类型是SLTNode*类型。

SLTNode* SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = SLTbuyNode(x);//链表为空if (phead == NULL){phead = newnode;}else{//找尾SLTNode* tail = phead;while (tail->next){tail = tail->next;}tail->next = newnode;}return phead;
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);plist=SLTPushBack(plist,1);SLTPrint(plist);return 0;
} 

执行结果：

• 解决方法二：
  我们在调用时传递一级指针的地址，用二级指针接收它。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = SLTbuyNode(x);//链表为空if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);return 0;
} 

执行结果：

以上两种方式都可以解决问题，只不过方法一在调用时有些麻烦，所以在本博客中将使用第二种解决方式。

5、头插

头插就是改变头指针存放的地址，无需单独考虑空链表的情况。

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

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);return 0;
} 

执行结果：

6、尾删

尾删我们不仅仅需要把尾部的结点删去，还要把尾结点前一个结点的next指针置为NULL，我们要定义一个名为ptail的结构体指针查找尾结点，再定义一个名为prev的结构体指针查找尾结点的前一个结点，这时候我们还要考虑链表中只有一个结点的情况，因为当链表中只有一个结点时，我们不能对prev进行解引用，因为此时它为NULL，会造成错误。

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* prev = NULL;//在ptail指针之前SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;//将尾指针前一个指针的next指针置为空free(ptail);ptail = NULL;}
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);return 0;
} 

执行结果：

7、头删

头删只需要注意链表是否为NULL，当链表为NULL时，是不能进行头删的，进行头删操作时，把头指针指向的下一个结点储存起来，再将头节点释放掉就可以了。

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

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);return 0;
} 

执行结果：

8、查找

就是遍历一下链表，如果找到了，就返回当前结点，如果未找到就返回NULL。

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead && *pphead);SLTNode* ptr = *pphead;while (ptr){if (ptr->data == x){return ptr;}ptr = ptr->next;}return NULL;
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTNode* find=SLTFind(&plist, 1);if (find){printf("找到了！\n");}else printf("未找到！\n");return 0;
} 

执行结果：

9、在指定位置pos之前插入数据

只需要定义一个结构体指针变量pcur，并遍历到pcur->next为pos时停止便可，之后，将它的next指针指向我们新创建的结点，再让新建立的结点的next指针指向pos就可以了。当然开头需要处理链表第一个结点就是pos的情况。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);if (pos == *pphead){SLTPushFront(pphead, x);//头插}else{SLTNode* newnode = SLTbuyNode(x);SLTNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = newnode;newnode->next = pos;}
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTNode* find=SLTFind(&plist, 1);SLTInsert(&plist, find, 5);//在数据为1的结点前面插入数据SLTPrint(plist);return 0;
} 

执行结果：

10、在指定位置pos之后插入数据

在pos位置之后插入数据的情况就比较简单，我们只需创建newnode储存新的数据，然后让newnode的next的指针指向pos的next指向的结点，再将pos的next指针指向newnode即可。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTbuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTNode* find=SLTFind(&plist, 1);SLTInsertAfter(find, 5);//在数据为1的后面插入数据SLTPrint(plist);return 0;
} 

执行结果：

11、删除pos结点

pos可能是头结点的地址，链表的头结点可能发生改变，所以形参要用二级指针。

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead && pos);if (pos == *pphead){SLTPopFront(pphead);//头删}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTNode* find=SLTFind(&plist, 1);SLTInsertAfter(find, 5);//在数据为1的后面插入数据SLTPrint(plist);SLTErase(&plist, find);SLTPrint(plist);return 0;
}

执行结果：

12、删除pos之后的结点

删除pos位置之后的结点注意不能写成这样：pos->next=pos->next->next这样写虽然可以把pos之后的结点剔除出链表，但并没有真正的删除它，因为每个结点都是通过动态内存开辟的，在不使用时要主动free掉，把这块空间还给操作系统，否则可能会导致内存泄漏，上面这样写就会导致无法释放，正确的做法应该是再次申请一个中间结点。

void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTNode* find=SLTFind(&plist, 1);SLTInsertAfter(find, 5);//在数据为1的后面插入数据SLTPrint(plist);SLTEraseAfter(find);SLTPrint(plist);return 0;
} 

执行结果：

13、销毁链表

链表的销毁需要从头节点开始，一节一节将后面的结点销毁。

void SListDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

要执行的代码：

int main()
{SLTNode* plist = NULL;SLTPrint(plist);SLTPushBack(&plist,1);SLTPrint(plist);SLTPushFront(&plist, 2);SLTPrint(plist);SLTNode* find=SLTFind(&plist, 1);SLTInsertAfter(find, 5);//在数据为1的后面插入数据SLTPrint(plist);SLTEraseAfter(find);SLTPrint(plist);SListDestroy(&plist);SLTPrint(plist);return 0;
} 

执行结果：

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！技术的探索永无止境。
道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～