[数据结构与算法]链表的三种插入方法（头插法，尾插法，任意位置插入）

插入作为链表的四大基本操作之一（增删改查），通常都会借助插入的方法增添信息，这一部分为大家着重讲解插入法。

1.头插法

简而言之，就是从链表的头部进行一个插入，定义一个结构体指针的新节点，并且为这个新的节点动态的分配内存。

如图所示：

?这个是原来的链表，现在要进行一个头插法的操作

如图所示：

?增添一个新结点Pnew

代码段如下:

Pnew->next = headNode->next;
headNode->next = Pnew;

2.尾插法

类似于头插法的道理，只不过此次的插入的位置是在链表的尾部，所以首先把文件遍历到尾部，然后进行操作。

如图所示：

?创建要插入的新节点 s

代码段如下：

struct Node *headNode;
while(headNode)
{
	headNode = headNode->next;
}
if(headNode)
{
	struct Node *s =(struct Node*)malloc(sizeof(struct Node));
	headNode->next = s;
	head = s;
	//增添的相关信息
	//eg.scanf("%d",s->结构体中的相关的变量)；
	headNode->next = NULL;                //s->next = NULL; 
}

3.任意插入

相较于前两个的方法，第三个的可选性增强了许多，这个方法可以类比尾插法的全部遍历，而这个任意位置的插入其实就是借助一个循环语句，遍历到你想要要的位置，从而达到目的。

如图所示：

?其实和第一个头插法特别的相似，只是不在头部了而已

代码段如下：

 struct Node *temp = headNode;
 int n                  //想要插入的位置 
 int i;
  for(i = 0;i<n;i++)
  {
	temp = temp->Next ;
  } 
   struct Node *Pnew = (struct Node *)malloc(sizeof(struct Node));
   Pnew->Next = temp->Next ;
   temp->Next = Pnew;

思路和头插法是一样的，只不过可以选择位置进行插入罢了。