头插法和尾插法总结（动图版）

╰半橙微兮° 2022-10-27 12:07 226阅读 0赞

代码使用结构体：

typedef struct Node{
        
    	int value;
    	struct Node* next;
    }*Link;

**头插法**：利用头指针控制链表节点的增加。

> 核心：  
> newNode->next = head->next;  
> head->next = newNode;

![在这里插入图片描述][20210513181847881.gif_pic_center]

//头插法创建链表
    Link headCreateLink(int n){
        
        //头指针初始化部分
    	Link head,newNode;
    	head = (Link)malloc(sizeof(struct Node));
    	head->next = NULL;
        
    	while(n--){
        
    		newNode = (Link)malloc(sizeof(struct Node));
    		scanf("%d",&newNode->value);
            // 主要核心，新节点指向头指针的下一节点，头指针指向新节点。
    		newNode->next = head->next;
    		head->next = newNode;
            
    	}
        
    	return head;
    }

**尾插法**：需要借助一个辅助指针`rear`，指向当前链表最后一个节点，每次处理辅助指针指向的节点和新增的节点的关系即可。

> 核心：  
> newNode->next = rear->next;  
> rear->next = newNode;  
> rear = rear->next;

![在这里插入图片描述][20210203224216652.gif_pic_center]

//尾插法创建链表
    Link rearCreateLink(int n){
        
        //头指针初始化以及rear指针初始化指向头指针。
    	Link head,rear,newNode;
    	head = (Link)malloc(sizeof(struct Node));
    	head->next = NULL;
    	rear = head;
        
    	while(n--){
        
    		newNode = (Link)malloc(sizeof(struct Node));
    		scanf("%d",&newNode->value);
            // 主要核心，新节点指向rear的下一节点，rear的下一节点指向新节点（顺序切记不可搞反），rear指向新节点。
    		newNode->next = rear->next;
    		rear->next = newNode;
    		rear = rear->next;
    	} 
    	return head;
    }

测试时完整代码（可忽略）

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Node{
        
    	int value;
    	struct Node* next;
    }*Link;
    
    Link headCreateLink(int n);
    Link rearCreateLink(int n);
    void print(Link head);
    int main(){
        
    	Link L1 = headCreateLink(5);
    	Link L2 = rearCreateLink(5);
    	printf("头插法：");
    	print(L1);
    	printf("尾插法：");
    	print(L2);
    	return 0;
    }
    Link headCreateLink(int n){
        
    	Link head,newNode;
    	head = (Link)malloc(sizeof(struct Node));
    	head->next = NULL;
    	while(n--){
        
    		newNode = (Link)malloc(sizeof(struct Node));
    		scanf("%d",&newNode->value);
    		newNode->next = head->next;
    		head->next = newNode;
    	}
    	return head;
    }
    Link rearCreateLink(int n){
        
    	Link head,rear,newNode;
    	head = (Link)malloc(sizeof(struct Node));
    	head->next = NULL;
    	rear = head;
    	while(n--){
        
    		newNode = (Link)malloc(sizeof(struct Node));
    		scanf("%d",&newNode->value);
    		newNode->next = rear->next;
    		rear->next = newNode;
    		rear = rear->next;
    	} 
    	return head;
    }
    void print(Link head){
        
    	Link link;
    	if(head == NULL || head->next == NULL){
        
    		printf("此链表为空！\n");
    		return ;
    	}
    	link = head->next;
    	while(link!=NULL){
        
    		printf(" %d ",link->value);
    		link = link->next;
    	}
    	printf("\n");
    }

测试结果：  
![在这里插入图片描述][20210203224351485.png_pic_center]

[20210513181847881.gif_pic_center]: /images/20221024/c389f341678e42e8858321e95b55e2a2.png
[20210203224216652.gif_pic_center]: /images/20221024/57982ff9dd7f4919b2ce74e30c3fa905.png
[20210203224351485.png_pic_center]: /images/20221024/bcfe5e287db948fba5f630bc014c8c0a.png