单链表一

单链表样式样式： 头指针--->头结点---->a1---> ... --->an
头指针：
指的是链表指向第一个结点的指针，若链表有头结点，那么就会指向这个头结点。一般头指针会被冠以链表的名字，做标识作用。头指针必须存在
头结点:
放在第一个元素的结点之前，数据域一般没有意义，有时候可能用来存放链表的长度。有它是为了将头结点的操作和其它节点统一起来。头结点非必须。

单链表：若指向第i个元素，那么这个结点的数据域是i->data,指针域是i->next,i->next指向下一个元素。
单链表的读取（时间复杂度为O（n））：
获得链表第i个元素思路：
1）要声明一个结点p指向链表的第一个结点，初始化j从1开始。
2）当j <1，遍历链表，同时p的指针向后移动，指向下一个结点，j+1。
3）当到了链表末尾p为空时，说明第i个元素不存在
4）否则查找成功，返回结点p的数据。

将存储元素为e的结点插入到结点p和p->next之间，p和p->next的存储元素分别为ai和ai+1.
单链表的插入操作：
1）声明一个结点p指向链表的头结点，初始化j从1开始
2）2）当j <1，遍历链表，同时p的指针向后移动，指向下一个结点，j+1。
3）当到了链表末尾p为空时，说明第i个元素不存在
4）否则查找成功，在系统中生成一个空的结点s
5）将数据元素e赋值给s->data
6）单链表插入两个标准语句，s->next = p->next ,p->next = s;
7）返回成功

单链表的删除操作：
1）声明一个结点p指向链表的头结点，初始化j从1开始
2）2）当j <1，遍历链表，同时p的指针向后移动，指向下一个结点，j+1。
3）当到了链表末尾p为空时，说明第i个元素不存在
4）否则查找成功，将想删除结点p->next赋值给q
5）单链表的删除标准语句p->next = q->next
6）将q结点中的数据赋值给e
7）释放结点q

分析：单链表中插入和删除的时间复杂度都是O（n）,
相比顺序存储结构似乎并没有什么优势，但是在插入第i个位置的元素时，前一种只是第一次O（n），接下来每次只需移动指针，这时时间复杂度是O（1），而顺序存储结构始终是O（n）.所以对于插入和删除月频繁的操作，单链表的优势才会越明显。