数据结构_单向链表_删除操作

思路与分析 ​

假设我们要删除如下链表的 q 节点：

flowchart LR
	p --> q
	q --> c[r]

其实只需要将 q 的 next 指针交给 p ，q 就算是退出链表，用代码表示就是：

p->next = q->next;

流程就是： （1）让 p 指针从头节点开始，遍历到目标节点的前一个节点 （2）让 q 指向目标节点，也就是 p 节点的下一个节点 （3）p->next = q->next （4）释放 q 节点的数据空间

因为判断节点是否为空，指定的坐标是否为越界，这样的检查在插入和读取里都说过了，这里的流程就简述了，但不意味着不重要。

代码实现 ​

int DeleteElement(linkedlist l, int i, datatype *e)
{
	if (l == NULL || l->len == 0 || i >= l->len || i < 0)
		return -1;
	linkedlist p = l;
	for (int j = 0; j < i; j++)
	{
		p = p->next;
	}
	linkedlist q = p->next;
	p->next = q->next;
	*e = q->data;
	free(q);
	q = NULL;
	l->len--;
	return 0;
}

前面几行代码和读取一模一样，但要注意，我们要找的是下标 i 节点的前一个当 p，所以遍历过去的时候不需要往后移动 1 节点（相当于把头节点也计算进去了)。

另外，和读取一样，我们把删除位置的数据用第三个指针的参数传了出来，增加了代码的功能性，但可能在不需要这个数据的情况下，需要传入一个临时指针去保存数据。

[!question] 问题

如果不传出数据地址会怎么样？上面的代码里没有对 q->data 的释放，虽然我的代码里设计它是 int 的别名，但实际应用中更可能是通过 malloc 申请空间的结构体。所以应当在 free(q) 之前调用 free(q->data) ，或者调用专属的销毁函数（如果有的话）

尾部删除 ​

datatype temp;
DeleteElement(l, l->len - 1, &temp);

头部删除 ​

datatype temp;
DeleteElement(l, 0, %temp);

头尾可以按需求自行封装成对应函数，这点在插入操作里说过了。