定义

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
示意图：

声明单链表

typedef struct LNode  
{
ElemType data;           //数据域
struct LNode *next;//指针域，指向后继结点
} LinkNode;//声明单链表结点类型
1
2
3
4
5

注意：本文章讨论的单链表是带头结点的单链表。
增加头结点的优点如下：
1.单链表中首结点的插入和删除操作与其他结点一致，无需进行特殊处理。
2.无论单链表是否为空都有一个头结点，因此统一了空表和非空表的处理过程。

基本运算

头插法建立单链表

void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立单链表
{
LinkNode *s;
L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
L->next=NULL;
for (int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
s->data=a[i];
s->next=L->next;//将结点s插在原开始结点之前,头结点之后
L->next=s;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

该运算依次从数组a中读取数据，生成一个新的结点，将该数据储放到新结点的数据域，然后将其插入到当前链表的表头（即头结点之后），直到所有的数据读完为止。
例如：数组 a={ 1,2,3,4 }，使用头插法得到的链表顺序为 4，3，2，1。
插入操作如下：

s->next=L->next;
L->next=s;
1
2

首先修改s结点的后继指针next，使其指向头节点L的后继指针next所指结点，然后修改头结点的后继指针next，使其指向s结点。

本算法的时间复杂度为O（n）

尾插法建立单链表

void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立单链表
{
LinkNode *s,*r;
L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
L->next=NULL;
r=L;//r始终指向终端结点,开始时指向头结点
for (int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
s->data=a[i];
r->next=s;//将结点s插入结点r之后
r=s;
}
r->next=NULL;//终端结点next域置为NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

该运算依次从数组a中读取数据，生成一个新的结点，将该数据储放到新结点的数据域，然后将其插入到当前链表的表尾，直到所有的数据读完为止。其过程是设置一个指针r，让它始终指向当前链表的尾结点，每次插入一个新结点后，让r指向这个新结点，所有元素插入完后，将r所指结点(尾结点)的next域设置为NULL。

例如：数组 a={ 1,2,3,4 }，使用尾插法得到的链表顺序为 1，2，3，4。

插入操作如下：

r->next=s;
r=s;
1
2

首先修改r结点的后继指针next，使其指向s结点，最后让r指向s结点。
本算法的时间复杂度为O（n）

初始化单链表

void InitList(LinkNode *&L)
{
L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
L->next=NULL;                          //后续节点置空
}
1
2
3
4
5

该运算建立一个空的单链表，其过程是创建一个头结点，并将其next域置为NULL。
本算法的时间复杂度为O（1）

销毁单链表

void DestroyList(LinkNode *&L)
{
LinkNode *pre=L,*p=pre->next;
while (p!=NULL)
{free(pre);
pre=p;
p=pre->next;
}
free(pre);//此时p为NULL,pre指向尾结点,释放它
}
1
2
3
4
5
6
7
8
9
10

该运算释放单链表L占用的内存空间，即逐一释放全部结点存储空间。设置p,pre两个指针指向两个相邻的结点，初始时pre指向头节点，p指向首结点(链表第一个元素)，当p不为NULL执行循环:先释放pre，然后pre，p同步后移一个结点。循环结束时，pre指向尾结点，再将其释放。
本算法的时间复杂度为O（n）

判断单链表是否为空表

bool ListEmpty(LinkNode *L)
{
return(L->next==NULL);
}
1
2
3
4

该运算判断单链表是否为空表，当头结点的next域为NULL时，表示链表为空，返回1，否则返回0。
本算法的时间复杂度为O（1）

求单链表长度

int ListLength(LinkNode *L)
{
LinkNode *p=L;int i=0;
while (p->next!=NULL)
{i++;
p=p->next;
}
return(i);
}
1
2
3
4
5
6
7
8
9

该运算返回链表L中数据元素的个数，设置指针p(初始指向头节点)，i(初始值为0）用来记录链表中结点的个数，遍历链表，当p不为NULL时执行循环:i加1，p指向下一个结点。循环结束后返回i。
本算法的时间复杂度为O（n）

输出单链表

void DispList(LinkNode *L)
{
LinkNode *p=L->next;
while (p!=NULL)
{printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
1
2
3
4
5
6
7
8
9

该运算逐一输出各结点的data域值，设置指针p(初始指向首结点)，p不为NULL执行循环:输出当前结点的数据域，p指向下一个结点。
本算法的时间复杂度为O（n）

求单链表中某个位置数据元素的值

bool GetElem(LinkNode *L,int i,ElemType &e)
{
int j=0;
LinkNode *p=L;
if (i<=0) 
    return false;//i错误返回假
while (j<i && p!=NULL)
{j++;
p=p->next;
}
if (p==NULL)//不存在第i个数据结点
return false;
else//存在第i个数据结点
{e=p->data;
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

该运算在单链表L中从开始找到第i个结点，如果存在第i个结点则将其data域值赋给e。设置指针p(初始指向头结点)，j(初始值为0)用来记录遍历过的结点个数，当j<i且p不为空时循环:j+1，p指向下一个结点。循环结束时有两种情况:如果p为NULL，表示单链表L中没有第i个结点(参数错误)，返回false;如果p不为NULL，表示找到第i个结点，将其data域值赋给e并返回true。
本算法的时间复杂度为O（n）

按元素的值查找

int LocateElem(LinkNode *L,ElemType e)
{
LinkNode *p=L->next;
int i=1;
while (p!=NULL && p->data!=e)
{p=p->next;
i++;
}
if (p==NULL)
return(0);
else
return(i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

该运算在单链表中从头开始找到第一个data域值与e相等的结点，如果存在这样的结点，则返回逻辑序号，否则返回0。设置指针p(初始指向首结点)，i(初始值为1)，当p不为NULL且p结点的data域值不等于e时执行循环:p指向下一个结点，i加1。循环结束时有两种情况:如果p=NULL,表示不存在值为e的结点，返回0;否则表示存在值为e的结点，返回其逻辑序号i。
本算法的时间复杂度为O（n）

插入数据元素

bool ListInsert(LinkNode *&L,int i,ElemType e)
{
int j=0;
LinkNode *p=L,*s;
if (i<=0) 
   return false;//i错误返回假
while (j<i-1 && p!=NULL)//查找第i-1个结点p
{j++;
p=p->next;
}
if (p==NULL)//未找到位序为i-1的结点
return false;
else//找到位序为i-1的结点*p
{s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点*s
s->data=e;
s->next=p->next;//将s结点插入到结点p之后
p->next=s;
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

该运算在单链表第i个结点前插入值为e的结点。
实现过程是先在单链表L中找到第i-1个结点，用p指向它。如果存在这样的结点，将值为e的结点(指针s所指结点)插入到p结点的后面。设置指针p(初始指向头结点)，i(初始值为0)，当j<i-1且p为NULL时执行循环:j加1，p指向下一个结点。循环结束时有两种情况:如果p为NULL，表示未找到第i-1个元素(参数错误)，返回false;否则表示找到第i-1个结点，创建新结点s并将其data域值置为e，将结点s插入到结点p之后，最后返回true。
插入操作如下：

s->next=p->next;
p->next=s;
1
2

此处插入操作与头插法建立单链表的插入操作相同(头插法建立单链表时的插入操作相当于把s结点插入到头结点L之后),此处是把s结点插入到p结点之后。
本算法的时间复杂度为O（n）
动画演示：

删除数据元素

bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
int j=0;
LinkNode *p=L,*q;
if (i<=0) 
   return false;//i错误返回假
while (j<i-1 && p!=NULL)//查找第i-1个结点
{j++;
p=p->next;
}
if (p==NULL)//未找到位序为i-1的结点
return false;
else//找到位序为i-1的结点p
{q=p->next;//q指向要删除的结点
if (q==NULL) 
return false;//若不存在第i个结点,返回false
e=q->data;
p->next=q->next;//从单链表中删除q结点
free(q);//释放q结点
return true;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

该运算删除单链表L中第i个结点，并将其data域值赋给e。实现过程是先在单链表中找到第i-1个结点，用p指向它。如果存在这样的结点，且存在后继结点(q所指结点)，则删除q所指结点。设置指针p(初始指向头结点)，j(初始值为0)，当j<i-1执行循环:j加1，p指向下一个结点。当循环结束时有两种情况:如果p为NULL,表示未找到第i-1个结点(参数错误)，返回false;否则表示找到第i-1个结点，用q指向第i个结点，如果q为NULL,则表示不存在第i个结点(参数错误)返回false，如果q不为NULL,则表示存在第i个结点，删除q结点，返回true。
删除操作如下：

p->next=q->next;//从单链表中删除q结点
1

直接修改p结点的后继指针next，使其指向q结点的后继指针next所指的结点。
本算法的时间复杂度为O（n）
动画演示：

完整代码

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct LNode  
{
ElemType data;
struct LNode *next;//指向后继结点
} LinkNode;//声明单链表结点类型
void CreateListF(LinkNode *&L,ElemType a[],int n)
//头插法建立单链表
{
LinkNode *s;
L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
L->next=NULL;
for (int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
s->data=a[i];
s->next=L->next;//将结点s插在原开始结点之前,头结点之后
L->next=s;
}
}
void CreateListR(LinkNode *&L,ElemType a[],int n)
//尾插法建立单链表
{
LinkNode *s,*r;
L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
L->next=NULL;
r=L;//r始终指向终端结点,开始时指向头结点
for (int i=0;i<n;i++)
{
s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点s
s->data=a[i];
r->next=s;//将结点s插入结点r之后
r=s;
}
r->next=NULL;//终端结点next域置为NULL
}
void InitList(LinkNode *&L)
{
L=(LinkNode *)malloc(sizeof(LinkNode));  //创建头结点
L->next=NULL;
}
void DestroyList(LinkNode *&L)
{
LinkNode *pre=L,*p=pre->next;
while (p!=NULL)
{free(pre);
pre=p;
p=pre->next;
}
free(pre);//此时p为NULL,pre指向尾结点,释放它
}
bool ListEmpty(LinkNode *L)
{
return(L->next==NULL);
}
int ListLength(LinkNode *L)
{
LinkNode *p=L;int i=0;
while (p->next!=NULL)
{i++;
p=p->next;
}
return(i);
}
void DispList(LinkNode *L)
{
LinkNode *p=L->next;
while (p!=NULL)
{printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
bool GetElem(LinkNode *L,int i,ElemType &e)
{
int j=0;
LinkNode *p=L;
if (i<=0) return false;//i错误返回假
while (j<i && p!=NULL)
{j++;
p=p->next;
}
if (p==NULL)//不存在第i个数据结点
return false;
else//存在第i个数据结点
{e=p->data;
return true;
}
}
int LocateElem(LinkNode *L,ElemType e)
{
LinkNode *p=L->next;
int n=1;
while (p!=NULL && p->data!=e)
{p=p->next;
n++;
}
if (p==NULL)
return(0);
else
return(n);
}
bool ListInsert(LinkNode *&L,int i,ElemType e)
{
int j=0;
LinkNode *p=L,*s;
if (i<=0) 
   return false;//i错误返回假
while (j<i-1 && p!=NULL)//查找第i-1个结点p
{j++;
p=p->next;
}
if (p==NULL)//未找到位序为i-1的结点
return false;
else//找到位序为i-1的结点*p
{s=(LinkNode *)malloc(sizeof(LinkNode));//创建新结点*s
s->data=e;
s->next=p->next;//将s结点插入到结点p之后
p->next=s;
return true;
}
}
bool ListDelete(LinkNode *&L,int i,ElemType &e)
{
int j=0;
LinkNode *p=L,*q;
if (i<=0) 
   return false;//i错误返回假
while (j<i-1 && p!=NULL)//查找第i-1个结点
{j++;
p=p->next;
}
if (p==NULL)//未找到位序为i-1的结点
return false;
else//找到位序为i-1的结点p
{q=p->next;//q指向要删除的结点
if (q==NULL) 
return false;//若不存在第i个结点,返回false
e=q->data;
p->next=q->next;//从单链表中删除q结点
free(q);//释放q结点
return true;
}
}
int main()
{
LinkNode *L;
ElemType e;
ElemType a[]={1,2,3,4};
CreateListF(L,a,4);        //尾插法建立链表 
printf("尾插法所得顺序为: ");
DispList(L);
DestroyList(L);
CreateListR(L,a,4);        //头插法建立链表 
printf("头插法所得顺序为：");
DispList(L);
printf("链表的长度为:%d\n",ListLength(L));
ListInsert(L,4,5);          //在链表第四个元素前插入5 
printf("插入一个元素后链表的元素为:");
DispList(L);
ListDelete(L,1,e);          //删除链表中第一个元素，并将它的值赋给e 
printf("删除的元素为:%d\n",e);
printf("删除一个元素后链表的元素为:");
DispList(L);
printf("当前链表是否为空:%d\n",ListEmpty(L));
GetElem(L,1,e);
printf("链表第一个元素为:%d\n",e);
printf("值为2的元素在链表中的位置为:%d\n",LocateElem(L,2));
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

参考资料：
李春葆《数据结构教程》（第五版）
维基百科