单链表（无头单项非循环）

单项非循环）"/>

单链表（无头单项非循环）

文章目录

• 前言
• 概述
• 链表的实现
• • 初始化
  • 遍历单链表
  • 创建新节点
  • 尾插
  • 头插
  • 尾删
  • 头删
  • 单链表的查找
  • 在pos位置之前插入一个节点
  • 在pos位置删除节点
  • 在pos位置后插入节点
  • 删除pos后一个节点
  • 销毁
• 结尾

前言

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表的形式有很多，本篇文章主要介绍的是单链表且无头结点。在严版数据结构（C语言 第2版）中，单链表采用的是有头节点，这两种形式，各有利弊。含头节点的单链表在学习时，可能会容易些，但是在实践中或者在力扣中做题时，很少会有带头节点。但是有时候做题，使用带头节点的单链表会简单许多，不常见。

概述

一个结点有两个部分组成，数据域（val），指针域（next）。

链表的实现

初始化

在无头单项非循环链表中，需要声明一个数据域和指针域，指针域指向的是下一个节点的地址，数据域是当前节点的数据。这里需要注意的是，在声明指针域是，因为是结构体指针类型，所以一定要写全了。

typedef int SLNDataType;//初始化
typedef struct SListNode
{SLNDataType val;    //指针域struct SListNode* next; //指针域
}SLNode;

遍历单链表

遍历单链表，就是从单链表的第一个节点一直访问到单链表的最后一个节点。
形参接收到的是单链表的第一节点，然后需要用指针去维护节点。通过改变指针的指向，从而实现访问不同的节点。
当cue不为空指针时，继续访问下一个节点，操作为：cur=cur->next
当cur为空时，已经访问结束，无需继续遍历。
需要注意的是，这里的判断条件是cur为不为空，而不是cur->next为不为空，如果去判断cur->next，那么当cur->next==NULL时，访问的是最后一个节点为空，此时还没有遍历结束。

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

创建新节点

用malloc函数，在堆上申请一片空间来存储数据，当newcode为空时，表示开辟失败。

//创建新节点
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}

尾插

尾插又称后插法，顾名思义，是将新节点逐个插入链表的尾部来创建链表。每次申请一个新节点，读入相应的数据元素值，同时需要一个尾指针指针链表的尾节点（tail）。
需要注意的是，当链表为空时，直接将新创建的节点当作第一个节点。尾插是封装在函数里实现的，对于函数来说，形参的改变不会改变形参，因此需要传递地址，即址传递，因此需要一个二级指针接收。
pphead是头指针（plist）的地址，*pphead是对它进行解引用。

void SLTPushBack(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

空链表和链表不存在的区别：

• 空链表： 头指针为空，也就是plist==NULL表示是一个空链表
  在遍历、尾插、头插时允许空链表存在，在头删、尾删中不允许出现
• 链表不存在： ppead==NULL，表示链表不存在，这种情况不允许存在的，因此，每次都需检查一下链表存不存在。

头插

头插法即前插法，逐个将新节点插入到链表的头部来创建，每次申请一个新节点，读入相应的数据元素值。传递的也是二级指针，将新节点的头节点给newnode->next，将newhead变成头节点。

//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾删

尾删是将最后一个节点给释放掉，同时还需要保存倒数第二个节点，将它的指针域存放的地址改成NULL。需要两个指针，一个找尾，一个找倒数第二个节点，同时遍历。
空链表不能删，链表中只有一个节点的链表删除后会变成一个空链表，改变头指针需要存放地址，形参也是一个二级指针。

void SLTPopBack(SLNode** pphead)
{assert(*pphead);assert(pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

头删

头删需要改变的是头指针的地址，因此传的也是地址。tous需要考虑链表是否为空，如果是空链表就不能操作了，因此需要先断言。在删除头节点的时候，需要先保存一下头节点，否则释放了头节点，就找不到原来的头节点了。

//头删
void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);
}

单链表的查找

单链表的查找实际上就是遍历单链表，遍历过程中，找到你所需要的数值，如果是的，就返回当前节点，不是就继续往下遍历，直到链表为空。如果遍历完了还没有找到，那就说明你想查找的数值不在链表里面，返回空指针。

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* ptr = phead;while (ptr){if (ptr->val == x){return ptr;}else{ptr = ptr->next;}}return NULL;
}

在pos位置之前插入一个节点

遍历链表，找到pos之前的节点，然后按照尾插的方式插入即可。但是需要判断一种情况，如果pos就是第一个节点，那么在pos位置之前插入，那就相当于是头插了。有限制条件，pos一定是链表中的一个有效节点。

//在pos位置之前插入
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert(*pphead);assert(pos);//pos如果为头节点，就是头插if (*pphead == pos){SLTPushFront(pphead, x);}//pos不是头节点else{SLNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}SLNode* newnode = CreateNode(x);pre->next = newnode;newnode->next = pos;}
}

在pos位置删除节点

pos需要是链表中存在的节点，链表不能为空。pos可能是头节点，因此需要二级指针，这种情况就相当于头删。删除pos节点时，需要一个指针保存pos前一个节点，让pos前一个结点的指针域直接指向pos下一个节点即可，释放pos，让pos=NULL。

//在pos位置删除节点
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLTPopFront(pphead);}else{SLNode* pre = *pphead;while (pre->next != pos){pre=pre->next;}pre->next = pos->next;free(pos);pos = NULL;}
}

在pos位置后插入节点

需要保证pos是链表的一个有效节点，然后让新节点的指针域指向pos的下一个节点，然后让pos的指针域指向新节点。

//pos位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}

删除pos后一个节点

删除pos后一个节点，pos已经是一个节点，因此，链表不可能为空。
需要注意的是，这里不能直接是pos的指针域指向pos后的第二个节点，因为每一个节点都是通过malloc在堆上申请的，不使用的时候要主动的去释放掉，也就是free掉，把这块空间归还给操作系统，否则会导致内存泄漏。需要借助一个节点，保存待删节点，然后去释放借助的这一个节点并置为空指针即可。

//删除pos后一个节点
void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

销毁

void SLTDestroy(SLNode** pphead){assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

结尾

单链表相对于顺序表会难很多，也会有很多的坑点，我们要去判断链表是否为空？（在遍历、尾插、头插时允许空链表存在），头节点是否存在？什么时候传二级指针？