链表是一种物理存储结构上非连续、非顺序的线性存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表中的元素（节点）中记录了与其他元素的连接关系，链表的存储方式相比于顺序表更加灵活。
链表结构多样，分带头/不带头、单向/双向和循环/不循环，相互组合可以有8种结构。本文实现不带头单向不循环链表。
逻辑结构
链表的逻辑结构是线性和连续的，各个节点通过指针进行连接。
物理结构
链表的物理结构是离散的，存储链表的内存空间是非连续的。
链表的定义
链表的每个节点包含两部分信息：有效数据(Value)和指向下一节点的指针(Next)。其中尾节点的Next指针为NULL。
typedef int SListDataType;
typedef struct SListNode
{
SListDataType data; //有效数据
struct SListNode* next; //Next指针
}SListNode;
void SLPrint(SListNode* phead); //链表打印
void SLPushBack(SListNode** phead, SListDataType x); //尾插数据
void SLPopBack(SListNode** pphead); //尾删数据
void SLPushFront(SListNode** pphead, SListDataType x); //头插数据
void SLPopFront(SListNode** pphead); //头删数据
SListNode* SListFind(SListNode* plist, SListDataType x); //查找数据
void SListInsertAfter(SListNode* pos, SListDataType x); //(后方)插入数据
void SListEraseAfter(SListNode* pos); //(后方)删除数据
void SListDestroy(SListNode* plist); //链表销毁
链表的初始化
通常用指针维护一个链表，这个指针通常指向一个链表的头结点，即phead->list。事实上，我们通常将头结点作为一个链表的代称，例如头结点head和链表head实际上是同义的。
建立一个链表通常分为两步，第一步是初始化各个节点，第二是在各个节点之间建立连接关系。完成后，即可从头结点出发，访问其余所有节点。
SListNode* plist = NULL; //用plist维护链表
接口实现和注意事项
创建节点
在下面的接口中往往需要申请一个新节点，此处将创建节点的功能单独封装成一个函数，返回新节点的地址。
SListNode* BuySLNode(const int x)
{
SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
if (newNode == NULL)
{
perror("BuySLNode::malloc");
return NULL;
}
else
{
newNode->data = x;
newNode->next = NULL;
return newNode;
}
}
链表打印
打印链表便于调试和直观显示数据。从头结点开始向后遍历链表以实现链表数据的打印。
void SLPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
尾部插入数据
在尾部插入数据时，首先要创建一个新节点，再寻找尾节点并将尾节点的Next修改为新节点的地址以实现链表和新节点的链接。
另外，需要额外考虑空表情况。当链表为空时，需要将新节点的地址赋值给plist，所以在传参时需要传plist的地址以顺利修改链表的头结点。另外，为了检查使用者的传参错误，需要对pphead进行断言。
void SLPushBack(SListNode** pphead, SListDataType x)
{
assert(pphead);
SListNode* newNode = BuySLNode(x);
if (*pphead == NULL)
{
*pphead = newNode;
}
else
{
SListNode* cur = *pphead;
while (cur->next)
{
cur = cur->next;
}
cur->next = newNode;
}
}
一种常见的错误实现如下：
void SLPushBack(SListNode** pphead, SListDataType x)
{
assert(pphead);
SListNode* newNode = BuySLNode(x);
if (*pphead == NULL) {
*pphead = newNode;
}
else
{
SListNode* cur = *pphead;
while (cur)
{
cur = cur->next;
}
cur = newNode;
}
}
出现上面错误的原因是对链表的物理结构理解不透彻，当循环停止时，tail的值为NULL，当赋值新节点的指针给tail时，尾节点的Next并未被改变，即这个操作不能将新节点链接起来。
注意深刻理解链表的物理结构：临时指针变量的地址不变，临时指针变量存储的地址在变。
尾部删除数据
空表情况和只有一个节点的情况需要额外考虑。
void SLPopBack(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
SListNode* cur = *pphead;
if (cur->next == NULL)
{
free(cur);
*pphead = NULL;
}
else
{
while (cur->next->next)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}
头部插入数据
void SLPushFront(SListNode** pphead, SListDataType x)
{
assert(pphead);
SListNode* newNode = BuySLNode(x);
newNode->next = *pphead;
*pphead = newNode;
}
头部删除数据
void SLPopFront(SListNode** pphead)
{
assert(pphead);
assert(*pphead);
SListNode* nextNode = (*pphead)->next;
free(*pphead);
*pphead = nextNode;
}
查找数据
SListNode* SListFind(SListNode* plist, SListDataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x) {
return cur;
}
cur = cur->next;
}
return NULL;
}
在指定位置后方插入数据
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* DelNode = pos->next;
assert(DelNode);//最后一个节点后面没有节点
SListNode* nextNode = DelNode->next;
free(DelNode);
DelNode = NULL;
pos->next = nextNode;
}
删除指定位置后方的一个数据
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* DelNode = pos->next;
assert(DelNode);//最后一个节点后面没有节点
SListNode* nextNode = DelNode->next;
free(DelNode);
DelNode = NULL;
pos->next = nextNode;
}
链表销毁
void SListDestroy(SListNode* plist)
{
while (plist->next != NULL)
{
SListEraseAfter(plist);
}
free(plist);
}
无头单向不循环链表的缺点
可以注意到，上述实现中间插入和删除数据都是在指定位置的后方进行操作，这是因为由于在单向不循环链表中，无法直接找到一个节点的前驱节点和后继节点，若要实现删除指定位置和在指定位置的前面插入一个节点，需要从头遍历链表找到pos位置的前驱节点，效率较低。STL库中对单向链表这种接口的实现的原因也是如此。
STL中单向链表中的部分接口:
链表具有以下缺点：
- 链表的随机访问效率较低。当需要寻找一个节点时，要从链表的头结点开始遍历寻找。
- 链表占用的内存较多。因为每个链表节点不仅要存储有效数据，还要额外存储指针。不过这些额外的内存在如今已经不值一提，所以这个缺点几乎可以忽略不计。