声明
本博文系本人学生时代的学习笔记，最初发布时，存在诸多语法错误。由于本人工作后不再从事C语言相关的开发工作，故本博文也未作修订。目前该博文中已知的错误已作更正，另在此对此前为读者造成的困扰表示歉意。
2025.9.7

参考文献

本博文为半摘记性质
——
声明：全文主干部分摘自
[1] 杨智明. 数据结构（C语言版）[M]. 第一版. 北京:北京理工大学出版社, 2016.

有很多描述数据结构的文档及书籍，标注为使用C语言进行编写，但实际上却使用了C++的语法特性，因此其代码根本无法被C编译器编译，请读者注意甄别。

部分资料转自互联网各类技术博客，内容有一定改动，并非全文转载。本人尊重各位的知识成果，大幅引用的文章原文网址已在各小节末尾给出。
——
C语言在线运行工具：https://tool.lu/coderunner/

1链表简介

由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表。链表即线性表的链式表示和实现。

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

链表由一系列结点（node，链表中每一个元素称为结点）组成，每一次为一个结构体 动态分配的内存空间，可称之为一个结点，每个结点之间可以是不连续的，但结点内是连续的。结点个数是不受限定的，可以随时删改，这是与数组相比的优点。

结点由指针域和数据域构成。存储数据元素信息的成员项称为数据域；存放下一结点的首地址的成员项被称为指针域，存储信息称为指针。第n个结点的指针域内存入第n+1个结点的首地址，如此串联下去直到最后一个结点，即尾结点，没有直接后继，其指针域为NULL，被称为空指针，表示该链表结束。

如果链表的每一个结点只有一个指针，则称为单链表（单向链表）。单链表分为两种：不带头结点的链表和带头结点的链表。
所有的链表都有一个头指针 head，头指针具有标识一个单链表的作用，整个单链表的存取必须从头指针开始进行，头指针指示链表的第一个结点，即首元结点。
在首元结点之前附加一个结点，称作头结点，可以不存储数据，也可存储附加信息。无论是否有头结点，头指针始终指向链表的第一个结点。如果有头结点，头指针就指向头结点。不带头结点时，这时链表直接在首元结点存入数据，那么当从头插入数据时，head需要时刻变化。因此带头结点的链表性能更优良。
在这里插入图片描述

图中每个节点，an表示数据，^表示NULL。

深刻理解：带头结点和不带头结点的区别 使用头结点的优势

2链表的使用

对链表的使用涉及到内存的动态分配。
下面介绍如何新建一个动态单链表以及对该链表的主要操作。

2.1线性表的链式储存结构的类型定义

单链表在C语言中可用结构指针来描述。

typedef int ElemType;	//数据域data用通用类型标识符ElemType表示
typedef struct LNode
{
   ElemType data;  //数据域，存放元素值
   struct LNode *next;//指针域，指向后继结点
}LNode, *LinkList;

2.2单链表的建立

在单向链表中插入结点，先要确定插入的位置。当待插结点插在工作指针p所指的结点之前称为头插（前插法）；当待插结点插在工作指针p所指的结点之后称为尾插（后插法）。

这里展示用尾插入法建立带头结点的单链表（正序建立），为了使新结点能够插入到表尾，除了头指针L、指向指向单链表中任意结点的工作指针p，还需增加一个始终指向尾结点的尾指针s。

  1. 建立头结点，并将头指针（L）指向头结点，头结点的指针域写NULL；
  2. 利用一个工作指针（p)，从头到尾依次指向链表中的每个结点。生成一个新结点，用p指向该结点，并向数据域写数据，指针域写NULL；
  3. 将上一步生成的新结点插入表尾，新结点的地址赋给前一个地址的指针域；
  4. 将第二个生成的新结点插入在第一个结点后，重复第二到第四步，使新结点总是插在当前链表的表尾，便可建立一个含有n个结点的单链表。

在这里插入图片描述

尾插法算法实现

//*L：头指针
//n：新建节点数量
int CreateListTail(LinkList *L,int n){
    LNode *s,*p; //尾指针，工作指针 
    *L=(LinkList *)malloc(sizeof(LNode));//创建头结点
    (*L)->next = NULL; //将头结点next域置空
    s=*L;//s指向头结点，开始时头结点和尾结点是同一个
	
	int i;
    for(i=0;i<n;i++){
      p=(LNode *)malloc(sizeof(LNode));//创建数据结点,函数malloc分配了一个LNode类型的结点空间，并将其首地址存入指针变量p中
      printf("please enter a new elem data No.%d.\n", i);
	  scanf("%d",&p->data);
      s->next=p;//新结点插入到当前链表的表尾
      s=p;//使s指向作为尾结点的新结点 
    }
    s->next = NULL;	//表示单链表结束
    printf("enter finished.\n");
    return OK;
}

头插法和尾插法建立单链表

2.3单链表的遍历

利用一个工作指针p，从头到尾依次指向链表中的每个结点，当指针指向某个结点时，就输出该结点数据域中的内容，直到指针为空。如果是空链表，就只输出有关信息并返回调用函数。

遍历算法实现

//*L：头指针
int DisplayList(LinkList *L)
{
	LNode *p =(*L)->next ;//工作指针p初始化
	while ( p!=NULL )
	 { 
		 printf("%d\n",p->data);
		 p=p->next;
	 }	 
	 return OK;
}

2.4单链表的查找

不同于顺序表，链表不是随机存储结构，只能从链表首元结点出发，顺着指针域逐个结点向下查找。
有以下几种查找项：

  1. 按序号查找
  2. 按值查找
  3. 相等的结点个数
  4. 最大值/最小值

下面介绍按值查找的算法思路：
从首元结点出发，逐个将结点的值与给定值做比较，若有结点值相等，则返回首次找到的值相等的结点的储存位置；若到尾结点都没有找到，返回0。

按值查找算法实现

//*L：头指针
//e：值
int getElem(LinkList *L, ElemType e)
{
	int i=0;
	LNode *p = (*L)->next;
	while (p!=NULL&&p->data!=e)
	{
		p = p->next;
		i++;
	}
	if(p!=NULL)return(i);
	else return ERROR;
}

2.5单链表的插入

在链表中第i个位置之前插入数据元素e，即插入到结点ai-i和ai之间。

  1. 查找第i-1个结点的地址，并使工作指针p指向第i-1个结点的地址;
  2. 生成一个数据域为e的新结点*s；
  3. 使新结点s的指针域指向结点ai；
  4. 使结点*p的指针域指向新结点s；
    在这里插入图片描述
    插入算法实现
int ListInsert(LinkList *L,int i ,ElemType e)
{
	LNode *p,*s; 
	p = *L;
	int j = 0;
	while (p && j<i-1) //寻找第i-1个结点
	    {
	    p = p->next;
	    j++;
	    }
	if (!p || j >i)
	    return ERROR;  //第i个元素不存在
	
	s = (LNode *)malloc(sizeof(LNode)); //生成新的结点
	s->data = e;
	s->next = p->next;  //将p的后继结点赋值给s的后继
	p->next = s;  //将s赋值给p的后继
	return OK;
}

如果表中有n个结点，则插入操作中合法的插入位置有n+1个，即1≤i≤n+1。当i=n+1时，新结点则插在链表尾部。

2.6单链表的删除

删除单链表上第i个结点ai。

为了删除单向链表中的某个结点，首先要找到待删除结点的前趋结点，然后将此前趋结点的指针域去指向待删除结点的后继结点（p->next=q->next)，最后释放被删除结点所占的存储空间。

  1. 查找第i-1个结点的地址，并使工作指针p指向第i-1个结点的地址;
  2. 将q指向被删除的第i个结点；
  3. 使p的指针域指向被删除结点的直接后继；
  4. 释放被删除的结点的空间；
    在这里插入图片描述
    删除算法实现
int ListDelete(LinkList *L,int i ,ElemType *e)
{
	int j=0;
	LNode *p,*q;
	p = *L;
	
	while(p->next && j <i-1)//寻找第i-1个结点，当1<=i<=n时是合法的。
	    {               //当i=n+1时，虽然被删结点不存在，但其前驱结点存在，是尾结点
	    p = p->next;   
	    ++j;
	    }
	if(!(p->next) || j>i-1)//前者表明p指针已指向最后结点；后者表明要删除头结点
	    return ERROR;
	q = p->next;//用q指向将要删除的结点
	p->next = q->next;//删除q指针指向的结点
	*e = q->data;
	free(q);//释放删除结点的存储空间
	return OK;
}

删除算法中的循环条件(p->next&&j<i-1)和插入算法中的循环条件(p&&(j<i−1))是有所区别的。
因为插入操作中合法的插入位置有n+1个，而删除操作中合法的删除位置只有n个，如果使用与插入操作相同的循环条件，则会出现引用空指针的情况，使删除操作失败。

2.7主函数演示

#include <stdio.h>
#include <stdlib.h>

#define OK 0
#define ERROR -1

int main()
{
	LinkList L; //头指针L	
	int result; //函数结果 
	int elemNum; //结点存储位置 
	ElemType elemValue; //结点值 
	
	//创建并遍历链表 
	printf("enter the linklist length you create:");
	scanf("%d", &elemNum);
	result = CreateListTail(&L, elemNum);
	printf("print linklist elem data:\n");
	result = DisplayList(&L);
	//按值查找结点
	printf("please enter a value you want to get:"); 
	scanf("%d", &elemNum);
	printf("the num is: %d\n", getElem(&L, elemNum));
	//插入结点，然后遍历链表 
	printf("to insert a new elem, please enter its num and value :"); 
	scanf("%d %d", &elemNum, &elemValue);
	result = ListInsert(&L, elemNum, elemValue);
	printf("print refreshed linklist elem data:\n");
	result = DisplayList(&L);
	//删除结点，然后遍历链表 
	printf("to delete a elem, please enter its num: "); 
	scanf("%d", &elemNum);
	result = ListDelete(&L, elemNum, &elemValue);
	printf("the deleted elem's value is %d.\n", elemValue);
	printf("print refreshed linklist elem data:\n");	
	result = DisplayList(&L);
	 
	return 0;
 }

案例演示：
创建长度为5的链表，输入各个结点值并打印；查找值为2的结点；插入新结点并重新打印；删除已插入的结点并重新打印。
在这里插入图片描述

更新日志

2020-4-26 首次发布
2022-8-1 正常维护
2025-9-7 错误修正

# 链表 # 算法 # c语言
Logo
乐奇 Rokid 开放社区

更多推荐

cover

小钱袋：说一句「午饭十八块五」，账单就记录到Rokid AI眼镜上啦

avatar 乐奇 Rokid 开放社区
cover

从“尝鲜“到“离不开“，华为AI眼镜这三个功能才是真刚需

avatar 乐奇 Rokid 开放社区
cover

基于Rokid AIUI实现眼镜上的倒数日

avatar 乐奇 Rokid 开放社区