链表简介（三）——在单向链表中删除节点

亦凉 2023-01-23 03:54 22阅读 0赞

本系列文章简要介绍链表的相关知识。

本文是系列文章的第三篇，将介绍**在单向链表中删除节点**的方法，并给出代码示例。

# 1 概述 #

在单向链表中删除节点，首先要根据预先确定的节点标志，判断待删除节点是否存在于链表之中，如果链表中不存在该节点，则无需进行删除操作。如果该节点存在于链表之中，在删除该节点时，还需要区分以下两种情况：

*  待删除节点是链表的首节点；
 *  待删除节点不是链表的首节点（即该节点是中间节点或末尾节点）。

下面通过伪代码的形式介绍在单向链表中删除节点的算法。

算法：DeleteLinkedlist(list,target)
    目的：在单向链表中删除节点
    前提：链表和要删除的节点信息
    后续：无
    返回：新链表
    {
        if (list == null)           // empty list
        {
            // nothing to do
            return
        }
        
        cur <- list
        
        while (((*cur).num != (*target).num) && ((*cur).link != null))    // find target node location
        {
            pre <- cur
            cur <- (*cur).link
        }
        
        if ((*cur).num == (*target).num)    // target node in the list
        {
            if (list == cur)                // target node is the first node
            {
                list <- (*cur).link
            }
            else                            // target node is not the first node
            {
                (*pre).link <- (*cur).link
            }
        }
        else
        {
            // target node not found
        }
        
        return list
    }

# 2 代码示例 #

根据上述内容，可以编写在单向链表中删除节点的代码示例。

代码示例内容如下：

#include <stdio.h>
    
    #define STRUCT_LEN sizeof(struct student)
    
    struct student
    {
        int stu_num;                /* student number */
        float stu_score;            /* student score */
        struct student* next;
    };
    
    int main()
    {
        /* declaration of func */
        struct student * delete(struct student * head, struct student * target_node);
        void print(struct student * list);
    
        /* create a static linked list */
        struct student * list;
        struct student stu_1, stu_2, stu_3;
        stu_1.stu_num = 1;
        stu_1.stu_score = 88;
        stu_2.stu_num = 2;
        stu_2.stu_score = 66;
        stu_3.stu_num = 3;
        stu_3.stu_score = 100;
        list = &stu_1;
        stu_1.next = &stu_2;
        stu_2.next = &stu_3;
        stu_3.next = NULL;
    
        /* print linked list before deletion */
        printf("before deletion, ");
        print(list);
    
        /* create target node that to be deleted from linked list */
        struct student stu_del;
        stu_del.stu_num = 3;
        stu_del.stu_score = 0;         /* any value, because this item not compare */
        
        /* delete target node from linked list */
        list = delete(list, &stu_del);
    
        /* print linked list after deletion */
        printf("after deletion, ");
        print(list);
    
        return 0;
    }
    
    /*
    ** this is the delete linked list function.
    */
    struct student * delete(struct student * head, struct student * target_node)
    {
        struct student * cur;
        struct student * pre;
        struct student * target;
    
        cur = head;                 /* let cur point first node */
        target = target_node;       /* let target point the node that to be deleted */
    
        if (NULL == head)           /* empty list */
        {
            printf("list is null!\n");
            return head;
        }
    
        while (((*target).stu_num != (*cur).stu_num) && ((*cur).next != NULL))  /* find target node location */
        {
            pre = cur;
            cur = (*cur).next;
        }
    
        if ((*target).stu_num == (*cur).stu_num)        /* target node in the list */
        {
                if (head == cur)                        /* target node is the first node */
                {
                    head = (*cur).next;
                }
                else                                    /* target node is not the first node */
                {
                    (*pre).next = (*cur).next;
                }
        }
        else
        {
            printf("\ntarget node not found!\n\n");
        }
    
        return head;
    }
    
    /*
    *  this is the print linked list content function.
    */
    void print(struct student * list)
    {
        struct student *walker;
        walker = list;
    
        printf("the linked list contents(student number and score) as followed:\n");
        printf("[student number] [student score]\n");
    
        while (walker != NULL)
        {
            printf("%d                %-f\n", (*walker).stu_num, (*walker).stu_score);
            walker = (*walker).next;
        }
        
        return;
    }

上述代码的编译及运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70][]

说明：

*  上述代码中使用了待删除节点的学生学号信息“std\_num”作为删除标志，除此之外的待删除节点的其他信息，不影响节点删除逻辑；
 *  为了验证在待删除节点是链表首节点、链表中间节点和链表末尾节点的情况，可以通过修改待删除节点的结构体成员“stu\_del.stu\_num”的值，进行对应的测试；（上面已给出了这几种场景对应的测试结果）
 *  为了简化代码内容，上述代码示例使用的是静态链表，即链表的所有节点都是在程序中定义的，节点的存储空间不是临时开辟的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70]: /images/20221004/3d5af977fce547df9f25ff5e902263da.png