导语：
无论是顺序存储结构还是链式存储结构，在内存中进行存放元素的时候，不仅需要存放该元素的相关信息，还需要存放该元素和其他元素之间的关系，而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系，不需要额外的信息去表达元素和元素之间的关系，而对于链式存储这种非顺序存储的结构，需要额外附加指针去表示这种关系。
单链表：
每个结点除了存放数据元素外，还要存储指向下一个节点的指针。
单链表的特点：
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针
定义：
typedef struct LNode { int data; struct LNode* next;//指针指向下一个节点，指针的类型为节点类型； }*LinkNode;//声明*LinkNode为结构体指针类型
除了上述这种方法外，我们还可以先先声明LinkNode为结构体类型，在使用该类型的时候，将对应的变量定义为指针即可。
单链表分为带头结点和不带头结点，我们一般主要学习带头结点的。
初始化操作：
在所有的操作之前，我们首先需要建立一个空的单链表，那么首先需要做的就是分配头结点。
void InistLinkNode(LinkNode& L) { L = (LNode*)malloc(sizeof(LNode));//分配头结点 L->next = NULL; }
头插法：
“头插法”顾名思义就是将元素插入到头结点之后，插入一次好像和我们通常所讲的插入没什么区别，但多次这样插到头结点之后，也就是“第一个真正的节点”，那么是不是会产生一种现象，它最终的存储数据和我们所插入时的顺序是相反的。
void InsertLinkNode(LinkNode& L) { LNode* s; int x,Length; printf("请输入你要插入的元素个数："); scanf("%d", &Length); printf("请输入你要插入的元素：\n"); for (int j = 0; j < Length; j++) { s = (LNode*)malloc(sizeof(LNode));//每插入一个元素之前，都需要给它分配节点空间 scanf("%d", &x); s->data = x; s->next = L->next; L->next = s; } }
通过程序验证以下：
尾插法：
“尾插法”顾名思义就是将元素插入到表尾，也就是我们普通的插入，那么怎么要找到表尾的位置呢？在顺序表中，我们完全可以利用它顺序存储结构的天然特性，通过下标即可以找到，但是单链表是没有办法的，我们只有两种方式，要么循环遍历，要么尝试在表尾的地方做个标记。
那么那种方法是好的呢？
答案是第二种！循环遍历的方式，如果只插入一个元素看似没什么问题，但如果多次的重复遍历循环无疑增加了时间复杂度，这显然不是好的方法。
第二个方法就不存在时间复杂度的问题，只需要在表尾位置做个标记，使它永远指向表尾即可。
void TailInsertLinkNode(LinkNode& L) { LNode* s,*r; int x,Length; r = L;//r为表尾指针 printf("请输入你要插入的元素个数："); scanf("%d", &Length); printf("请输入你要插入的元素：\n"); for (int j = 0; j < Length; j++) { s = (LNode*)malloc(sizeof(LNode)); scanf("%d", &x); s->data = x; r->next = s; r = s;//s为当前的表尾指针，将他的值赋值给r----使r永远指向表尾 } printf("\n"); r->next = NULL; }
删除第i个元素：
既然要删除某个元素，那么首先我们需要保证这个元素是非NULL，其次，我们还需要保证它前面的那个节点也是非NULL，为什么呢？因为如果将该元素从链表中删除后，只有前面节点非NULL的情况下，才可以实现后续元素和前面子表的连接。
void DeleteLinkNode(LinkNode& L) { int x, j = 0,e; printf("请输入你要删除的元素位序：\n"); scanf("%d", &x); LNode*p = L; while (p != NULL && j < x - 1) {//寻找要删除元素前的元素 p = p->next; j++; } if (p == NULL) { printf("不存在我们要删除的元素！"); } if (p->next == NULL)//判断该要删除的节点是否为NULL { printf("不存在我们要删除的元素！"); } LNode* q = p->next;//q为我们要删除的节点 e = q->data; p->next = q->next; free(q);//需要及时的将删除了的元素空间进行释放 }
其他的基本操作都是很常规化的，这里就不单独的进行解释了，需要注意的点，我会在文章结尾部分的完整代码的注释中展出。
在第i个位置插入：
void IncreaseLinkNode(LinkNode& L) { printf("请输入你要插入的元素和位序：（元素和位序之间用逗号隔开）\n"); int x, j = 0, e; scanf("%d,%d",&e, &x); LNode* s = L, * r= (LNode*)malloc(sizeof(LNode)); while (j < x-1 && s != NULL) { j++; s = s->next; } r->data = e; r->next = s->next; s->next = r; }
如下所示的代码顺序不能发生改变，否则会出现无法和后面的节点；
r->next = s->next; s->next = r;
完整代码如下：
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> typedef struct LNode { int data; struct LNode* next; }*LinkNode; //初始化 void InistLinkNode(LinkNode& L) { L = (LNode*)malloc(sizeof(LNode));//分配头结点 L->next = NULL; } //头插法 void InsertLinkNode(LinkNode& L) { LNode* s; int x,Length; printf("请输入你要插入的元素个数："); scanf("%d", &Length); printf("请输入你要插入的元素：\n"); for (int j = 0; j < Length; j++) { s = (LNode*)malloc(sizeof(LNode)); scanf("%d", &x); s->data = x; s->next = L->next; L->next = s; } } //尾插法 void TailInsertLinkNode(LinkNode& L) { LNode* s,*r; int x,Length; r = L; printf("请输入你要插入的元素个数："); scanf("%d", &Length); printf("请输入你要插入的元素：\n"); for (int j = 0; j < Length; j++) { s = (LNode*)malloc(sizeof(LNode)); scanf("%d", &x); s->data = x; r->next = s; r = s; } printf("\n"); r->next = NULL; } //输出单链表 void PrintLinkNode(LinkNode& L) { LNode* s=L->next; printf("单链表元素如下：\n"); while (s != NULL) { printf("%d", s->data); s =s->next; } printf("\n"); } //求线性表长度 void lengthLinkNode(LinkNode& L) { LNode* s = L->next; int n=0; while (s != NULL) { n++; s = s->next; } printf("单链表长度为：%d",n); printf("\n"); } //取第i个元素 void GetElemLinkNode(LinkNode& L) { printf("请输入你要查找的元素位序：\n"); int i, j = 0; LNode* s=L; scanf("%d", &i); while (j < i && s != NULL) { j++; s = s->next; } if (s == NULL) { printf("不存在我们要查找的元素！"); } else { printf("元素位序为%d的元素是%d",i, s->data); } printf("\n"); } //删除第i个元素 void DeleteLinkNode(LinkNode& L) { int x, j = 0,e; printf("请输入你要删除的元素位序：\n"); scanf("%d", &x); LNode*p = L; while (p != NULL && j < x - 1) { p = p->next; j++; } if (p == NULL) { printf("不存在我们要删除的元素！"); } if (p->next == NULL) { printf("不存在我们要删除的元素！"); } LNode* q = p->next; e = q->data; p->next = q->next; free(q); } //在第i个位置插入 void IncreaseLinkNode(LinkNode& L) { printf("请输入你要插入的元素和位序：（元素和位序之间用逗号隔开）\n"); int x, j = 0, e; scanf("%d,%d",&e, &x); LNode* s = L, * r= (LNode*)malloc(sizeof(LNode)); while (j < x-1 && s != NULL) { j++; s = s->next; } r->data = e; r->next = s->next; s->next = r; } //查找位序 void SearchLinkNode(LinkNode &L) { int x,j=1; LNode* p=L->next; printf("请输入你要查找的元素:\n"); scanf("%d", &x); while (p != NULL && p->data != x) { p = p->next; j++; } if (p == NULL) { printf("您要查找的元素不存在！"); } else { printf("你要查找的元素%d的位序为%d", x, j); } } int main() { LinkNode L; InistLinkNode(L); /*InsertLinkNode(L);*/ TailInsertLinkNode(L); PrintLinkNode(L); lengthLinkNode(L); GetElemLinkNode(L); IncreaseLinkNode(L); PrintLinkNode(L); DeleteLinkNode(L); PrintLinkNode( L); SearchLinkNode(L); }
输出：
