前面所讲的线性表的顺序存储结构，它最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以在内存中未被占用的任意位置。
比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）。
一、链式存储结构定义
我们把存储数据元素的域称为数据域。
把存储直接后继位置的域称为指针域。
指针域中存储的信息称为指针或者链。
这两部分信息组成数据元素称为存储映像，称为结点（Node）
n个结点链接成一个链表，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
二、单链表存储结构
单链表图例：
空链表图例：
我们在C语言中可以用结构指针来描述单链表。
typedef struct Node
{ElemType data; // 数据域struct Node *Next; // 指针域，指针指向的是下一个结点
}Node;
typedef struct Node *LinkList;
问题：
如果 p->data = ai ,那么 p->next->data = ?
答案：
p->next->data = ai+1。
三、单链表的读取
在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。在单链表中，由于第i个元素到底在哪里？我们压根儿没有办法一开始就知道，必须得从第一个结点开始挨个找。
获取链表第i个数据的算法思路：
- 声明一个结点p指向链表第一个结点，初始化 j 从1开始；
- 当 j<i 时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j+1；
- 若到链表末尾p为空，则说明第 i 个元素不存在。
- 若查找成功，返回结点 p 的数据。
代码实现：
int GetElem LinkList L, int i, ElemType *e )
{int j;LinkList p;p = L->next;j = 1;while p && j<i ){p = p->next;++j;}if !p || j>i ){return 0;} e = p->data;return 1;
}
由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需要遍历，当i=n时则遍历n-1次才可以。因此最坏的情况的时间复杂度为On)。
由于单链表的结构中没有定义表长，所以不能实现知道要循环多少次，因此不方便使用for来控制循环。
其核心思想叫做“工作指针后移”，这其实也是很多算法的常用技术。
四、单链表的插入
我们思考后发现，我们根本用不着惊动其他结点，只需要让s->next 和 p->next 的指针做一点改变。（这里的指针通通看成一个整体，你要把它想象成指向这个结点的名字）
- s->next = p-next;
- p->next = s;
我们通过图片来解读一下这两句代码：
单链表第 i 个数据插入结点的算法思路：
- 声明一个结点p指向链表头结点，初始化 j 从1开始；
- 当 j<i 时，就遍历链表，让 p 指针向后移动，不断指向下一个结点，j 累加1；
- 若到达链表尾部 p 为空，则说明第 i 个元素不存在；
- 否则查找成功，在系统中生成一个空节点 s ；
- 将数据元素 e 赋值给 s->data ;
- 单链表的插入刚才两个标准语句；
代码实现：
int ListInsert LinkList L, int i, ElemType e )
{LinkList p, s;p = L;int j = 1;while p && j<i ){p = p->next;++j;}if !p || j>i ){return 0;}s = LinkList)mallocsizeofNode)); // 生成新的结点s->data = e;s->next = p-next;p->next = s;return 1;
}
五、单链表的删除
假设元素a2的结点为q，要实现结点p删除单链表的操作，其实就是将它的前继结点的指针绕过指向后继结点即可。
实现的步骤就是：
- p->next = p->next->next;
单链表第i个数据删除结点的算法思路：
- 声明结点p指向链表的第一个结点，初始化j=1；
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
- 若到链表末尾p为空，则说明第i个元素不存在；
- 否则查找成功，将欲删除结点p->next赋值给q；
- 单链表的删除标准语句p->next = q->next；
- 将q结点中的数据赋值给e，作为返回；
- 释放q结点。
实现代码：
int ListDelete LinkList L, int i)
{LinkList p,q;int j,e;p = L;j = 1;while p->next && j<i ){p = p->next;++j;}if !p->next) || j>i ){return 0;}q = p_next;e = q->data;p->next = q->next;freeq);return e;
}
单链表，我们只需要在第一次时，找到第i个位置的指针，此时为On)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O1)。
显然，对于插入或者删除数据越频繁的操作，单链表的效率优势就是越明显。