单链表
一种以链接方式存储的线性表，适用于频繁增删操作，存储空间不定的情形。
单链表的一个存储结点包含两个域，数据域和指针域。数据域用于存储线性表的一个数据元素，指针域用于指示下一个结点开始的存储地址。
链表第一个结点的地址可通过头指针找到，其他结点的地址则在前驱结点的指针域中，最后一个结点没有后继，用NULL终结。
为了操作的方便，习惯上单链表带一个头结点，也就是first指向的第一个结点不存放任何数据，从第二个结点开始存放数据。
由于指针域的存在，数据元素的顺序与物理存储顺序可能不一致。
定义与封装
//结点的定义
struct LinkNode { //链表结点类的定义int data; //数据域
LinkNode *link; //链指针域
LinkNode() { link = NULL; } //构造函数
LinkNode(int item, LinkNode *ptr = NULL)
{ data = item; link = ptr; } //构造函数
};
带附加头结点的插入操作
1、newnode->link = p->link;
2、p->link = newnode;
注意图中标1和2的位置与代码相结合
带附加头结点的查找操作
查找过程就是从第一个结点开始不断沿着link域寻到和所需值相同的结点
带附加头结点的删除操作
1、q = p->link;
2、p->link = q->link;
3、delete q;
附加头结点的单链表创建
一般单链表的创建可采用前插法或者尾插法，
前插法就是每来一个新的结点，就把这个结点插在头结点的后面。
尾插法就是每来一个新的结点就把这个结点插在链表最后一个结点的后面，相比前插法需要设置一个尾指针。
实现插入过程和链表的插入操作几乎无区别。
优点：
长度很容易方便扩充。
缺点：
存储空间上多了指针域，存储空间代价比顺序表大。
至于带附加头节点和不带附加头节点的好处，看过书的同学都知道，前者的增删操作更简练
代码https://github.com/xiaoYaChh/datastructure.git
参考资料：数据结构第二版，殷人昆，清华大学出版社