删除结点操作

删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删结点的前驱结点，再将其删除。其操作过程如图2-7所示。

图2-7 单链表结点的删除

假设结点*p为找到的被删结点的前驱结点，为了实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，即将*p的指针域next指向*q的下一结点。

实现删除结点的代码片段如下：

p=GetElem(L,i-1);  //查找删除位置的前驱结点
q=p->next;  //令q指向被删除结点
p->next=q->next  //将*q结点从链中“断开”
free (q) ;  //释放结点的存储空间

和插入算法一样，该算法的主要时间也是耗费在查找操作上，时间复杂度为O(n)。