数据结构--单链表的删除

要删除链表中第i个节点的基本算法如下：

（1）定位第i-1个节点。指针q 指向第i-1个节点，指针p指向被删除的节点。

（2）摘链。q->link = p->link。

（3）释放p节点。free(p)。



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




                                        图：单链表结点的删除


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


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

        p=GetElem(L,i-1);          //查找删除位置的前驱结点（查看前一篇文章：单链表插入）

        q=p->next;                  //令q指向被删除结点（q就是p的下一个节点）

        p->next=q->next          //将*q结点从链中“断开”

        free (q) ;                      //释放结点的存储空间


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