欢迎来到白刘的领域   Miracle_86.-CSDN博客

         系列专栏   数据结构与算法

先赞后看，已成习惯

   创作不易，多多支持！

一、链表的概念和结构

1.1 链表的概念

在上一篇文章中，我们了解了线性表(linear list)，并且学习了其中一种线性表——顺序表(Sequence List)。链表也是线性表的一种，那么它是一种什么样的结构呢？

链表，顾名思义，带着链子的表。日常生活中，我们知道链子是用来链接两个东西的，那么我们可以很容易理解，顺序表是基于数组实现的，是一个元素一个元素挨着的，那链表我们就可以理解为每个元素用链子连接起来，这样就形成了链表(Linked List)。

1.2 链表的结构

那么我们得到了两个链表的组成的关键元素，一个是每个元素，我们管它叫节点(或结点)，另一个就是那个链子。而在C语言中，我们用结构体来实现节点，用指针来充当链，连接两个节点。

在生活中链表类似于我们的火车的结构，在物理上它是一种存储结构非顺序非连续的结构。

节点的组成主要由两个部分组成：一个是数值域，用来保存当前节点的数据，一个是指针域，用来保存下一个节点的地址(指针变量)。

如图所示，指针变量plist保存的是第一个节点的地址，如果我们想让plist指向第二个节点，我们只需要将plist保存的内容修改为0x0012FFD0。

为什么我们需要指针变量来保存下一个节点的位置？

因为之前我们说了，链表不同于顺序表，它在内存中的地址不一定是连续的，它是独立申请的(对其插入数据时才申请一个节点)。我们需要通过指针才能从当前节点找到下一个节点。

所以我们可以通过一个结构体来实现一个节点，它要有一个节点的数据以及一个指针变量来保存下一个节点的地址，代码如下：

struct SListNode{ 	int data; //节点数据	struct SListNode* next; //指针变量⽤保存下⼀个节点的地址};

当然我们也可以用typedef来进行修改，方便我们后续操作。

typedef int SLTDataType;typedef struct SListNode{ 	SLTDataType data; //节点数据	struct SListNode* next; //指针保存下⼀个节点的地址}SLTNode;

我们如何将链表进行打印呢？

首先我们将节点传到打印函数，然后我们创建了一个指向头结点的结构体指针，利用循环从头遍历到尾，每次打印完成令pcur指向pcur的next节点。这里注意的就是结构体成员的访问的问题，我们用到了->操作符，在前面的博客我们都介绍过。

武器大师——操作符详解（下）-CSDN博客

代码如下：

void SLTPrint(SLTNode* phead){     SLTNode *cur = phead;    while(cur){         printf("%d ",cur->data);        cur = cur->next;    }    printf("\n");}

 二、单链表的实现

上面我们知道了什么是链表，那单链表又是什么呢？单链表(Singly Linked List)，一般所指的是“不带头单向不循环链表”。

我们实现的功能无非就四个“增、删、查、改”。

2.1 增

2.1.1 尾插

尾插，顾名思义，在尾部插入，俗称后入(bushi)。

首先我们要申请新的节点，我们可以写一个申请节点的函数。

SLTNode* BuyNode(SLTDataType x) {     SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));    if (node == NULL) {         perror("malloc fail!\n");        exit(1);    }    node->data = x;    node->next = NULL;    return node;}

首先我们用malloc函数动态申请一块内存，然后将节点的数据赋进去。

void SLTPushBack(SLTNode** pphead, SLTDataType x) {     assert(pphead);    SLTNode* node = BuyNode(x);    if (*pphead == NULL) {         *pphead = node;        return;    }    //找尾    SLTNode* cur = *pphead;    while (cur->next) {         cur = cur->next;    }    cur->next = node;}

接下来的代码逻辑特别简单，首先我们通过buynode函数创建了一个节点，然后我们判空，如果这个链表是空的，我们直接将指针变量pphead赋为node。如果不是空的，那我们就需要找到链表的尾部，我们可以通过循环来找到尾部，首先为了防止原来数据被破坏，我们创建一个指向第一个节点的指针变量cur，而不是直接遍历pphead。

注意我们如何找尾，通过判断该节点的下一个位置是否为空。

这里还有一个细节就是，我们传入的是二级指针，因为我们要修改一个数据的话，需要传地址，而那个数据如果是指针的话，我们就需要传指针的地址，也就是二级指针。

2.1.2 头插

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

这个代码逻辑也很简单，首先我们assert断言防止访问空指针，之后buynode函数申请节点，然后将结点接到头部，也就是*pphead，之后别忘了将*pphead再指向node，形成新的头。

2.2 删

2.2.1 尾删

尾删也很简单，仔细思考，我们只需要两步就能完成，一个是找尾，一个是删除。

首先我们来看找尾，我们可以用循环，再加上两个指针，

//找尾//    SLTNode *cur = *pphead;//    SLTNode *prev = NULL;//    while(cur->next){ //        prev = cur;//        cur = cur->next;//    }//    prev->next = NULL;//    free(cur);//    cur = NULL;

首先cur指向头，prev指向空，cur用来找尾，prev用来保存上一个节点的地址。当cur的下一个位置为NULL时循环结束，意味着找到最后一个节点了，我们将它所指的位置free掉(因为是动态开辟出来的)，然后指针置空即可完成删除。

还有一种方法可以用一个指针就解决，

SLTNode* tail = *pphead;    while (tail->next->next)     {         tail = tail->next;    }    free(tail->next);    tail->next = NULL;

 我们判断条件改成这样，实际上我们找的tail是倒数第二个节点，所以最后的删除需要改成tail的next为NULL。

2.2.2 头删

头删的逻辑就更加简单了，我们只需要创建一个变量来保存原来的头节点，方便我们后续删除，然后让原头节点移到下一个结点成为新的头结点，然后删掉原来的。如果我们不保存，我们没有办法找到原来的头结点。

代码如下：

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

2.3 查

这个实现也很简单，就是遍历，然后匹配。由于是查找，而不是对数据进行修改，所以传一级指针即可。

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

2.4 改

2.4.1 在pos前插入

将图画出来我们就清晰明了了。我们如果想把node插入到pos前，我们只需要将node的next指向pos，然后将prev的next指向node，这样就构成了插入操作。

试想一下，1和2的操作可以调换顺序吗？答案是不可以，这是因为如果我们先做2，这个时候我们就找不到pos了，也就不能执行1操作了。有人会问，我创建两个变量来记录这两个点的位置不可以吗？可以，但是没必要。

之后我们来看代码部分，首先我们要创建一个node节点，用buynode函数。正常情况，我们需要找pos的前一个节点prev，利用循环即可。如果只有一个节点怎么办呢？这个时候直接头插就可以了。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {     assert(pphead);    assert(pos);    SLTNode* node = BuyNode(x);    if (*pphead == pos) {         //        node->next = pos;        //        *pphead = node;        SLTPushFront(pphead, x);        return;    }    //找pos的前一个节点    SLTNode* prev = *pphead;    while (prev->next) {         if (prev->next == pos) {             break;        }        prev = prev->next;    }    node->next = pos;    prev->next = node;}

2.4.2 删除pos

其实逻辑也是很简单的，要删除pos的话，我们需要找到pos前面的节点保存，否则就找不到了。

void SLTErase(SLTNode** pphead, SLTNode* pos) { 	assert(pphead);	assert(pos);	if (*pphead == pos) { 		//        SLTNode *del = *pphead;		//        *pphead = (*pphead)->next;		//        free(del);		//        del = NULL;		SLTPopFront(pphead);		return;	}	//找pos的前一个节点	SLTNode* prev = *pphead;	while (prev->next) { 		if (prev->next == pos) { 			break;		}		prev = prev->next;	}	prev->next = pos->next;	free(pos);	//    pos = NULL;//没有存在的必要}

并且要注意连接好pos后面的节点后再删除，不然也找不到。

2.4.3 在pos后插入

逻辑跟在pos前插入一样，也要注意顺序，只不过在pos之后插入不需要传链表第一个节点了，只需要传pos即可。

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

2.4.4 删除pos后的节点

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

其实看到这你就发现，对链表的操作无非就是保存节点，然后连接，同时画图操作也可以对我们学习数据结构有所帮助。

2.5 链表的销毁

我们将链表每个节点通过循环遍历free掉即可，唯一比较吃操作的就是创建一个用于保存下一个节点的位置的指针。

//销毁链表void SListDesTroy(SLTNode** pphead){ 	assert(pphead && *pphead);	SLTNode* pcur = *pphead;	while (pcur)	{ 		SLTNode* next = pcur->next;		free(pcur);		pcur = next;	}	*pphead = NULL;}