【数据结构之单链表的实现（不带头）】

1.单链表

1.1概念与结构

链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

可以用下图便于理解

节（结）点：

与顺序表不同的是，链表里面的每节“车厢”都是独立申请下来的空间，所以我们之为“节/结点”。

每个节（结）点的组成主要是两部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。上图中指针变量plist保存的是第一个节点的地址，我们称plist为“指向”第一个节点，如果我们希望plist指向第二个节点时，只需要修改plist保存的内容为0x0012FFA0即可。

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

链表的结构：

假设当前链表中保存的是整型数据，当然我们也可以保存其它同一类型的数据。因此为了便于操作其它数据类型的操作，我们对类型进行重命名。
typedef int SLTDatatype;
typedef struct SlistNode
{SLTDatatype data;struct SlistNode* next;
}SLTNode;

1.2链表的性质

链式结构在逻辑上是连续的，在物构上不是连续的。
节点一般是从堆上申请的。（涉及动态内存管理）
从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，也可能不连续。

2.单链表的实现

实现链表的时候和实现顺序表的时候类似，都需要三个文件，SlistNode.c文件，SlistNode.h文件和test.c（测试文件）。

2.1 SlistNode.h 链表结构的定义以及函数功能的声明部分

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//单链表的结构定义   不带头所以不需要初始化
typedef int SLTDatatype;
typedef struct SlistNode
{SLTDatatype data;struct SlistNode* next;
}SLTNode;//函数的声明部分//单链表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x);//单链表的数据的打印
void SLTPrint(SLTNode* phead);//单链表的删除
//单链表的尾删
void SLTPopBack(SLTNode** pphead);
//单链表的头删
void SLTPopFront(SLTNode** pphead);//单链表中数据的查找
SLTNode* SLTFind(SLTNode* phead, SLTDatatype x);//单链表指定位置的操作
//指定位置之前的插入
void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDatatype x);
//指定位置之后数据的插入
void SLTInsertBack(SLTNode* pos, SLTDatatype x);//指定位置数据的删除
void SLTErase(SLTNode** pphead, SLTNode* pos);
//指定位置之后的删除
void SLTEraseAfter(SLTNode* pos);//链表的销毁
void SListDestroy(SLTNode**pphead);

2.2 SlistNode.c 函数功能的实现

2.2.1 单链表数据的插入：尾插和头插
//申请新节点
SLTNode* SLTBuyNode(SLTDatatype x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
实现思路：

在实现链表的插入之前，需要先封装一个可以申请新节点的函数，由链表的概念以及性质我们只需要用malloc函数进行申请新节点，随后插入时只需要改变节点的的指向关系即可。
//单链表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{assert(pphead);//链表为空和非空两种情况SLTNode* newnode = SLTBuyNode(x);if (*pphead==NULL){*pphead = newnode;}else{SLTNode* pcur = *pphead;//先遍历找到尾节点while (pcur->next != NULL){pcur = pcur->next;}pcur->next = newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDatatype x)
{assert(pphead );SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
实现思路：

尾插头插之前头需要对所传的二级指针进行判空（检查是否为有效地址），除此之外尾插和头插都需要申请到新节点。

尾插：分为两种情况，一种是链表为空，另一种是链表非空。之所以分成这两种情况是因为在尾插的时候需要遍历链表完之后对当前位置的节点进行解引用，如果为空链表，就会报错（对空链表不能进行访问）。所以链表为空时直接将申请的新节点的地址给*pphead，非空时先让链表进行遍历，遍历到下一个节点为空时停下来，将所申请到新节点的地址给当前节点中的next指针。

头插：头插很简单，对于空链表和非空链表都可以，先将申请到新节点的next指针指向头结点，再将新节点的地址给头结点。

PS：我们在这里之所以传的是二级指针，是因为我们在刚开始（见test.c）中申请节点的时候，使用的是一级指针申请的变量，由指针内容我们可以知道要通过函数改变一个指针指向的内容就需要用该变量的指针，在这里该变量是一级指针，所以我们需要用指针的指针即就是二级指针。

2.2.2 单链表数据的删除：尾删和头删
//单链表的删除
//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead && * pphead);//分成两种情况：只有一个节点（不需要遍历链表）  有多个节点if ((*pphead)->next == NULL){*pphead = NULL;}else{SLTNode* prev = *pphead, * ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next= NULL;}
}
//单链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//先把头结点的下一个节点保存下来SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
实现思路：

尾删头删实现的时候都需要先进行对pphead和*pphead（确保链表非空）进行判空。

尾删：因为链表中只有一个节点的时候不存在前驱节点，则直接将头结点释放掉且置为空。而当链表中有多个节点时，则需要先找到前驱节点，释放掉尾节点，再将前驱节点的next和尾节点置为空。

头删：先将头结点所指向的next保存在next中，然后释放掉头结点，最后将保存的next赋值给头节点。

2.2.3 单链表数据的查找
//单链表中数据的查找
SLTNode* SLTFind(SLTNode* phead, SLTDatatype x)
{assert(phead);//遍历链表SLTNode* pcur = phead;while (pcur){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}
实现思路：先对所传的变量进行判空（是否有效）。再遍历链表，如果当前节点的数据为所要查找的数据，则返回当前节点的地址。

2.2.4 单链表指定位置的操作

2.2.4.1 指定位置的插入
//指定位置之前的插入     特别注意
void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{assert(pphead);assert(pos);if (*pphead == pos){//头结点没有前一个节点，故就直接调用头插的方法SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//将prev newnode pos连接起来newnode->next = prev->next;prev->next = newnode;}
}
//指定位置之后数据的插入
void SLTInsertBack(SLTNode* pos, SLTDatatype x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//将pos newnode pos->next连接起来newnode->next = pos->next;pos->next = newnode;
}
实现思路： 指定位置之前的插入（还需要判断pphead的有效性）和指定位置之后插入，都需要对要插入位置pos的有效性进行判断。

指定位置之前的插入：

（1.）当插入的位置恰好为头节点时，（因为头结点没有前驱节点）所以直接调用头插的方法即可。

（2.）当插入的位置为其他节点的位置时，先申请一个新节点，然后遍历找到要插入位置之前的前驱节点prev，然后将newnode,prev,pos三个位置的节点连接起来。

指定位置之后的插入：

先判断位置的有效性，再申请一个新节点，最后将pos ,newnode,pos->next位置的节点连接起来。

2.2.4.2 指定位置的删除
//指定位置数据的删除     特别注意
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead&&pos);if (*pphead == pos){//如果是删除的头结点，头结点没有前驱节点SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//先将申请的节点释放掉，将pos pos->next->next连接起来prev->next = pos->next;free(pos);pos = NULL;}
}
//指定位置之后的删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos&&pos->next);//先释放pos之后的节点，再将pos pos->next->next 连接起来SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
实现思路：

指定位置的数据的删除：需要先判断pphead和*pphead的有效性以及pos位置的有效性。（1.）如果要删除的是头结点（不存在前驱节点），则只需要调用头删即可。

（2.）如果删除的不是头结点的位置，则需要先遍历链表找到要删除位置的前驱节点，然后先将删除位置的下一个节点保存下来,其次将pos前后位置的节点连接起来，再释放掉要删除位置的节点，将pos置为空。

指定位置之后的数据的删除：需要先判断pos和pos->next的有效性。

先将pos位置之后的节点保存到del中，然后将pos和del->next连接起来，再释放掉del,最后将del置为空即可。

2.2.5 单链表的销毁
//链表的销毁
void SListDestroy(SLTNode** pphead)
{assert(pphead&&*pphead);//每次循环释放 每次释放节点时先将下一个节点保存下来SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}
实现思路：应先判断pphead和*pphead的有效性。

因为每一个节点都是动态内存申请的，所以我们应该遍历链表一一释放节点。但是需要注意的是每次释放释放节点时，应该先把当前要删除节点的下一个位置保存下来，在释放完之后，将保存的节点的位置赋值给当前节点。