【数据结构】单链表按位序插入元素e【前插】（带头结点的和不带头结点的）这篇很重要，文字说明比起其他篇是正确的

声明单链表的结构体成员

struct LNode {int data;struct LNode *next;
};typedef struct LNode LNode;// 或者: 两者是等价的
typedef struct LNode {int data;struct LNode *next;
}LNode;

按位序插入元素e：就是在第i个位置插入新结点，数据域为e

以下带头结点的：

思路：在第i个位置插入，就要找到第i-1个位置，然后在它的后面分配存储空间，创建新结点，再改变新结点以及其左右结点的指针指向，完成插入

1. 由于单链表不具有随机存取的特点，不能想找i就找i，只能从头开始依次遍历，也就是从头指针L开始，即第0个结点，因为一开始的时候L是指向第一个（i=1）结点的，
2. 就要用到循环，由于有条件判断，就用了while循环
3. 单链表具有指针域，声明的L头指针是指向链表的第一个实际元素的，但是L的指向不能动，它必须指向链表的第一个元素，所以就要再声明一个新的指针变量p，让它初始化指向单链表的第一个结点，即让p=L，以此实现从头开始遍历
4. 遍历到第i-1个位置，就可以停止，在其后面创建结点，分配存储空间
5. 怎么能用代码表示，新结点一定是在i-1结点的后面呢：让新结点的指针域指向i-1的指向，再让i-1的指针域指向新结点，通过指针完成，再给新结点的数据域赋值e，新结点就插入完成了
6. 注意：为了代码的健壮性，在执行上述代码时，我觉得有几个要注意的地方:

• 首先，要确保查找的位序是合法的，不然就不要执行了，会报错的，位序i从1开始，最多只能在第1 个位置插入新结点，<1肯定不合法
• 其次，如果查找的位序根本就不存在当前的单链表中，那么while循环走到最后，p指针应该是指向NULL，指向NULL的时候就不要再继续循环了，因为后面以及没有结点了
• 最后，由于是动态声明的单链表，可以动态分配存储空间，就不存在空间满了不能插入的情况，可以不做这个兼容

代码：

bool ListInsert(LinkList &L, int i, int e) {LNode *p;int j=0;p=L;if(i<1) {return false;		// 位序不合法，返回false停止指向插入操作}while(p!=NULL && j<i-1) {p=p->next;		// p结点的指针域存储的下一结点的地址赋值给p结点，表示p结点此时就走到了原p的下一节点，此时的P的指针域存的就是原p下一结点的指针域存的结点地址// 不能写成p->next=p,因为p->next=p表示p指针域指向的元素是p结点，就是自己指向自己了j++;}// 如果循环完整个单链表都没有找到要找的位序，最后p应该是指向null，如果p指向null，就不应该再指向插入操作了if(p==NULL) {// 我感觉，p最后会走向NULL，说明要找的位序都超过单链表的长度了，其实也可以在i<1的时候加个条件判断i>L.length也可以吧return false;}// 找到i-1,跳出循环，此时p指针指向i-1// 假设原顺序是p-q-r，现在想在p和q之间插入s，值为eLNode *s = (LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;		// p->next：p结点的指针域，存储下一结点的地址，即q结点的地址// s->next：s结点的指针域，存储下一结点的地址	// 将p结点的下一结点地址即q结点的地址，赋值给s结点的指针域存储，也就是说此时s指向的下一结点是qp-next=s;		// s表示新结点，p->next表示p的指针域，存储下一结点的地址// s赋值给p->next，就是说p指向的下一节点是s，即形成了p-s-q-rreturn true;
}

分析一下时间复杂度：

1. 最好时间复杂度，i=1时，循环0次，O(1)
2. 最坏时间复杂度，插在表尾，i=n，循环n-1次，O(n)
3. 平均时间复杂度，插在除表头和表尾之外的任意位置，他们的概率都是一样的p=1/(n-1)
   平均循环次数=总次数*概率=(1+2+3+…+n-1)*1/(n-1)=n(n-1)/2 * 1/(n-1) = n/2，O(n)

以下是不带头结点的：

请注意，头指针L和头结点是两个东西，一个单链表，它可以没有头结点，但它一定有头指针，头指针指向链表的第一个结点，如果链表带头结点，头指针L就指向头结点，头结点不存储数据，如果链表不带头结点，头指针L就指向链表的第一个实际结点

思路：在第i个位置插入结点，就要找到第i-1个结点，在它的后面创建新结点，给新结点分配存储空间，然后通过改变指针指向来实现，与带头结点的步骤一致。

• 只是有一点，此时考虑的是不带头结点的单链表，所以L指向第一个实际结点，在位序i=1的位置插入结点时，找i-1的位置，就找不到，因为原先是把头结点当作位序为0的位置做插入的。所以此时就要单独考虑i=1时的情况。

1. i=1时，第一个结点前面是头指针L，应该让头指针L指向新插入的i=1的结点，让新插入的i=1的结点的指针域存储原i=1的结点的地址，也就是原先头指针L存储的地址
2. 原先带头结点的单链表查找i是从0开始遍历的，因为头结点可看作位序为0的结点，在第1个位置插入就是在头结点后面插，所以要从i-0=0开始遍历。现在没有头结点，i=1的位置单独写逻辑了，只要考虑从第二个位置开始之后的，也就是从i-1=1开始遍历

bool inserList_Nohead(LinkList &L, int i, int e) {if(i<1) {return false;}if(i==1) {LNode *s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=L;L=s;}int j=1;LNode *p;p=L;// 以下这段和上面带头结点的插入其实是一样的，可以用一个函数调用，就不要写那么多代码了while(p!=NULL && j<i-1) {p=p->next;		// p->next:p结点的指针域，存储下一结点的地址，赋值给p结点就表示此时p结点变成了下一节点，// 如果写成p->next=p，就表示：p结点的指针域存储的结点是p结点，就是自己指向自己，这个链表就断了j++;}if(p==NULL) {return false;}LNode *s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return true;
}