C 语言【单链表】

单链表是一种基本的数据结构，由一系列节点组成，每个节点包含数据域和指针域。‌数据域用于存储实际的数据，而指针域则存储指向下一个节点的地址。单链表的特点包括动态存储、非连续存储、易于插入和删除。

节点可以定义成一个结构体，每个节点中包含一个数据和下一个节点的地址。

//构造节点
typedef int SLDataType;struct SLNode
{SLDataType data;struct SLNode* next;
};typedef struct SLNode SLNode;

上面的结构体定义了一个节点，节点中存放的数据类型被定义成了SLDataType类型，节点的名称叫做SLNode。

1、单链表的顺序访问

这里给出单链表的逻辑结构：首先有一个节点指针pList指向开始的节点，节点中的next存放的是下一个节点的地址。可以通过next访问下一个节点。最后一个节点的next中存放的是空指针NULL；

这里写一个打印单链表的函数，以示范单链表的访问功能；

void SLPrint(SLNode* phead);

这里需要说明的是，打印函数在访问链表的过程中不涉及更改链表，所以在设计函数时参数部分用节点的指针就可以。进一步来说，打印函数需要将每一个节点的data打印出来，这个时候可以按照如下的方式进行访问节点；

当cur为NULL时打印NULL即可，那么函数的实现可以写成如下的形式；（由于链表为空时能进行打印功能，所以不能在函数体最开始进行断言操作）

void SLPrint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

2、单链表的末尾插入

链表的末尾插入首先需要创建新的节点，这里可以创建一个新的节点指针，并对里面的内容分进行初始化，由于后面还会涉及到节点的创建，所以在这里选择将其封装成一个函数；在创建完成时，返回新节点的指针用于后续的拼接。

SLNode* SLBuyNode(SLDataType val)
{SLNode* newNode = (SLNode*)malloc(sizeof(SLNode));if (newNode == NULL){perror("PushBack malloc faile");return;}newNode->data = val;newNode->next = NULL;return newNode;
}

在末尾插入节点时会有两种情况：1、链表本身为空 2、链表不为空

当链表本身为空时，我们需要将新创建的节点与pList进行拼接，此时的操作就会改变pList的值，在写函数时我们要改变的是一级节点指针的内容，所以在函数传参时应该传入二级节点指针才能达到目的效果。

当链表pList为空时,将新创建的节点的地址newNode赋值给pList.然而在函数调用过程中形参的改变不影响实参的变化。所以在这里选择使用*pphead = newNode ，这样就可以达到修改实参的目的。

当链表不为空时，需要找到链表的最后一个节点的地址tail，修改最后一个节点的next 使其指向创建的新节点newNode。

这里需要注意的是，我们需要改变的是最后一个节点中nest的值，那么就需要最后一个节点的地址tail ，当tail->next非空时将tail->next赋值给tail即可找到最后一个节点的地址。最后将newNode赋值给tail->next即可。这样尾插节点就实现了，下面是代码实现：

void SLPushBack(SLNode** pphead,SLDataType val)
{//1、创建新的节点指针SLNode* newNode = SLBuyNode(val);//进行拼接if (*pphead == NULL){*pphead = newNode;}else{//找最后一个节点的结构体指针SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}
}

3、单链表的末尾删除

需要考虑的是当链表为空时就不能进行删除操作，所以需要在函数体开始进行断言操作。第二点：目标链表的节点数为1时，删除完节点之后要修改pList的值，使它的值为NULL;这里就需要更改pList的值，所以在函数传参时就需要传入节点的二级指针。函数声明如下：

void SLPopBack(SLNode** pphead);

当链表只有一个节点时：直接释放pList 再将其置空

当链表中的节点个数大于1时，先找到倒数第二个节点的地址，用于将倒数第二个节点中的next置为空，也需要找到倒数第一个结点的地址，直接释放再将其置为空。

那么单链表的末尾删除就可以写成如下的形式：

void SLPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)->next != NULL){//链表节点大于1个SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}else{free(*pphead);*pphead = NULL;}
}

4、单链表的头部插入

链表为空时可以进行插入操作，所以不能进行断言操作。当链表为空时，创建新节点之后需要将新节点的地址赋值给pList，在这个操作中需要修改pList的值，所以在函数传参时需要传入节点的二级指针。单链表的头部插入函数声明如下：

void SLPushFront(SLNode** pphead, SLDataType val);

在头部插入时，均需要修改pList的值。然后将新节点中next的值修改为原来pList的值

可以看到，上述的两种情况可以合并为一种情况来写，所以单链表的头部插入函数可以写成如下的形式：

void SLPushFront(SLNode** pphead, SLDataType val)
{SLNode* newNode = SLBuyNode(val);newNode->next = *pphead;*pphead = newNode;
}

5、单链表的头部删除

链表为空时不能进行删除操作，所以在函数体内要进行断言操作。每次删除一个节点之后，要将第二个节点的地址赋值给pList，在这里也需要修改pList的值，所以在函数传参时，也需要传入节点的二级指针。函数的声明如下：

void SLPopFront(SLNode** pphead);

按照上面的逻辑就可以定义函数为：

void SLPopFront(SLNode** pphead)
{assert(*pphead != NULL);SLNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

单链表的测试：

void Test1()
{SLNode* pList;pList = NULL;SLPushBack(&pList,1);SLPushBack(&pList,2);SLPushBack(&pList,3);SLPushBack(&pList,4);SLPrint(pList);SLPopBack(&pList);SLPopBack(&pList);SLPopBack(&pList);SLPopBack(&pList);SLPrint(pList);}void Test2()
{SLNode* pList;pList = NULL;SLPushBack(&pList, 1);SLPushBack(&pList, 2);SLPushBack(&pList, 3);SLPushBack(&pList, 4);SLPrint(pList);SLPushFront(&pList,1);SLPushFront(&pList,2);SLPushFront(&pList,3);SLPushFront(&pList,4);SLPrint(pList);}void Test3()
{SLNode* pList;pList = NULL;SLPushFront(&pList, 1);SLPushFront(&pList, 2);SLPushFront(&pList, 3);SLPushFront(&pList, 4);SLPrint(pList);SLPopFront(&pList);SLPrint(pList);SLPopFront(&pList);SLPrint(pList);SLPopFront(&pList);SLPrint(pList);SLPopFront(&pList);SLPrint(pList);}int main()
{Test1();Test2();Test3();return 0;
}

下附运行结果，可以观察到，上述功能均已实现。