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

声明单链表的结构体成员

struct LNode {
	int data;
	struct LNode *next;
};

typedef struct LNode LNode;

// 或者: 两者是等价的
typedef struct LNode {
	int data;
	struct LNode *next;
}LNode;
1
2
3
4
5
6
7
8
9
10
11
12

按位序插入元素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 && jnext;		// 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，值为e
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;		
	// p->next：p结点的指针域，存储下一结点的地址，即q结点的地址
	// s->next：s结点的指针域，存储下一结点的地址	
	// 将p结点的下一结点地址即q结点的地址，赋值给s结点的指针域存储，也就是说此时s指向的下一结点是q
	p-next=s;		// s表示新结点，p->next表示p的指针域，存储下一结点的地址
	// s赋值给p->next，就是说p指向的下一节点是s，即形成了p-s-q-r
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

分析一下时间复杂度：

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 && jnext;		
		// 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29