在数据结构1——顺序表（C语言版）中，我们已经了解了顺序表的使用和实现，总结一下顺序表的优点：
①尾插尾删效率足够快；
②下标的随机访问和修改也足够方便。
可除此之外顺序表也确实存在着不足：
①头部和中部的插入删除效率都不高（时间复杂度为O(N)）；
②扩容需要申请新空间，拷贝数据，释放旧空间，有一定的消耗；
③扩容可能存在空间浪费（我们的扩容函数是2倍增长，比如：当前容量是100，我需要再插入3个数据，按照我的2倍扩容机制就会扩容到200，这时就会浪费了97个数据的空间）。
了解了顺序表的不足，下面我们就来学习一下链表，看一看链表能不能解决顺序表的不足。
目录
1.链表
1.1链表的概念及结构
1.2 链表的分类
2.无头单链表的实现
1. 节点
2.遍历链表
3.动态增加新节点
4.查找（修改）
5.插入
5.1 尾插
5.2 头插
5.3 在pos之前插入x
5.4 在pos之后插入x
6.删除
6.1 尾删
6.2 头删
6.3 删除pos位置
6.4 删除pos的后一个位置
7.测试（仅测试一个）
源代码
SList.h
SList.c
test.c
1.链表
为了避免像顺序表那样插入数据时造成扩容浪费，那我就边插入边扩容行不行呢？只要插入一个新数据我就开一块空间存一个。那么问题来了，如果这么搞，这些数据就不连续了啊，那还怎么像顺序表那样成为一个表结构呢？~~~~~~对！不要忘了指针，我们可以用指针把这写不连续的空间串起来啊！
1.1链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
也就是说，链表并不像顺序表那样在物理空间上是连续存储的，链表的每一个单位里存的不仅仅有数据域，还存的有指针域，我们把每一个这样的单位称为节点。
如图：
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
①单向或者双向
②带头或者不带头
③循环或者非循环
④最常用的两个
1.无头单向非循环链表
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
2.带头双向循环链表
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
2.无头单链表的实现
1. 节点
经过上面的分析我们得知，链表的主要结构为节点，所以我们先用结构体定义节点：
//定义节点
typedef int SLTDataType;//typedef节点的数据域
typedef struct SListNode
{
SLTDataType data;//定义节点的数据域
struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;2.遍历链表
//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;//定义当前节点
//while (cur != NULL)//等于空就结束
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点
}
printf("NULL\n");
}3.动态增加新节点
//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//malloc为空直接退出
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
4.查找（修改）
//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}5.插入
5.1 尾插
//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
//改变结构体的指针，所以要用到指针的指针
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;//定义尾节点
while (tail->next != NULL)//只有尾节点的next指针为空
{
tail = tail->next;
}
//改变结构体，只需用到结构体的指针即可
tail->next = newnode;
}
}5.2 头插
//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
5.3 在pos之前插入x
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}5.4 在pos之后插入x
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = pos->next;
}6.删除
6.1 尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1、空
assert(*pphead);
//2、一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//3、一个以上节点 找尾
{
SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空
SLTNode* tail = *pphead;
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}6.2 头删
//头删函数实现
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//空
assert(*pphead);
//非空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}6.3 删除pos位置
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
6.4 删除pos的后一个位置
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//检查pos是否为尾节点
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}7.测试（仅测试一个）
int main()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
return 0;
}
*源代码
SList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义节点
typedef int SLTDataType;//typedef节点的数据域
typedef struct SListNode
{
SLTDataType data;//定义节点的数据域
struct SListNode* next;//定义指向下一个节点的指针
}SLTNode;
//遍历链表函数声明
void SLTPrint(SLTNode* phead);
//增加新节点函数声明
SLTNode* BuySListNode(SLTDataType x);
//尾插函数声明
void SLTPushBack(SLTNode** phead, SLTDataType x);
//头插函数声明
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删函数声明
void SLTPopBack(SLTNode** pphead);
//头删函数声明
void SLTPopFront(SLTNode** pphead);
//查找下标pos函数声明
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos之后插入x
void SLTInsertAfter( SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
//遍历链表函数实现
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;//定义当前节点
//while (cur != NULL)//等于空就结束
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;//将下一个节点的地址（指针）赋值给当前节点
}
printf("NULL\n");
}
//增加新节点函数实现
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);//malloc为空直接退出
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//尾插函数实现
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
//改变结构体的指针，所以要用到指针的指针
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;//定义尾节点
while (tail->next != NULL)//只有尾节点的next指针为空
{
tail = tail->next;
}
//改变结构体，只需用到结构体的指针即可
tail->next = newnode;
}
}
//头插函数实现
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//尾删函数声明
void SLTPopBack(SLTNode** pphead)
{
assert(pphead);
//1、空
assert(*pphead);
//2、一个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else//3、一个以上节点 找尾
{
SLTNode* tailPrev = NULL;//将要尾删的前一个节点的指针域置空
SLTNode* tail = *pphead;
while (tail->next)
{
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
}
}
//头删函数实现
void SLTPopFront(SLTNode** pphead)
{
assert(pphead);
//空
assert(*pphead);
//非空
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
//查找下标pos函数实现
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
pos->next = newnode;
newnode->next = pos->next;
}
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
//检查pos是否为尾节点
assert(pos->next);
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
int main()
{
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist);
return 0;
}
