数据结构与算法学习：单向链表之插入与删除

之前完成了单向链表的创建和遍历，这里来说说如何插入与删除。
因为链表的特性，插入与删除十分方便，只需要在前后两个结点进行操作。而数组等连续存储则必须重新申请全部数据的空间，并且复制。因此插入与删除时，链表效率较高(￣^￣゜)

单向链表之插入

还是使用《数据结构与算法学习：单向链表之构造与遍历》中的代码，先创建一个链表。
生成链表

0->2->4->6->8->10->12->14->16->18

此时假设给定一个int，要求按数值大小插入链表中，此时有几步需要完成

1. 寻找要插入的位置
2. 创建新数据结点，插入数据，指针域指向插入位置的下一个结点
3. 修改前一数据结点的指针域，指向该新数据结点

• 一个普遍的情形是，该位置在链表中，此时需要遍历并通过比较数据大小来找到位置。
• 另一个特殊的情形则是，该位置位于第一个结点，此时第三步则变成修改head指针指向新结点。
  （当链表存在头结点时还得处理下头结点的问题，注意“头结点”≠“第一个数据结点”，头结点并不用于存储数据，本文中不设头结点）

函数原型：void Insert(List *&head, List *node);

首先考虑特殊情形，当要插入的位置刚好位于链表首部时，此时较容易检测出，直接将node与head的数据比较即可（不会的自己回去复习( •̀д•́) ），而后直接执行第二步生成新结点后返回。

if ( node->data <= head->data ) //1. 检测特殊情形
{
    node->pNext = head; // 2. 指向之前的第一个第一个结点
    head = node;  //3. 修改
    return ; //完成了插入操作，可以返回啦
}

更普遍的情形，就需要遍历链表并逐个比较数据大小啦(￣^￣゜)

List *q = head->pNext, *p = head; // 因为首位置是特殊情形已处理，从第二个结点开始比较
while (q != NULL)
{
    if ( node->data > q->data )
    {
        p = q;
        q = q->pNext; //继续向下遍历
    }else{
        break; //找到位置，退出循环
    }

}

结束循环后，p所指向的即为要插入数据的前一结点
而后插入新结点

p->pNext = node;
node->pNext = q;

此时插入完成，执行返回return ;
整个函数如下：

void Insert(List *&head, List *node) //必须保证链表中数据为升序
{
    if ( node->data <= head->data )
    {
        node->pNext = head;
        head = node;
        return ;
    }
    List *q = head->pNext, *p = head;
    while (q != NULL)
    {
        if ( node->data > q->data )
        {
            p = q;
            q = q->pNext;
        }else{
            break;
        }
    }
    p->pNext = node;
    node->pNext = q;
    return ;
}

最后，我们可以用点小技巧，即可认为第一个结点之前还存在一个NULL结点，即可将该两种情形的代码逻辑合并，处理链表问题中这也是个思路。

void Insert(List *&head, List *node) //必须保证链表中数据为升序
{
    List *q = head, *p = NULL; //从第一个结点开始比较，设置第一个结点的前一个结点为NULL
    while (q != NULL)
    {
        if ( node->data > q->data )
        {
            p = q;
            q = q->pNext;
        }else{
            break;
        }
    }
    if (p != NULL) //要注意空指针问题，否则可能引起异常
        p->pNext = node;
    else
        head = node; //特殊情形，修改head指针指向新结点
    node->pNext = q;
    return ;
}

单向链表之删除

还是这个链表，与插入大同小异，除了插入中的那些坑，还需要注意下内存的释放。
直接上代码算了。相信只要会插入就可以看懂下面这段(/ω＼)

void delete(List *&head, int data)
{
    List *q = head, *p = NULL;
    while (q != NULL)
    {
        if ( data != q->data )
        {
            p = q;
            q = q->pNext;
        }else{
            break;
        }
    }
    if (p != NULL){
        p->pNext = q->pNext; //链接前后结点
    }else{
        head = q->pNext; //修改head指针
    }
    delete q; //释放从链表脱离的结点所占用内存，否则内存泄漏
    return ;
}

自我吐槽：懒癌无药可救╮(￣⊿￣)╭

Donate