我们存储很多数的时候，通常使用数组，但是数组不够灵活。
哦？为什么说不灵活？
我们如果要在一个数组前面或者中间插入一个数，就会很麻烦。
假设我们有一个数组a,里面是排序好的数字,我们要将7按大小顺序插入数组
我们就得把后面的数全都依次往后移一位，再将7放入。
这样如果后面的数非常多的话就会很耽误时间。
所以我们需要用到链表。
链表就是利用结构体和指针，在存储数据的同时，存储一个指向下一个结点的指针。
这样我们要插入数字的时候，只要修改下指针的指向，就可以快速的进行插入或取出之类的操作。
链表有很多种：
**单链表:**每个结点记录后继(图片演示的就是)
**双链表:**每个结点记录前驱和后继，它比单链多了个往前走的功能
**循环单链表:**将单链表的最后一个结点的后继指向第一个结点，形成一个环形结构
**循环双链表:**将双链表连成环形
…（还有几种就不一一列述了）
这里我们设计一个程序实现一下链表，首先输入四个按大小顺序排列的数字，然后再输入要插入的数字，
程序会输出插入后的排列
先上代码
#include <iostream>
using namespace std;
struct node {
int data;//存数据
node* next;//后继指针
};
int main()
{
int a;
node* head, * p, * q = NULL;
head = NULL;
for (int i = 1; i < 5; i++) {
//用指针p指向一个动态申请的node大小的空间
p = (node*)malloc(sizeof(node));
cin >> a;
//将数据存入当前结点(p指向的结点)
p->data = a;
p->next = NULL;
if (head == NULL)head = p;//如果是第一个结点，就将头指针指向当前结点
else q->next = p;//否则将上一个结点的后继指针指向当前结点
q = p;//将q指向当前结点
}
//插入数据
int b;
cin >> b;
node* t = head;//从链表头开始遍历
while (t != NULL) {
if (t->next->data > b) {
p = (node*)malloc(sizeof(node));
//将数据存入当前结点(p指向的结点)
p->data = b;
p->next = t->next;//将当前结点的后继指针指向下一结点
t->next = p;//将上一结点的后继指针指向当前结点
break;
}
t = t->next;//下一结点
}
//输出
t = head;//从链表头开始遍历
while (t != NULL) {
cout << t->data << endl;
t = t->next;//下一结点
}
//释放动态申请的空间(确保安全)
t = head;
while (t != NULL) {
node* current = t;//记录当前结点
t = t->next;//下一结点
free(current);
}
return 0;
}
代码不长，但是可能需要时间理解。
讲讲malloc函数，malloc函数的作用是动态分配内存。
每次输入数据前，我们就用p指向一个动态申请的新空间，然后存入数据。
程序的最后，我们用free()函数来释放动态申请的空间，这样可以让我们的程序更安全。
我们学习c语言和c++应该追求最大程度地优化，排除可能出现的问题。