本篇要解决的问题

        链表的所有相关操作中，什么操作用二级指针 ? 什么操作用一级指针?以及为什么这个操作要用一级指针?为什么那个操作要用二级指针？

背景

        我发现无论是观看学习视频，还是看数据结构相关的书籍，侧重点都是链表操作要如何移动相关结点。一些细小的地方，比如实现链表操作的伪代码函数的形参中，有的传一级指针，有的传二级指针。对于我等学渣。简直是无法理解。关键是有的同样的链表操作，有的视频用了一级指针，有的视频用了二级指针。很让人费解。而且网上与此相关的文章也只是给出了什么链表操作用什么指针，而没有给出为什么这样用？ 本篇文章不仅让你知道链表的什么操作用一级指针，什么操作用二级指针，以及为什么要这么用。

结论

链表的所有操作中，头插法建表、尾插法建表、链表的初始化操作、链表的销毁操作我们需要使用二级指针。而链表的插入、删除、查询、判空、打印操作使用一级指针即可实现。

链表的插入、删除、查询、判空、打印操作使用一级指针可以实现，使用二级指针亦可以实现，但是没必要。后面会画图说明为什么二级指针也可以实现。

验证

基础代码：

#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define null NULL
//定义单链表链表节点
typedef struct LNode {
  ElemType data;
  struct LNode *next;
}LNode;

//打印链表 
void printList(LNode *list){
	if(list == null){
		printf("链表头结点都没了,你还想打印啥?\n");
		return;
	}
	LNode *s = list->next;
	while(s!=null){
		printf("%d\n",s->data);
		s=s->next;
	}
}

链表头插代码：T(n)=O(n)   需要使用二级指针

//头插法建表  
bool createListHead(LNode **list,ElemType content[],int len){
	*list = (LNode *)malloc(sizeof(LNode));
	(*list)->next = null;
	for(int i = 0;i<len;i++){    
		LNode *s =(LNode *) malloc(sizeof(LNode));
		s->data = content[i];
		s->next = (*list)->next;
		(*list)->next = s; 
	}
	return true;
}

假如链表头插使用一级指针，错误代码如下：

//头插法建表  
bool createListHead(LNode *list,ElemType content[],int len){
	list = (LNode *)malloc(sizeof(LNode));
	list->next = null;
	for(int i = 0;i<len;i++){    
		LNode *s =(LNode *) malloc(sizeof(LNode));
		s->data = content[i];
		s->next = list->next;
		list->next = s; 
	}
	return true;
}

链表尾插代码:  T(bn)=O(n)    需要使用二级指针

//尾插法建表  T(n) = O(n)
bool createListTail(LNode **list,ElemType content[],int len){
	*list =(LNode *)malloc(sizeof(LNode));
	LNode *r;
	r=*list;
	for(int i = 0;i<len;i++){
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = content[i];
		r->next = s; 
		r=r->next;
	}
	r->next=null;
	return true;
}

假如链表尾插使用一级指针，错误代码如下:

//尾插法建表  T(n) = O(n)
bool createListTail(LNode *list,ElemType content[],int len){
	list =(LNode *)malloc(sizeof(LNode));
	LNode *r;
	r=list;
	for(int i = 0;i<len;i++){
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = content[i];
		r->next = s; 
		r=r->next;
	}
	r->next=null;
	return true;
}

测试方法代码：

int main(int argc, char *argv[])
{
	int a[]={1,2,3,4,5,6,7,8,9,10};
	//数组长度 
	int len =sizeof(a)/sizeof(a[0]);
	LNode *head=null;
	createListHead(&head,a,len);
	//createListTail(&head,a,len);
	printList(head);
    return 0;
}

测试结果：

使用二级指针的测试结果：

使用一级指针的测试结果：

分析原因：

此处以头插建立单链表代码进行分析，尾插法原因一样。

链表的初始化代码： T(n)=O(1)   需要使用二级指针

//单链表的初始化操作
bool initList(LNode **list){
	(*list) = (LNode *)malloc(sizeof(LNode));
	if((*list)==null){   //内存空间不足
		return false;
	}
	(*list)->next=null;
	return true;
}

假如链表初始化使用一级指针，错误代码如下:

//单链表的初始化操作 
bool initList(LNode *list){
	list = (LNode *)malloc(sizeof(LNode));
	if(list==null){   //内存空间不足
		return false;
	}
	list->next=null;
	return true;
}

测试方法代码：

int main(int argc, char *argv[])
{
	int a[]={1,2,3,4,5,6,7,8,9,10};
	//数组长度 
	int len =sizeof(a)/sizeof(a[0]);
	LNode *head=null;
    initList(&head);
    printList(head);
    return 0;
}

测试结果：

使用二级指针的测试结果：

使用一级指针的测试结果：

分析原因：

链表的销毁代码： T(n) = O(n)   需要使用二级指针

//链表的销毁代码
void destoryList(LNode **head){
	if((*head) == null){
		printf("该链表已经销毁,请勿重复销毁\n");
		return; 
	}
	while((*head)->next!=null){
		LNode *p = (*head)->next;
		(*head)->next = p->next;
		free(p);
	}
	free(*head);
	*head = null;
}

假如链表销毁使用一级指针，错误代码如下:

//链表的销毁代码
void destoryList(LNode *head){
	if(head == null){
		printf("该链表已经销毁,请勿重复销毁\n");
		return; 
	}
	while(head->next!=null){
		LNode *p = head->next;
		head->next = p->next;
		free(p);
	}
	free(head);
	head = null;
}

测试方法代码：

int main(int argc, char *argv[])
{
	int a[]={1,2,3,4,5,6,7,8,9,10};
	//数组长度 
	int len =sizeof(a)/sizeof(a[0]);
	LNode *head=null;
	createListHead(&head,a,len);
	printf("销毁链表前:\n");
	printList(head);
	destoryList(&head);
	printf("销毁链表后:\n");
	printList(head);
	return 0;
}

测试结果:

使用二级指针测试结果：

使用一级指针测试结果：

分析原因：

链表的销毁使用二级指针,不是因为一级指针不能把头结点和链表数据结点销毁掉，而是一级指针销毁掉数据结点和头结点之后，并不能对原来的头指针置为null,会导致原来的头指针成为野指针。

链表中能用一级指针实现的操作均能用二级指针实现，但是没必要。比如链表的判空操作。

链表判空代码： T(n)=O(1)     使用一级指针即可

//单链表的判空操作 T(n)=O(1)
bool isEmpty(LNode *list){          
	return list->next == null ? true:false; 
}

假如链表的判空代码使用二级指针,代码如下。 也能实现功能，但是没必要。

//单链表的判空操作 T(n)=O(1)
bool isEmpty(LNode **list){          
	return (*list)->next == null ? true:false; 
}

测试方法代码:

int main(int argc, char *argv[])
{
	int a[]={1,2,3,4,5,6,7,8,9,10};
	//数组长度 
	int len =sizeof(a)/sizeof(a[0]);
	LNode *head=null;
	createListHead(&head,a,len); //头插法建立单链表
	//printList(head); 
 	printf("头插法建立单链表后,链表的状态%d\n",isEmpty(head));   // 0代表非空 
 	//对链表进行删除
	 deleteList(head);
	 printf("对链表进行删除之后,链表的状态%d\n",isEmpty(head)); //对链表进行删除之后，1代表空 
 	
	return 0;	
}

测试结果：

0==false,代表非空，1==true代表空。

使用二级指针的测试结果：

使用一级指针的测试结果：

分析原因：

 

至此，我们应该弄明白了，链表函数的形参什么时候用一级指针，什么时候用二级指针，以及为什么要用一级指针，为什么要用二级指针。因为不是专业学C\C++的，对C++的理解并不太深，如果有哪写的不对不严谨的地方，还望指出。

下面仅贴出链表剩余操作相关代码：

链表的查询操作(按位查询)   T(n)=O(n)   使用一级指针

//按位查询  T(n) = O(n)
LNode * GetElem(LNode *list,int i){
	if(list==null) return null;
	if(i<0) return false;
	LNode *p = list;
	int j = 0;
	while(p!=null && j<i){
		p=p->next;
		j++;
	}
	return p;
}

链表的查询操作(按值查询)   T(n)=O(n)   使用一级指针

//按值查询  T(n)=O(n)
LNode * LocateElem(LNode *list,ElemType e){
	if(list == null) return false;
	LNode *p = list->next;
	while(p!=null && p->data != e){
		p=p->next;
	}
	return p;
}

链表的删除操作(后删)    T(n)=O(1)    使用一级指针

//链表的后删操作      T(n)=O(1)
bool deleteElem2(LNode *p,ElemType *e){
	if(p==null) return false;
	*e = p->data;
	LNode *q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return true;
}

链表的删除操作(前删)   

方式一：找到要删除元素的前驱结点，修改前驱结点的指向即可。  T(n) =O(n)   使用一级指针

//链表前删操作  T(n)=O(n)
bool deleteElem1(LNode *list,LNode *p, ElemType *e){
	if(p==null) return false;
	while(list->next!=null && list->next!=p){
		list=list->next;
	}
	if(list->next==null){
		return false;
	}
	*e = p->data;
	list->next = p->next;
	free(p);
	return true;
}

方式二:将后一个元素的值赋值给当前元素，删除后一个元素即可 T(n) =O(1)  使用一级指针   删除最后一个元素不适用。 

//链表元素前删  T(n) = O(1)
bool deleteElem2(LNode *p,ElemType *e){
	if(p==null) return false;
	*e = p->data;
	LNode *q = p->next;
	p->data = q->data;
	p->next = q->next;
	free(q);
	return true;
}

链表的删除操作(保留头结点)   T(n) =O(n)   使用一级指针。

//链表的删除操作(保留头结点)   T(n)=O(n)
void deleteList(LNode *head){
	if(head->next == null){
		printf("该链表已经被删除了\n");
		return;
	}
	while(head->next!=null){
	LNode *p = head->next;
	head->next = p->next;
	free(p);
	}
}

链表的插入操作(后插)  T(n)=O(1)   使用一级指针

//链表的插入操作(后插)  T(n)=O(1)
bool insertAfterP(LNode *p,ElemType e){
	if(p==null) return false;
	LNode *s =(LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

链表的插入操作(前插) 

方式一：循环找到前驱结点并插入 T(n) = O(n)  使用一级指针

//链表的前插 T(n) = O(n)
bool insertPriorP1(LNode *list,LNode *p,ElemType e){
	if(p==null) return false;  
	while(list->next!=null && list->next!= p){
		list=list->next;
	}
	if(list->next==null){
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = list->next;
	list->next = s;
	return true;
}

方式二：直接后插，并且交换两元素的值 T(n) = O(1)   使用一级指针

//链表的插入(前插)   T(n) = O(n)
bool insertPriorP2(LNode *p,ElemType e){
	if(p==null) return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return e;
}