先来看单链表的插入。假设存储元素e的结点为s，要实现结点p、p->next和s之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。可如何插入呢（如图3-8-1所示）？
    image.png
    根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改变即可。

    s->next = p->next; p->next = s;

    解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点（如图3-8-2所示）。
    image.png
    考虑一下，这两句的顺序可不可以交换？

    如果先p->next=s;再s->next=p->next;会怎么样？哈哈，因为此时第一句会使得将p->next给覆盖成s的地址了。那么s->next=p->next，其实就等于s->next=s，这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的，这点初学者一定要注意。

    插入结点s后，链表如图3-8-3所示。
    image.png
    对于单链表的表头和表尾的特殊情况，操作是相同的，如图3-8-4所示。
    image.png
    单链表第i个数据插入结点的算法思路：

    1. 声明一指针p指向链表头结点，初始化j从1开始；
    2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；
    3. 若到链表末尾p为空，则说明第i个结点不存在；
    4. 否则查找成功，在系统中生成一个空结点s；
    5. 将数据元素e赋值给s->data；
    6. 单链表的插入标准语句s->next=p->next;p->next=s；
    7. 返回成功。

    实现代码算法如下：

    1. /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)， */
    2. /* 操作结果：在L中第i个结点位置之前插入新的数据元素e，L的长度加1 */
    3. Status ListInsert(LinkList *L, int i, ElemType e){
    5.     int j;
    6.     LinkList p, s;
    7.     p = *L;
    8.     j = 1;
    10.     /* 寻找第i-1个结点 */
    11.     while (p && j < i){
    13.         p = p->next;
    14.         ++j;  
    15.     }
    17.     /* 第i个结点不存在 */
    18.     if (!p || j > i)
    19.         return ERROR;
    21.     /* 生成新结点（C标准函数） */
    22.     s = (LinkList)malloc(sizeof(Node));
    23.     s->data = e;
    25.     /* 将p的后继结点赋值给s的后继 */
    26.     s->next = p->next;
    28.     /* 将s赋值给p的后继 */
    29.     p->next = s;
    31.     return OK;      
    32. }

    在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放数据e的s结点。