02 链表的插入实现：头插、尾插、指定位置插入（Linked List 链表）

柔情只为你懂 2022-01-09 12:49 112阅读 0赞

**实现代码**

#include <stdio.h>
    #include <stdlib.h>
    
    /*
     * 定义一个链表节点
     */
    typedef struct LinkedNode {
        int data;
        struct LinkedNode *next;
    } LinkedNode;
    
    /*头插法和尾插法，均是传入头指针，然后进行操作的,所以在入参的时候，用到的是双指针*/
    /*
     * 头插法
     * Following are the 4 steps to add node at the front.
     * Given a reference (pointer to pointer) to the head of a list
     * and an int,  inserts a new node on the front of the list.
     * 注意这里传的参数是指针的指针
     * Time complexity of push() is O(1) as it does constant amount of work.
     */
    void push(LinkedNode **head_ref, int new_data
    );
    
    /*
     * 尾插法
     * Add a node at the end: (6 steps process)
     * Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then change the next of last node to new node.
     * Given a reference (pointer to pointer) to the head
     * of a list and an int, appends a new node at the end
     */
    void append(LinkedNode **head_ref, int new_data);
    
    /**
     * 给定一个节点，在这个节点后面插入数据
     * @param prev_node 是一个指针，这个指针目前指在哪个节点，就将新节点插入到其后面
     * @param new_data
     */
    void insertAfter(LinkedNode *prev_node, int new_data);
    
    /*输出各节点的值*/
    void printList(LinkedNode *node);
    
    int main() {
        //1.测试一下头插法
        LinkedNode *head = NULL;
        //2.测试一下尾插法
        LinkedNode *tail = NULL;
        //因为push的入参是指针的指针，所以这里一定要用&取指针的地址
        printf("%p\n", &head);
        printf("头插法\n");
        push(&head, 5);
        push(&head, 6);
        push(&head, 7);
        printList(head);
        printf("尾插法\n");
        append(&tail, 4);
        append(&tail, 3);
        append(&tail, 2);
        printList(tail);
        //这里要传节点
        //将值插到指定的节点后面
        //tail本来是指向4的位置，tail->next就是3的位置。将7插入到3后面
        printf("对指定的节点后插入数据\n");
        insertAfter(tail->next, 7);
        printList(tail);
        return 0;
    }
    
    /*1.头插法*/
    void push(LinkedNode **head_ref, int new_data) {
        //1.声明一个LinkedNode类型的指针，并且给它申请内存空间，使它变成一个节点
        LinkedNode *new_node = (LinkedNode *) malloc(sizeof(LinkedNode));
        //2.将new_data值赋值给新申请的节点
        new_node->data = new_data;
        //3.使新申请的节点的next指向原头指针head_ref指向的节点
        new_node->next = (*head_ref);
        //4.将头指针前移，使头指针head_ref指向新申请的节点
        (*head_ref) = new_node;
    }
    
    /*2.尾插法*/
    void append(LinkedNode **head_ref, int new_data) {
        //1.声明一个LinkedNode类型的指针，并且给它申请内存空间，使它变成一个节点
        LinkedNode *new_node = (LinkedNode *) malloc(sizeof(LinkedNode));
        //2.将new_data值赋值给新申请的节点
        new_node->data = new_data;
        //3.因为是尾插法，所以new_node的next指针势必为NULL
        new_node->next = NULL;
        //4.定义一个新的LinkedNode类型的指针*temp，使它初始时等于头指针*head_ref
        //然后向后移动一直到指向最后一个节点
        //注意这里一定要是*temp = *head_ref，不能少掉*
        LinkedNode *temp = *head_ref;
    
        //5.如果这个头指针*head_ref为NULL,证明这是一个空链表，空链表的话，就直接将头指针指向新节点
        if (*head_ref == NULL) {
            *head_ref = new_node;
            //返回
            return;
        }
        //6.如果这个头指针*head_ref不为为NULL，非空链表,就要通过临时指针temp找到最后一个节点
        while (temp->next != NULL) {
            temp = temp->next;
        }
    
        //7.将新节点链接在指针后面
        temp->next = new_node;
        return;
    }
    
    // This function prints contents of linked list starting from head
    void printList(LinkedNode *node) {
        while (node != NULL) {
            printf(" %d ", node->data);
            node = node->next;
        }
    }
    
    void insertAfter(LinkedNode *prev_node, int new_data) {
        //1.首先要判空，这个节点不能够为空
        if (NULL == prev_node) {
            printf("the given previous node cannot be NULL");
            return;
        }
    
        //2.创建一个指针，并且给这个指针申请内存空间，使之成为一个节点
        LinkedNode *new_node = (LinkedNode *) malloc(sizeof(LinkedNode));
        //3.给新节点赋值
        new_node->data = new_data;
    
        //4.把prev_node->next的节点赋值给new_node->next
        new_node->next = prev_node->next;
    
        //把新申请的节点
        prev_node->next = new_node;
    }

**输出**

0x7ffeead397b0
    头插法
     7  6  5 尾插法
     4  3  2 对指定的节点后插入数据
     4  3  7  2