单链表的运算之插入运算
插入运算 （ ）思想方法 插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 与ai之间 具体步骤 （ ）找到ai 存储位置p （ ）生成一个数据域为x的新结点*s （ ）令结点*p的指针域指向新结点 （ ）新结点的指针域指向结点ai
具体插入过程【参见动画演示】
（ ）具体算法实现 void InsertList(LinkList head DataType x int i) {//将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上 ListNode *p; p=GetNode(head i );//寻找第i 个结点 if (p==NULL)//i< 或i>n+ 时插入位置i有错 Error( position error ) s=(ListNode *)malloc(sizeof(ListNode)); s >data=x;s >next=p >next;p >next=s; }
（ ）算法分析 算法的时间主要耗费在查找操作GetNode上 故时间复杂度亦为O(n)
删除运算 （ ）思想方法 删除运算是将表的第i个结点删去 具体步骤 （ ）找到ai 的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai 的指针域next中） （ ）令p ＞next指向ai的直接后继结点（即把ai从链上摘下） （ ）释放结点ai的空间 将其归还给 存储池
具体操作过程【参见动画演示】
（ ）具体算法实现 void DeleteList(LinkList head int i) {//删除带头结点的单链表head上的第i个结点 ListNode *p *r; p=GetNode(head i );//找到第i 个结点 if (p==NULL||p >next==NULL)//i< 或i>n时 删除位置错 Error( position error );//退出程序运行 r=p >next;//使r指向被删除的结点ai p >next=r >next;//将ai从链上摘下 free(r);//释放结点ai的空间给存储池 } 注意 设单链表的长度为n 则删去第i个结点仅当 ≤i≤n时是合法的 当i=n+ 时 虽然被删结点不存在 但其前趋结点却存在 它是终端结点 因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在 仅当*p存在（即p！=NULL）且*p不是终端结点（即p ＞next！=NULL）时 才能确定被删结点存在
