顺序线性表的优点：方便存取（随机的），特点是物理位置和逻辑为主都是连续的（相邻）。但是也有不足，比如；前面的插入和删除算法，需要移动大量元素，浪费时间，那么链式线性表 (简称链表) 就能解决这个问题。
一般链表的存储方法
一组物理位置任意的存储单元来存放线性表的数据元素，当然物理位置可以连续，也可以不连续，或者离散的分配到内存中的任意位置上都是可以的。故链表的逻辑顺序和物理顺序不一定一样。
因为，链表的逻辑关系和物理关系没有必然联系，那么表示数据元素之间的逻辑映象就要使用指针，每一个存储数据元素的逻辑单元叫结点（node）。
结点里有两个部分，前面存储数据元素内容，叫数据域，后面部分存储结点的直接后继在内存的物理位置，叫指针域。那么就可以实现用指针（也叫链）把若干个结点的存储映象链接为表，就是链式线性表。
上面开始介绍的是最简单的链表，因为结点里只有一个指针域，也就是俗称的单链表（也叫线性链表）。
单链表可以由一个叫头指针的东东唯一确定，这个指针指向了链表（也就是直接指向第一个结点）。因此单链表可以用头指针的名字来命名。且最后一个结点指针指向NULL。
链表类别
1、实现的角度：动态链表，静态链表（类似顺序表的动态和静态存储）
2、链接方式的角度：单链表，双向链表，循环链表
单链表
单链表的头结点
一般是使用单链表的头指针指向链表的第一个结点，有的人还这样做，在第一个结点之前再加一个结点（不保存任何数据信息，只保存第一个结点的地址，有时也保存一些表的附加信息，如表长等），叫头结点（头结点是头结点，第一个结点是第一个结点）。那么此时，头指针指向了头结点。并且有无头结点都是可以的。链表还是那个链表，只不过表达有差异。
那么问题来了！为什么还要使用头结点？
作用是对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，
编程更方便。
描述动态单链表
有两种做法，一种是传统的动态链表结构，暨只定义结点的存储结构，使用4个字节的指针变量表示线性表。还有一种是直接采用结构体变量（类似顺序表）来表示线性表。
顾名思义，肯定是第二种方法比较方便。
先看传统存储动态单链表结构的操作
1 /************************************************************************/
2 /* 文件名称：ADT.h
3 /* 文件功能：动态单链表传统存储结构和常见操作
4 /* 作 者：dashuai
5 /* 备 注：以下算法，并没有考证是否全部都是最佳优化的，关于算法的优化后续研究
6 /************************************************************************/
7 #include
8 #include
9
10 //传统的单链表动态存储结构（带头指针）
11 typedef struct Node//Node标记可以省略，但如结构里声明了指向结构的指针，那么不能省略！
12 {
13 char data;//数据域
14 struct Node *next;//指针域
15 } Node, *LinkList;//LinkList是指向Node结构类型的指
16
17 /*
18 1、查找（按值）算法
19 找到第一个值等于value的结点，找到则返回存储位置
20 */
21 LinkList getElemByValue(LinkList L, char value);
22
23 /*
24 2、查找（按序号）算法
25 查找第i个元素，并用变量value返回值，否则返回提示，即使知道了序号，也必须使用指针顺次查访
26 */
27 void getElemByNum(LinkList L, int num, char *value);
28
29 /*
30 3、删除结点
31 删除元素，并用value返回值
32 */
33 void deleteList(LinkList L, int i, char *value);
34
35 /*
36 4、插入结点
37 在第i个位置之前插入结点e
38 */
39 void insertList(LinkList L, int i, char value);
40
41 /*
42 5、头插法建立单链表（逆序建表）
43 从一个空结点开始，逐个把 n 个结点插入到当前链表的表头
44 */
45 void createListByHead(LinkList *L, int n);
46
47 /*
48 6、尾插法建立单链表（顺序建表）
49 从一个空结点开始，逐个把 n 个结点插入到当前链表的表尾
50 */
51 void createListByTail(LinkList *L, int n);
52
53 /*
54 7、尾插法建立有序单链表（归并链表）
55 把两个有序（非递减）链表LA LB合并为一个新的有序（非递减）链表LC(空表)
56 要求：不需要额外申请结点空间来完成
57 */
58 void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC);
59
60 /*
61 8、销毁单链表
62 */
63 void destoryLinkList(LinkList *L);
64
65 /*
66 9、求表长，长度保存到头结点
67 */
68 void getLength(LinkList L);
69
70 /*
71 10、遍历单链表
72 */
73 void traversalList(LinkList L);
复制代码
C变量的随用随定义，可以确定C99之后新增加的，和c++一样，貌似一些编译器还不支持
复制代码
1 #include "ADT.h"
2
3 /*
4 1、查找（按值）算法
5 找到第一个值等于value的结点，找到则返回存储位置
6 */
7 LinkList getElemByValue(LinkList L, char value)
8 {
9 //定义指示指针指向L第一个结点
10 LinkList p = L->next;//L开始指向了头结点，L->next指向的就是第一个结点
11
12 while (p && p->data != value)
13 {