如何学精链表？

我们存储很多数的时候，通常使用数组，但是数组不够灵活。

哦？为什么说不灵活？

我们如果要在一个数组前面或者中间插入一个数，就会很麻烦。

假设我们有一个数组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;
}