链表简介（二）——在单向链表中插入节点

深藏阁楼爱情的钟 2022-10-19 12:40 171阅读 0赞

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

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

# 1 概述 #

在单向链表中插入节点，是要将待插入节点插入到链表的“合适”位置中。所以，这里需要一个**前提条件**：单向链表中的各节点是按其某个成员（如学生的成绩）的值有序排列（如由小打到）的。只有具备了这个前提条件，才能进行针对单向链表的节点插入操作。

为了将待插入节点插入到链表的“合适”位置中，需要进行两个步骤：

1.  找到链表中合适的位置；
2.  将节点插入到步骤1找到的位置中。

下面通过伪代码的形式介绍实现上述两个步骤的算法。

算法：InsertLinkedlist(list,new)
    目的：在单向有序链表中插入节点
    前提：链表和要插入的节点数据
    后续：无
    返回：新链表
    {
        if (list == null)           // insert into empty list
        {
            list <- new
            (*new).link <- null
        }
        else
        {
            while (((*new).data > (*cur).data) && ((*cur).link != null))    // find location where the new node insert into
            {
                pre <- cur
                cur <- (*cur).link
            }
            
            if ((*new).data <= (*cur).data)
            {
                if (list == cur)                // insertion at the beginning
                {
                    list <- new
                    (*new).link <- cur
                }
                else                            // insertion in the middle
                {
                    (*pre).link <- new
                    (*new).link <- cur
                }
            }
            
            if ((*cur).link == null)            // insertion at the end
            {
                (*cur).link <- new
                (*new).link <- null
            }
        }
        
        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 * insert(struct student * head, struct student * new_node);
        void print(struct student * list);
    
        /* create a static linked list, which sorted by student score from small to large */
        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_2;
        stu_2.next = &stu_1;
        stu_1.next = &stu_3;
        stu_3.next = NULL;
    
        /* print linked list before insertion */
        printf("before insertion, content of linked list as followed(sorted by student score from small to large):\n");
        print(list);
    
        /* create new node that wants to insert into linked list */
        struct student stu_new;
        stu_new.stu_num = 5;
        stu_new.stu_score = 83;
        
        /* insert new node into linked list */
        list = insert(list, &stu_new);
    
        /* print linked list after insertion */
        printf("after insertion, content of linked list as followed(sorted by student score from small to large):\n");
        print(list);
    
        return 0;
    }
    
    /*
    ** this is the insert linked list function.
    */
    struct student * insert(struct student * head, struct student * new_node)
    {
        struct student * cur;
        struct student * pre;
        struct student * new;
    
        cur = head;                 /* let cur point first node */
        new = new_node;             /* let new point the node that wants to insert into linked list */
    
        if (NULL == head)           /* insert into empty list */
        {
            head = new;
            (*new).next = NULL;
        }
    
        while (((*new).stu_score > (*cur).stu_score) && ((*cur).next != NULL))  /* find location where the new node insert into */
        {
            pre = cur;
            cur = (*cur).next;
        }
    
        if ((*new).stu_score <= (*cur).stu_score)
        {
                if (head == cur)        /* insertion at the beginning */
                {
                    head = new;
                    (*new).next = cur;
                }
                else                    /* insertion in the middle */
                {
                    (*pre).next = new;
                    (*new).next = cur;
                }
        }
    
        if ((*cur).next == NULL)        /* insertion at the end */
        {
            (*cur).next = new;
            (*new).next = NULL;
        }
    
        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][]

为了验证在链表头、链表尾插入的情况，可以修改结构体成员“stu\_new.stu\_score”的值，使节点满足在链表头、链表尾插入的条件。代码修改后的编译及运行情况如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70 1][]

说明：

*  为了简化代码内容，上述代码示例使用的是静态链表，即链表的所有节点都是在程序中定义的，节点的存储空间不是临时开辟的；
 *  上述代码示例中，链表是按照学生的分数由小到大排序的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70]: /images/20221005/dce66209485149718ed6f47b88f64c6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaXRkYXI_size_16_color_FFFFFF_t_70 1]: /images/20221005/c85a8132e9d14f3abd6e132082e90fb2.png