【数据结构】单链表：数据结构中的舞者，穿梭于理论与实践的舞池

 欢迎来到白刘的领域   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;
}