1.单链表：
在顺序表中，用一组地址连续的存储单元来一次存放线性表的结点，因此结点的逻辑顺序与物理顺序是一致的。但链表却不同，链表是用一组任意的存储单元来存放 线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置上。因此，链表中结点的逻辑顺序与物理顺序不一定相同。为了正确表示节点间的逻辑关系，必须在存储线性表的每个数据元素的同时，存储指示其后继结点的地址信息，这两部分信息共同构成了单链表结点的结构，如下图:
结点包括两个域，数据域用来存放结点的值，指针域用来存储数据元素的直接后继的地址（或位置）。线性表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序连接在一起的。由于此线性表的每个节点只有一个next指针域，故将这种链表叫做单链表。
由于单链表中的每一个结点除了第一个节点外，它们的存储地址存放在其前驱结点的指针域中，由于第一个节点无前驱，所以应该设一个头指针指向第一个节点，本文中设置了first指针指向第一个结点。单链表中的最后一个节点无直接后继，所以指定单链表的最后一个结点的指针域为"空"（NULL）。
一般情况下，使用链表，只关心链表中结点的逻辑顺序，并不关心每个结点的实际存储位置，因此通常用箭头来表示链域中的指针，于是链表就可以更直观地画成用箭头链接起来的结点序列，如图：
有时候，为了操作的统一方便，可以在单链表的第一个结点前附设一个头结点，头结点的数据域可以存储一些关于线性表的长度等附加信息，也可以不存储任何信息，对头结点的数据域无特别规定，而头结点的指针域用来存储指向第一个结点的指针（即第一个结点的存储位置）。如果线性表为空，则头结点的指针域为"空"。如图所示：
2.单链表操作：
头插过程：
头插的方式如上图所示。采用头插法得到的单链表的逻辑顺序与输入元素顺序相反，亦称头插法为逆序建表法。在这只介绍头插法的示意图，对于尾插、头删、尾删、可以参考《数据结构----用C语言描述》（耿国华主编）这本书。下面的代码中，实现了头插、尾插、头删、尾删，读者可以仔细研究研究。（本文所编写的代码是在VS2013编译环境下运行的）
3.运行代码：
Linklist.h文件包括各个操作函数的声明以及包含的头文件，test.c包含了测试代码，Linklist.c文件里主要是各个操作函数的具体实现。
1 //Linklist.h 2 #pragma once 3 #include4 #include 5 #include 6 7 typedef int LDataType; 8 typedef struct Linklist 9 {10 LDataType data;11 struct Linklist *next;12 }Linklist, *pLinklist;13 14 //接口函数15 pLinklist BuyNewNode(LDataType data);//动态生成新节点16 void InitLinklist(pLinklist *pL);//初始化单链表17 void PushBackLinklist(pLinklist *pL, LDataType data);//尾插18 void PushFrontLinklist(pLinklist *pL, LDataType data);//头插19 void PopBackLinklist(pLinklist *pL);//尾删20 void PopFrontLinklist(pLinklist *pL);//头删21 void PrintLinklist(Linklist *pL);//打印单链表22 pLinklist FindLinklist(pLinklist *pL, LDataType data);//查找指定元素,返回指定元素的位置23 void InsertLinklist(pLinklist *pL, pLinklist p, LDataType data);//指定位置插入24 void RemoveLinklist(pLinklist *pL, LDataType data);//删除第一个指定元素25 void RemoveAllLinklist(pLinklist *pL, LDataType data);//删除所有的指定元素26 int IsEmptyLinklist(pLinklist pL);//判断链表是否为空，为空返回1；不为空返回0；27 void DestoryLinklist(pLinklist *pL);//销毁单链表
1 //Linklist.c 2 #include"Linklist.h" 3 pLinklist BuyNewNode(LDataType data)//生成新节点 4 { 5 pLinklist NewNode = (pLinklist)malloc(sizeof(Linklist)); 6 if (NewNode == NULL) 7 { 8 printf("动态开辟内存空间失败\n"); 9 return; 10 } 11 NewNode->data = data; 12 NewNode->next = NULL; 13 return NewNode; 14 } 15 void InitLinklist(pLinklist *pL)//初始化 16 { 17 assert(pL != NULL); 18 (*pL) = NULL; 19 } 20 void PushBackLinklist(pLinklist *pL, LDataType data)//尾插 21 { 22 assert(pL != NULL); 23 pLinklist NewNode = BuyNewNode(data); 24 if (*pL == NULL) 25 { 26 *pL = NewNode; 27 return; 28 } 29 pLinklist cur = *pL; 30 while (cur->next) 31 { 32 cur = cur->next; 33 } 34 cur->next = NewNode; 35 } 36 void PushFrontLinklist(pLinklist *pL, LDataType data)//头插 37 { 38 assert(pL != NULL); 39 pLinklist NewNode = BuyNewNode(data); 40 if (*pL == NULL) 41 { 42 *pL = NewNode; 43 return; 44 } 45 NewNode->next = *pL; 46 *pL = NewNode; 47 } 48 int IsEmptyLinklist(pLinklist pL)//判断是否为空链表 49 { 50 if (pL == NULL) 51 return 1; 52 return 0; 53 } 54 void PopBackLinklist(pLinklist *pL)//尾删 55 { 56 assert(pL != NULL); 57 if (IsEmptyLinklist(*pL))//链表为空，没有节点 58 { 59 printf("链表为空，删除操作失败\n"); 60 return; 61 } 62 pLinklist cur = *pL; 63 pLinklist pre = NULL;//保存cur的前一个节点 64 if (cur->next == NULL)//有一个节点 65 { 66 *pL = NULL; 67 free(cur); 68 cur = NULL; 69 return; 70 } 71 while (cur->next) 72 { 73 pre = cur; 74 cur = cur->next; 75 } 76 pre->next = NULL; 77 free(cur); 78 cur = NULL; 79 } 80 void PopFrontLinklist(pLinklist *pL)//头删 81 { 82 assert(pL != NULL); 83 if (*pL == NULL) 84 { 85 printf("链表为空，删除操作失败\n"); 86 return; 87 } 88 pLinklist cur = *pL; 89 *pL = cur->next; 90 free(cur); 91 cur = NULL; 92 } 93 pLinklist FindLinklist(pLinklist *pL, LDataType data)//查找指定元素,返回指定元素的位置 94 { 95 assert(pL != NULL); 96 pLinklist cur = *pL; 97 while (cur) 98 { 99 if (cur->data == data)100 {101 return cur;102 }103 cur = cur->next;104 }105 return NULL;106 }107 void InsertLinklist(pLinklist *pL, pLinklist p, LDataType data)//指定位置前面插入108 {109 assert(pL != NULL);110 pLinklist NewNode = BuyNewNode(data);111 pLinklist cur = *pL;112 while (cur->next != p)113 {114 cur = cur->next;115 }116 NewNode->next = p;117 cur->next = NewNode;118 }119 void RemoveLinklist(pLinklist *pL, LDataType data)//删除第一个指定元素120 {121 assert(pL != NULL);122 pLinklist cur = NULL;123 pLinklist p = *pL;124 pLinklist pre = NULL;125 cur = FindLinklist(pL, data);//找到要删除的指定元素126 if (cur == NULL)127 {128 printf("没找到要删除的指定元素，删除失败\n");129 return;130 }131 if (*pL == cur)//位于第一个节点132 {133 *pL= cur->next;134 free(cur);135 cur = NULL;136 return;137 }138 while (p!= cur)139 {140 pre = p;141 p = p->next;142 }143 pre->next = cur->next;144 free(cur);145 cur = NULL;146 }147 void RemoveAllLinklist(pLinklist *pL, LDataType data)//删除所有的指定元素148 {149 assert(pL != NULL);150 pLinklist cur = NULL;151 pLinklist p = *pL;152 pLinklist pre = *pL;153 while (p)154 {155 156 if (p->data == data && (*pL) == p)157 {158 pre = p;159 p = p->next;160 *pL = p;161 free(pre);162 pre = NULL;163 }164 else if (p->data == data)165 {166 cur = p;167 p = p->next;168 pre->next = p;169 free(cur);170 cur = NULL;171 }172 else173 {174 pre = p;175 p = p->next;176 }177 }178 179 }180 void PrintLinklist(Linklist *pL)//打印单链表181 {182 pLinklist cur = pL;183 while (cur)184 {185 printf("%d-->", cur->data);186 cur = cur->next;187 }188 printf("NULL\n");189 }190 void DestoryLinklist(pLinklist *pL)//销毁单链表，放置内存溢出191 {192 assert(pL != NULL);193 pLinklist cur = *pL;194 pLinklist pre = NULL;//保存cur的前一个节点195 if (*pL == NULL)196 {197 printf("链表为空\n");198 return;199 }200 if (cur->next == NULL)//只有一个节点201 {202 *pL = NULL;203 free(cur);204 cur = NULL;205 return;206 }207 while (cur)208 {209 pre = cur;210 cur = cur->next;211 free(pre);212 pre = NULL;213 }214 } 1 //test.c测试函数 2 #include"Linklist.h" 3 4 void test() 5 { 6 pLinklist cur = NULL;//用来接收FindLinklist的返回值 7 Linklist *first = NULL; 8 InitLinklist(&first);//初始化 9 //PushBackLinklist(&first, 1);//尾插元素10 //PushBackLinklist(&first, 2);11 //PushBackLinklist(&first, 3);12 //PushBackLinklist(&first, 4);13 //PushBackLinklist(&first, 5);14 //PrintLinklist(first);//打印单链表15 PushFrontLinklist(&first, 6);//头插元素16 PushFrontLinklist(&first, 7);17 PushFrontLinklist(&first, 8);18 PushFrontLinklist(&first, 9);19 PushFrontLinklist(&first, 10);20 //PopBackLinklist(&first);//尾删一个节点21 //PopFrontLinklist(&first);//头删一个节点22 //PrintLinklist(first);//打印单链表23 //DestoryLinklist(&first);24 //cur = FindLinklist(&first, 8);25 //InsertLinklist(&first, cur, 11);26 //printf("在8前面插入11得:");27 //PrintLinklist(first);//打印单链表28 //printf("删除11得:");29 //RemoveLinklist(&first, 11);30 //PrintLinklist(first);31 PushFrontLinklist(&first, 7);32 PushFrontLinklist(&first, 7);33 //RemoveLinklist(&first, 7);34 RemoveAllLinklist(&first, 7);35 PrintLinklist(first);36 37 //RemoveAllLinklist(&first, 7);//删除所有的738 }39 int main()40 {41 test();42 system("pause");43 return 0;44 } 4.尾插法建立单链表如下图：
测试图： 运行图：
5.头插法建立单链表如下图：
测试图： 运行图：
6.头删和尾删一个结点：
测试图： 运行图：
7.在指定位置插入元素：
测试图： 运行图：
除这几个操作外，还有删除指定元素RemoveLinklist（删除第一个找到的指定元素），删除所有的指定元素RemoveAllLinklist。因为本文中单链表的结点是动态开辟的，因此还要实现销毁函数DestoryLinklist，防止内存泄漏。