链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
链表是什么
和顺序表不同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。例如，使用链表存储 {1,2,3}，各个元素在内存中的存储状态可能是：
图 1 数据分散存储在内存中
可以看到，数据不仅没有集中存放，在内存中的存储次序也是混乱的。那么，链表是如何存储数据间逻辑关系的呢？ 链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，如下图所示：
图 2 链表的实现方案
显然，我们只需要记住元素 1 的存储位置，通过它的指针就可以找到元素 2，通过元素 2 的指针就可以找到元素 3，以此类推，各个元素的先后次序一目了然。 像图 2 这样，数据元素随机存储在内存中，通过指针维系数据之间“一对一”的逻辑关系，这样的存储结构就是链表。
结点（节点）
很多教材中，也将“结点”写成“节点”，它们是一个意思。
在链表中，每个数据元素都配有一个指针，这意味着，链表上的每个“元素”都长下图这个样子：
图 3 链表中的结点结构
数据域用来存储元素的值，指针域用来存放指针。数据结构中，通常将图 3 这样的整体称为结点。 也就是说，链表中实际存放的是一个一个的结点，数据元素存放在各个结点的数据域中。举个简单的例子，图 2 中 {1,2,3} 的存储状态用链表表示，如下图所示：
图 4 链表中的结点
在 C 语言中，可以用结构体表示链表中的结点，例如：
typedef struct link{
char elem; //代表数据域
struct link * next; //代表指针域，指向直接后继元素
}Link;
我们习惯将结点中的指针命名为 next，因此指针域又常称为“Next 域”。
头结点、头指针和首元结点
图 4 所示的链表并不完整，一个完整的链表应该由以下几部分构成：
头指针：一个和结点类型相同的指针，它的特点是：永远指向链表中的第一个结点。上文提到过，我们需要记录链表中第一个元素的存储位置，就是用头指针实现。结点：链表中的节点又细分为头结点、首元结点和其它结点：
头结点：某些场景中，为了方便解决问题，会故意在链表的开头放置一个空结点，这样的结点就称为头结点。也就是说，头结点是位于链表开头、数据域为空（不利用）的结点。首元结点：指的是链表开头第一个存有数据的结点。其他节点：链表中其他的节点。
也就是说，一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针，但头结点不是必须的。 例如，创建一个包含头结点的链表存储 {1,2,3}，如下图所示：
图 5 完整的链表示意图
再次强调，头指针永远指向链表中的第一个结点。换句话说，如果链表中包含头结点，那么头指针指向的是头结点，反之头指针指向首元结点。
链表的创建
创建一个链表，实现步骤如下：
定义一个头指针；创建一个头结点或者首元结点，让头指针指向它；每创建一个结点，都令其直接前驱结点的指针指向它。
例如，创建一个存储 {1,2,3,4} 且无头节点的链表，C 语言实现代码为：
Link* initLink() {
int i;
//1、创建头指针
Link* p = NULL;
//2、创建首元结点
Link* temp = (Link*)malloc(sizeof(Link));
temp->elem = 1;
temp->next = NULL;
//头指针指向首元结点
p = temp;
//3、每创建一个结点，都令其直接前驱结点的指针指向它
for (i = 2; i < 5; i++) {
//创建一个结点
Link* a = (Link*)malloc(sizeof(Link));
a->elem = i;
a->next = NULL;
//每次 temp 指向的结点就是 a 的直接前驱结点
temp->next = a;
//temp指向下一个结点（也就是a),为下次添加结点做准备
temp = temp->next;
}
return p;
}
再比如，创建一个存储 {1,2,3,4} 且含头节点的链表，则 C 语言实现代码为：
Link* initLink() {
int i;
//1、创建头指针
Link* p = NULL;
//2、创建头结点
Link* temp = (Link*)malloc(sizeof(Link));
temp->elem = 0;
temp->next = NULL;
//头指针指向头结点
p = temp;
//3、每创建一个结点，都令其直接前驱结点的指针指向它
for (i = 1; i < 5; i++) {
//创建一个结点
Link* a = (Link*)malloc(sizeof(Link));
a->elem = i;
a->next = NULL;
//每次 temp 指向的结点就是 a 的直接前驱结点
temp->next = a;
//temp指向下一个结点（也就是a),为下次添加结点做准备
temp = temp->next;
}
return p;
}
链表的使用
对于创建好的链表，我们可以依次获取链表中存储的数据，例如：
#include
#include
//链表中节点的结构
typedef struct link {
int elem;
struct link* next;
}Link;
Link* initLink() {
int i;
//1、创建头指针
Link* p = NULL;
//2、创建头结点
Link* temp = (Link*)malloc(sizeof(Link));
temp->elem = 0;
temp->next = NULL;
//头指针指向头结点
p = temp;
//3、每创建一个结点，都令其直接前驱结点的指针指向它
for (i = 1; i < 5; i++) {
//创建一个结点
Link* a = (Link*)malloc(sizeof(Link));
a->elem = i;
a->next = NULL;
//每次 temp 指向的结点就是 a 的直接前驱结点
temp->next = a;
//temp指向下一个结点（也就是a),为下次添加结点做准备
temp = temp->next;
}
return p;
}
void display(Link* p) {
Link* temp = p;//temp指针用来遍历链表
//只要temp指向结点的next值不是NULL，就执行输出语句。
while (temp) {
Link* f = temp;//准备释放链表中的结点
printf("%d ", temp->elem);
temp = temp->next;
free(f);
}
printf("\n");
}
int main() {
Link* p = NULL;
printf("初始化链表为：\n");
//创建链表{1,2,3,4}
p = initLink();
//输出链表中的数据
display(p);
return 0;
}
程序中创建的是带头结点的链表，头结点的数据域存储的是元素 0，因此最终的输出结果为：
0 1 2 3 4
如果不想输出头结点的值，可以将 p->next 作为实参传递给 display() 函数。 如果程序中创建的是不带头结点的链表，最终的输出结果应该是：
1 2 3 4
单链表的基本操作（增删查改）
学会创建链表之后，本节继续讲解链表的一些基本操作，包括向链表中添加数据、删除链表中的数据、查找和更改链表中的数据。
1) 链表插入元素
同顺序表一样，向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
插入到链表的头部，作为首元节点；插入到链表中间的某个位置；插入到链表的最末端，作为链表中最后一个结点；
对于有头结点的链表，3 种插入元素的实现思想是相同的，具体步骤是：
将新结点的 next 指针指向插入位置后的结点；将插入位置前结点的 next 指针指向插入结点；
例如，在链表 {1,2,3,4} 的基础上分别实现在头部、中间、尾部插入新元素 5，其实现过程如图 1 所示：
图 1 带头结点链表插入元素的 3 种情况
从图中可以看出，虽然新元素的插入位置不同，但实现插入操作的方法是一致的，都是先执行步骤 1 ，再执行步骤 2。实现代码如下：
void insertElem(Link* p, int elem, int add) {
int i;
Link* c = NULL;
Link* temp = p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (i = 1; i < add; i++) {
temp = temp->next;
if (temp == NULL) {
printf("插入位置无效\n");
return;
}
}
//创建插入结点c
c = (Link*)malloc(sizeof(Link));
c->elem = elem;
//① 将新结点的 next 指针指向插入位置后的结点
c->next = temp->next;
//② 将插入位置前结点的 next 指针指向插入结点；
temp->next = c;
}
注意：链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。
对于没有头结点的链表，在头部插入结点比较特殊，需要单独实现。
图 2 不带头结点链表插入元素的 3 种情况
和 2)、3) 种情况相比，由于链表没有头结点，在头部插入新结点，此结点之前没有任何结点，实现的步骤如下：
将新结点的指针指向首元结点；将头指针指向新结点。
实现代码如下：
Link* insertElem(Link* p, int elem, int add) {
if (add == 1) {
//创建插入结点c
Link* c = (Link*)malloc(sizeof(Link));
c->elem = elem;
c->next = p;
p = c;
return p;
}
else {
int i;
Link* c = NULL;
Link* temp = p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (i = 1; i < add-1; i++) {
temp = temp->next;
if (temp == NULL) {
printf("插入位置无效\n");
return p;
}
}
//创建插入结点c
c = (Link*)malloc(sizeof(Link));
c->elem = elem;
//向链表中插入结点
c->next = temp->next;
temp->next = c;
return p;
}
}
注意当 add==1 成立时，形参指针 p 的值会发生变化，因此需要它的新值作为函数的返回值返回。
2) 链表删除元素
从链表中删除指定数据元素时，实则就是将存有该数据元素的节点从链表中摘除。 对于有头结点的链表来说，无论删除头部（首元结点）、中部、尾部的结点，实现方式都一样，执行以下三步操作：
找到目标元素所在结点的直接前驱结点；将目标结点从链表中摘下来;手动释放结点占用的内存空间；
从链表上摘除目标节点，只需找到该节点的直接前驱节点 temp，执行如下操作：
temp->next=temp->next->next;
例如，从存有 {1,2,3,4} 的链表中删除存储元素 3 的结点，则此代码的执行效果如图 3 所示：
图 3 带头结点链表删除元素
实现代码如下：
//p为原链表，elem 为要删除的目标元素
int delElem(Link* p, int elem) {
Link* del = NULL, *temp = p;
int find = 0;
//1、找到目标元素的直接前驱结点
while (temp->next) {
if (temp->next->elem == elem) {
find = 1;
break;
}
temp = temp->next;
}
if (find == 0) {
return -1;//删除失败
}
else
{
//标记要删除的结点
del = temp->next;
//2、将目标结点从链表上摘除
temp->next = temp->next->next;
//3、释放目标结点
free(del);
return 1;
}
}
对于不带头结点的链表，需要单独考虑删除首元结点的情况，删除其它结点的方式和图 3 完全相同，如下图所示：
图 4 不带头结点链表删除结点
实现代码如下：
//p为原链表，elem 为要删除的目标元素
int delElem(Link** p, int elem) {
Link* del = NULL, *temp = *p;
//删除首元结点需要单独考虑
if (temp->elem == elem) {
(*p) = (*p)->next;
free(temp);
return 1;
}
else
{
int find = 0;
//1、找到目标元素的直接前驱结点
while (temp->next) {
if (temp->next->elem == elem) {
find = 1;
break;
}
temp = temp->next;
}
if (find == 0) {
return -1;//删除失败
}
else
{
//标记要删除的结点
del = temp->next;
//2、将目标结点从链表上摘除
temp->next = temp->next->next;
//3、释放目标结点
free(del);
return 1;
}
}
}
函数返回 1 时，表示删除成功；返回 -1，表示删除失败。注意，该函数的形参 p 为二级指针，调用时需要传递链表头指针的地址。
3) 链表查找元素
在链表中查找指定数据元素，最常用的方法是：从首元结点开始依次遍历所有节点，直至找到存储目标元素的结点。如果遍历至最后一个结点仍未找到，表明链表中没有存储该元素。 因此，链表中查找特定数据元素的 C 语言实现代码为：
//p为原链表，elem表示被查找元素
int selectElem(Link* p, int elem) {
int i = 1;
//带头结点，p 指向首元结点
p = p->next;
while (p) {
if (p->elem == elem) {
return i;
}
p = p->next;
i++;
}
return -1;//返回-1，表示未找到
}
注意第 5 行代码，对于有结点的链表，需要先将 p 指针指向首元结点；反之，对于不带头结点的链表，注释掉第 5 行代码即可。
4) 链表更新元素
更新链表中的元素，只需通过遍历找到存储此元素的节点，对节点中的数据域做更改操作即可。 直接给出链表中更新数据元素的 C 语言实现代码：
//p 为有头结点的链表，oldElem 为旧元素，newElem 为新元素
int amendElem(Link* p, int oldElem, int newElem) {
p = p->next;
while (p) {
if (p->elem == oldElem) {
p->elem = newElem;
return 1;
}
p = p->next;
}
return -1;
}
函数返回 1，表示更改成功；返回数字 -1，表示更改失败。如果是没有头结点的链表，直接删除第 3 行代码即可。
总结
以上内容详细介绍了对链表中数据元素做"增删查改"的实现过程及 C 语言代码，最后给大家一段完整的代码，实现对有头结点链表的“增删查改”：
#include
#include
//链表中节点的结构
typedef struct link {
int elem;
struct link* next;
}Link;
Link* initLink() {
int i;
//1、创建头指针
Link* p = NULL;
//2、创建头结点
Link* temp = (Link*)malloc(sizeof(Link));
temp->elem = 0;
temp->next = NULL;
//头指针指向头结点
p = temp;
//3、每创建一个结点，都令其直接前驱结点的指针指向它
for (i = 1; i < 5; i++) {
//创建一个结点
Link* a = (Link*)malloc(sizeof(Link));
a->elem = i;
a->next = NULL;
//每次 temp 指向的结点就是 a 的直接前驱结点
temp->next = a;
//temp指向下一个结点（也就是a),为下次添加结点做准备
temp = temp->next;
}
return p;
}
//p为链表，elem为目标元素，add为要插入的位置
void insertElem(Link* p, int elem, int add) {
int i;
Link* c = NULL;
Link* temp = p;//创建临时结点temp
//首先找到要插入位置的上一个结点
for (i = 1; i < add; i++) {
temp = temp->next;
if (temp == NULL) {
printf("插入位置无效\n");
return;
}
}
//创建插入结点c
c = (Link*)malloc(sizeof(Link));
c->elem = elem;
//① 将新结点的 next 指针指向插入位置后的结点
c->next = temp->next;
//② 将插入位置前结点的 next 指针指向插入结点；
temp->next = c;
}
//p为原链表，elem 为要删除的目标元素
int delElem(Link* p, int elem) {
Link* del = NULL, *temp = p;
int find = 0;
//1、找到目标元素的直接前驱结点
while (temp->next) {
if (temp->next->elem == elem) {
find = 1;
break;
}
temp = temp->next;
}
if (find == 0) {
return -1;//删除失败
}
else
{
//标记要删除的结点
del = temp->next;
//2、将目标结点从链表上摘除
temp->next = temp->next->next;
//3、释放目标结点
free(del);
return 1;
}
}
//p为原链表，elem表示被查找元素
int selectElem(Link* p, int elem) {
int i = 1;
//带头结点，p 指向首元结点
p = p->next;
while (p) {
if (p->elem == elem) {
return i;
}
p = p->next;
i++;
}
return -1;//返回-1，表示未找到
}
//p 为有头结点的链表，oldElem 为旧元素，newElem 为新元素
int amendElem(Link* p, int oldElem, int newElem) {
p = p->next;
while (p) {
if (p->elem == oldElem) {
p->elem = newElem;
return 1;
}
p = p->next;
}
return -1;
}
//输出链表中各个结点的元素
void display(Link* p) {
p = p->next;
while (p) {
printf("%d ", p->elem);
p = p->next;
}
printf("\n");
}
//释放链表
void Link_free(Link* p) {
Link* fr = NULL;
while (p->next)
{
fr = p->next;
p->next = p->next->next;
free(fr);
}
free(p);
}
int main() {
Link* p = initLink();
printf("初始化链表为：\n");
display(p);
printf("在第 3 的位置上添加元素 6：\n");
insertElem(p, 6, 3);
display(p);
printf("删除元素4：\n");
delElem(p, 4);
display(p);
printf("查找元素 2：\n");
printf("元素 2 的位置为：%d\n", selectElem(p, 2));
printf("更改元素 1 的值为 6：\n");
amendElem(p, 1, 6);
display(p);
Link_free(p);
return 0;
}
执行结果为：
初始化链表为： 1 2 3 4 在第 3 的位置上添加元素 6： 1 2 6 3 4 删除元素4： 1 2 6 3 查找元素 2： 元素 2 的位置为：2 更改元素 1 的值为 6： 6 2 6 3