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

实现代码

#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