链式存储结构

用一组任意的存储单元存储线性表数据元素，这组存储单元可以存在内存中未被占用的任意位置；每个元素需要两个位置，一个存储元素本身，一个存储它后继元素的存储地址（指针）
数据域：存储数据元素信息的域；
指针域：存储直接后继位置的域；
指针/链：指针域中存储的信息
存储映像/结点（node）：数据域和指针域这两部分信息组成的数据元素
链式存储结构：n个结点连接成一个链表
单链表：链表中每个结点中只包含一个指针域

头指针：链表中第一个结点的存储位置
最后一个结点指针为空

头结点的数据域一般不存储任何信息
头指针
—— 指指向链表第一个结点的指针，若链表有头结点，则是指向头结点的指针
在头结点之前
—— 头指针具有标志作用，所以常用头指针冠以链表的名字（指针变量的名字）
—— 无论链表是否为空，头指针均不为空
—— 头指针是链表的必要元素
头结点
—— 为了操作统一和方便而设立，放在第一个元素的结点之前，其数据域一般无
意义（但也可以用来存放链表的长度）
—— 有了头结点，对第一个元素节点前插入结点和删除第一个结点操作与其他结
点的操作就统一了
——头结点不一定是链表的必须要素

用结构指针来描述单链表

typedef struct Node
{
	ElemType data;//数据域
	struct Node* Next;//指针域
}Node;
Typedef struct Node* LinkList

Typedef struct Node LinkList 将Node取别名为LinkList
结点由存放数据元素的数据域和存放后继结点的地址指针组成

假设P是指向线性表第i个元素的指针，则该结点ai的数据域为p->data
指针域为p->next,因为p->next是一个指针，它指向第i+1个元素ai+1
因此，如果p->data=ai,那么p->next->data=ai+1

单链表元素读取

链表元素不像顺序存储线性表通过位置计算可以得到，需要一个一个找

时间复杂度为O（n）;核心思想：“工作指针后移”

单链表元素插入O(n)

单链表元素删除O(n)

以上操作代码链接

小结

如果我们想从第i个位置开始，插入连续10个元素，
对顺序存储结构意味着，每次插入都需要移动n-i个位置,所以每次都是O(n);
而单链表，只需要在第一次找到第i个位置的指针，此时时间复杂度为O(n),
接下来只是简单的赋值移动指针而已，时间复杂度都是O(1)
因此对于频繁插入或删除数据来说，单链表效率更高。