单链表的算法

先进先出单链表（尾插法）

首先我们要知道什么是先进先出：每次插入的新元素，都是插在表尾。就比如饭堂打饭排队的时候，第一个打饭的人往往是第一个离开的，以此类推，最后一个人是最后离开的，这就是先进先出。

生成先进先出单链表：

struct node *creat1(){
    struct node *head,*tail,*p;		//结点变量声明
    int e;
    head=(struct node*)malloc(LENG);		//生成表头结点，一般第一个括号里的struct node为指针类型（不要忘记还有个*号），第二个括号里的LENG，写为sizeof（指针类型）*数据数量
    tail=head;		//尾指针指向表头
    scanf("%d",&e);		//输入第一个元素
    while(e!=0){		//e不为0(这个看需求而定，就是要有个结束的数)
        p=(struct node*)malloc(LENG);		//生成新的结点
        p->data=e;		//将元素e装进data域中
        tail->next=p;		//新节点链接到表尾(就是把尾指针指向新节点)
        tail=p;		//尾指针指向新节点
        scanf("%d",&e);		//再输入一个数赋值给e元素(准备将新的e元素装进新节点的data域中)
    }
    tail->next=NULL;		//尾结点的next置为空指针
    return head;		//返回头指针
}

实际上的操作就是在最后一个结点后面增加（插入）一个新的结点。

生成后进先出单链表（头插法）

然后我们来了解一下什么是后进先出：每次插入的新元素，都是插在表头，原本的元素将会向后排。就比如一个袋子，我们朝里面装东西，先装的东西会在下面，后装的东西会在上面。所以当我们拿东西的时候，就是先拿后装入的东西，然后再拿先装入的。

生成后进先出单链表：

struct node *creat2(){
	struct node *head,*p;		//结点变量声明
    head=(struct node*)malloc(LENG);		//生成表头结点
    head->next=NULL;		//置为空表
    scanf("%d",&e);		//输入第一个元素
    while(e!=0){		//e不为0
        p=(struct node*)malloc(LENG);		//生成新结点
        p->data=e;		//将元素e装进data域中
        p->next=head->next;		//新节点指针指向原首结点
        head->next=p;		//表头结点的指针指向新结点
        scanf("%d",&e);		//再输入一个数赋值给e元素
    }
    return head;		//返回头指针
}

简单画个图方便理解，为了方便了解这里将空结点（NULL）换为1结点；p结点换成二结点（画工不好，请见谅）：

最后经过整理就是这样：

2结点增加到1结点前面了。

插入一个结点（任意位置）

有些时候我们并不想在头部或者尾部插入元素，而是想在单链表的中间位置插入一个元素。

那么我们可以有两种操作方式，第一种是知道前一个结点的情况。原理和头插法是类似的，基本上就是把head结点改成需要插入位置的前一个位置的结点即可（假设要将add结点插入在1结点和2结点之间，1结点在前面）：

add=(struct node*)malloc(LENG);		//生成一个结点add
add->data=e;		//将元素e装入data域中
add->next=1->next;		//add结点指向1的后继，就是2结点
1->next=add;		//add结点成为1结点的后继

第二种是知道后一个结点的情况，其实方法基本上是一样的：

add=(struct node*)malloc(LENG);		//生成一个结点add
add->data=e;		//将元素e装入data域中
add->next=2;		//add结点成为2的前趋
1->next=add;		//add结点成为2的前趋结点的后继

需要稍微主要一下：我们不能直接"1->next=add;add->next=2;"因为一开始我们的1是未知的。