四、插入元素操作
前面已经分析过，在线性表中"插入"一个元素时，使元素之间的关系<
,
>改变为< ,e
>和< e,
>。当用指针指示后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可。因为新的元素插入在线性表的第i个元素之前，使得
不再是
的后继，而是新的元素e的后继，因此需要修改元素e和元素
所在结点的指针。由此，算法的基本思想就是，首先找到第i-1个结点，然后修改相应指针。
算法2.16bool ListInsert ( SLink &L, int pos, ElemType e )
{
// 若1≤pos≤LengthList(L)+1，则在指针L指向头结点的单链表
// 的第 pos 个元素之前插入新的元素 e，且返回函数值为 TRUE,
// 否则不进行插入且返回函数值为 FALSE
p=L; j=0;
while(p && j<pos-1)
{ // 查找第pos-1个结点，并令指针p指向该结点
p=p->next; ++j;
} // while
if(!p||j>pos-1)
return FALSE; // 参数不合法，pos 小于1或者大于表长+1
s=new LNode;
if (!s) exit(1); // 存储空间分配失败
s->data=e; // 创建新元素的结点
s->next=p-> next; p->next=s; // 修改指针
return TRUE;
} // ListInsert
算法时间复杂度为O (ListLength(L))。
算法2.16的演示效果如动画所示。
|
|||
|
这里的变量初始化能否改为 
|
|||
|
算法时间复杂度的分析：
在插入算法中，修改指针的时间复杂度仅为O(1)，但为了修改前驱结点的指针首先要找到这个结点，因此插入算法的时间主要消耗在查询结点上，因此，其时间复杂度和"存取元素"的操作相同。