---

单链表的操作

1.按序号查找

在单链表中取出第 i 个节点，并返回结点的指针。

LNode *GetElem(LinkList L,int i){
	int j = 1;
	LNode *p = L -> next;
	if(i == 0) return L;
	if(i < 0)  return NULL;

	while(p && j < i){
		p = p -> next;
		j++;
	}
	return p;
}

• if判断语句用来判读 i 是否在正确的使用范围内，（ i 不可以小于 0 ）。
• while 循环用来从链表的头部开始遍历，找到第 i 个结点，返回其指针。
• 此操作时间复杂度 O(n)。

p = p -> next 大致是这个样子的，如下图所示：

 

 

2.按值查找

查找某个值所在的结点，返回此结点的指针。

LNode *LocateElem(LinkList L,ElemType e){
	LNode *p = L -> next;
	while(p != NULL && p -> data != e )
		p = p->next;
	return p;
}

• while循环中的 p != NULL 是用来判断链表是否遍历到最后。

 

• 此操作时间复杂度 O(n)。

3.插入

将一个新的结点插入到第 i 个位置。

 

 

p = GetElem(L,i-1);
s -> next = p -> next;
p -> next = s;

• 获取第 i-1 个结点的指针，将新的结点 S 插入到第 i-1 个结点之后（第 i 个位置）。
• 因为查找第 i-1 个结点的位置时间复杂度为 O(n) 插入操作只需 O(1)，所以总体的时间复杂度为 O(n)。

########## 此操作称之为后插操作，与之对应的还有前插操作：

将一个结点插入到某个结...