582 字
2 分钟
链表——随机插入节点
链表任意位置插入节点
本文会带大家实现在链表的任意位置插入节点，使用的语言依旧是c/c++。坐稳发车！
ps:本文没有做内存释放和异常处理（比如输入一个不存在的位置咋办），大佬勿怪😭
假设我们已经有上面的链表。并且想要实现一个Inert函数，传入的参数是data和n，n表示要插入的位置。
创建head
#include<iostream>using namespace std;struct Node{ int data; struct Node* next;};struct Node* head;int main(){ head =NULL;//表示空链表}结合这个，正好咱们来看看内存四区模型
这部分是os的内容，但是可以帮助我们理解链表。四区是粗略的划分，详细的还有BSS等。
从下到上前三个是固定内存大小，在编译过程中就已经定了。而堆（Heap）区域则可以动态申请。
我们上面的c代码实现了申请一个全局的内存用来存放head，如下图。
Insert函数实现
#include <iostream>using namespace std;struct Node{ int data; struct Node* next;};struct Node* head;void Insert(int data,int n){ Node* temp1=new Node(); temp1->data=data; temp1->next=NULL; //处理特殊情况 if(n==1){ temp1->next=head; head=temp1; return; } Node* temp2=head; for(int i=0;i<n-2;i++){//注意这里的n-2，从0到n-2实现了达到n-1的效果，所以也可以写成i<=n-1;画个图就很好理解了！ temp2=temp2->next;//这个循环实现的效果就是让指针到达n位置~！ } temp1->next=temp2->next; temp2->next=temp1;}
int main(){ head =NULL;//表示空链表 Insert(2,1);//List:2 Insert(3,2);//List:2,3 Insert(4,1);//List:4,2,3 Insert(5,2);//List:4,5,2,3 Print();}Print函数实现
void Print(){ Node* temp = head; while(temp != NULL){ printf("%d",temp->data); temp = temp->next; } printf("\n");}完整代码与分析
#include <iostream>using namespace std;struct Node{ int data; struct Node* next;};struct Node* head;void Insert(int data,int n){ Node* temp1=new Node(); temp1->data=data; temp1->next=NULL; //处理特殊情况 if(n==1){ temp1->next=head; head=temp1; return; } Node* temp2=head; for(int i=0;i<n-2;i++){//注意这里的n-2，从0到n-2实现了达到n-1的效果，所以也可以写成i<=n-1;画个图就很好理解了！ temp2=temp2->next;//这个循环实现的效果就是让指针到达n位置~！ } temp1->next=temp2->next; temp2->next=temp1;}void Print(){ Node* temp = head; while(temp != NULL){ printf("%d",temp->data); temp = temp->next; } printf("\n");}
int main(){ head =NULL;//表示空链表 Insert(2,1);//List:2 Insert(3,2);//List:2,3 Insert(4,1);//List:4,2,3 Insert(5,2);//List:4,5,2,3 Print();}流程
程序开始执行时，最初调用main函数，stack（栈）中的内存被分配用于执行函数，变成下图
接着执行到第三十六行，也就是Insert(2,1);,操作系统将会暂停main函数，并继续执行Insert函数的调用，因此进入Insert的栈，并且他有两个局部变量。
temp1对应的Node是new出来的，所以堆里面会有他指着的内存地址（假设是150）。
我们通过malloc或者new创建的内存，不是通过获取变量名来访问的！唯一的方法是利用指针变量！就像遥控器一样😎
所以我们可以用temp1指针来操纵150地址里的数据，比如第一次Insert存储了数字2，指向NULL也就是0.
第一个Insert执行后会变成这样。
接着执行第二个Insert到达下方代码块的位置，不会走for循环，结果是下图的样子
Node* temp2=head; for(int i=0;i<n-2;i++){//注意这里的n-2，从0到n-2实现了达到n-1的效果，所以也可以写成i<=n-1;画个图就很好理解了！ temp2=temp2->next;//这个循环实现的效果就是让指针到达n位置~！ } temp1->next=temp2->next; temp2->next=temp1;}
执行完所有的Insert就会变成下图
至于剩下的print就不说啦吧。。。。道理都是一个道理🐧
部分信息可能已经过时