【考研数据结构——C语言描述】第二章 线性表链式存储结构上的基本操作——单链表的插入
25计算机考研，数据结构知识点整理（内容借鉴了王道408＋数据结构教材），还会不断完善所整理的内容，后续的内容也会不断更新（可以关注），若有错误和不足欢迎各位朋友指出!
目录
一.插入操作
1.算法思想
2.结果
3.算法描述
4.算法分析
5.扩展：对某一结点进行前插操作
一.插入操作
在线性表的第i1≤i≤n+1)个位置之前插入一个新元素e。
1.算法思想
插入过程分为以下三步
①查找：在单链表中找到第i-1个结点并由指针pre指示。
②申请：申请新结点s，将其数据域的值置为e。
③插入：通过修改指针域将新结点s挂入单链表L。
2.结果
将长度为n的线性表（，... ，
，
，...，
），变成长度为n+1的线性表（
，... ，
，
，...，
）。
在单链表第i个结点前插入一个结点的过程如图2.11所示
3.算法描述
void InsList( LinkList L,int i, ElemType e)
/*在带头结点的单链表L中第i个位置插入值为e的新结点*/{Node *pre, *s;int k;if(i<= 0) return ERROR;pre=L;k=0; /*从头开始,查找第i-1个结点*/while( pre!= NULL&&k<i-1)/*表未查完且未查到第i-1个结点时重复,找到pre指向第i-1个结点*/{pre=pre->next;k=k+1;} /*査找第 i-1个结点*/if(pre==NULL) /*如当前位置pre 为空表示已查找完,但还未数到第i个,说明插入位置不合理*/{ printf("插入位置不合理!");return ERROR;}s=(Node*)malloc(sizeof(Node)); /*申请一个新的结点s*/s->data=e; /*值e置人s的数据域*/s->next=pre->next; /*修改指针,完成插入操作，将结点s插入L中*/pre=pre->s;return OK;
} //ListInsert——L
说明：若单链表中有几个结点，则按头插法操作时插人位置有n+1个，即1≤i≤n+1。当i=n+1时,则认为是在单链表的尾部插人一个结点。
特别注意：
插入时，①和②的顺序不能颠倒，否则，先执行p->next=s后，指向其原后继的指针就不存在了，再执行s->next=p->next时，相当于执行了s->next=s，显然有误。
4.算法分析
本算法主要的时间开销在于查找第i-1个元素，时间复杂度为O(n)。若在指定结点后插入新结点，则时间复杂度仅为O(1)。需注意的是，当链表不带头结点时，需要判断插入位置i是否为1，若是，则要做特殊处理，将头指针工指向新的首结点。链表带头结点时，插入位置i为1时不用做特殊处理。
5.扩展：对某一结点进行前插操作
前插操作是在某一结点的前面插入一个新结点，后插操作的定义刚好与之相反。算法中，通常都采用后插操作。以上面的算法为例，先找到第1-1个结点，即插入结点的前驱，再对其执行后插操作。由此可知，对结点内前插操作均可转化为后插操作，前提是从单链表的头结点开始顺序查找到其前驱结点，时间复杂度为 O(n)。
此外，可采用另一种方式将其转化为后插操作来实现，设待插入结点为*s，将*s插入到*p的前面。我们仍然将*s插入到*p的后面，然后将p->data与s->data 交换，这样做既满足逻辑关系，又能使得时间复杂度为O(1)。该方法的主要代码片段如下：
s->next-p->next; //修改指针域，不能颠倒
P->next=s;
temp-p->data;
p->data=s->data; //交换数据域部分
s->data=temp;