单链表的定义、插入和删除

一、定义一个单链表

struct LNode{          //定义单链表节点类型
	ElemType data;     //存放节点数据元素
	struct LNode *next; //指针指向下一个结点
};
//增加一个新节点：在内存中申请一个结点所需空间，并用指针p指向这个结点
struct LNode * p =(struct LNode *)malloc(sizeof(struct LNode));

typedef 关键字 —— 数据类型重命名，所以上述代码还可以写成：

typedef struct LNode LNode; //struct LNode重命名为LNode
LNode * p =(LNode *)malloc(sizeof(LNode));

书本上的写法

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

/*
上述写法与下面写法等价
*/
struct LNode{
	ElemType data;
	struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

这里有一点需要注意：
虽然LNode *和LinkList效果一样，但是两者的意义不一样。

强调这是一个单链表——LinkList
强调这是一个结点——LNode *

二、初始化一个单链表

1.带头结点

带头结点：头指针指向一个节点，这个结点不存放数据，这个结点的next存放指向第一个数据的指针，这样的节点叫头结点。

不带头结点：头指针指向的第一个节点就是数据元素结点。

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//初始化一个单链表（带头结点）
bool InitList(LinkList &L){
	L = (LNode *)malloc(sizeof(LNode));//分配一个头结点
	if(L==NULL)        //内存不足，分配失败
		return false;
	L->next = null;    //头结点之后暂时还没有节点
	return true;
}
//判断单链表是否为空（带头结点）
bool Empty(LinkList L){
	if(L->next == NULL)
		return true;
	else
		return false;
}
void test(){
	LinkList L; //声明一个指向单链表的指针
	InitList(L);//初始化一个空表
	//......
}

2.不带头结点

空表判断条件

L == NULL

三、单链表的插入

（一）按位序插入（带头结点）

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

//在第i个位子插入元素e
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1)
		return false;
	LNode *p; //p指向当前扫描到的结点
	int j=0;  //当前p指向的是第几个结点
	p=L;      //L指向头结点头结点是第0个结点（不存放数据）

	/*
	因为要插入到第i个结点，所以我们只要找到第i-1个结点，然后将结点插入				到第i-1个结点即可。
	*/
	while(p!=NULL && j<i-1){ //循环到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)   //i值不合法
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true; //插入成功

}

代码解析：
1.j=0,以i=1为例，不满足j<i-1,直接跳过循环。

• 第一步，LNode *s=(LNode *)malloc(sizeof(LNode)); 开辟一块结点内存空间；将e赋给s结点的data域：s->data = e
• 第二步，改变指针指向：s->next = p->next; p->next = s;
  需要注意的是①和②的操作不能颠倒，否则就会导致s结点之后的数据丢失。
  
  2.j=0,以i=3为例，i-1=2，j<i-1，满足循环条件
• 下面分析一下循环部分的代码
  ① j=0，j<2，执行p=p->next，满足循环条件，p向后移动
  
  ②j++=1，j<2，执行p=p->next，满足循环条件，p向后移动
  
  ③j++=2，不满足循环条件，跳出循环

之后插入的操作跟上述i=1的操作一样

• 开辟结点空间，并给结点空间赋值：LNode *s=(LNode *)malloc(sizeof(LNode)); s->data = e;
  
• 改变指针指向：s->next = p->next; p->next = s;
  
  3.如果i=6，当p指向第5个结点时不满足p!=null（即找不到第i-1个结点），会跳出循环

时间复杂度分析：

• 插入表头时间复杂度为 O(1)
• 插入到表尾时间复杂度为O(n)
• 平均时间复杂度为O(n)

（二）按位序插入（不带头结点）

思路：跟带头结点一样，找到第i-1个结点，然后把结点插入第i-1个结点之后。
需要注意的是，如果不带头结点，则插入、删除第一个元素时，需要更改头指针。

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
bool ListInsert(LinkList &L,int i,ElemType e){
	if(i==1){//插入第一个结点操作与其他结点不同
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L=s; //头指针要指向新的结点
		return true;
	}
	LNode *p;
	int j=1;//当前p指向的是第几个结点
	p=L;    //p指向第一个结点，不是头结点
	while(p!=NULL && j<i-1){//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL){
		return false;//i值不合法
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true; //插入成功

}

四、指定结点的插入操作

（一）指定结点的后插操作

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){
	if(p==NULL)
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

（二）指定结点的前插操作
思路1：如果要在p的前驱插入一个结点，那就循环查找p的前驱q，再对q后插
但是如果要找到p的前驱就要传入头指针。

//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LinkList L,LNode *p,ElemType E){
}

时间复杂度：O(n)
思路2：
新建一个结点，让这个结点作为p的后继结点。然后调换一下两个结点里的数据，这样需要插入的数据依旧在p的前面，依然可以实现前插操作。

bool InsertPriorNode(LNode *p,ElemType e){
	if(p==NULL)
		return false;
	LNode *s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->next=p->next; 
	p->next=s;       //新结点s连接到p之后
	s->data=p->data; //p中的元素复制到s中
	p->data=e;       //p中存放新插入的数据e
	return true;
}

时间复杂度：O(1)

关键代码图解：

①s->next=p->next; ②p->next=s;

s->data=p->data; p->data=e;

五、删除

(一)、按位序删除

删除表L中第i个位置的元素

思路：如果要删除第i个元素，那么找到第i-1个元素，让其指向第i+1个元素，再把第i个元素的空间释放掉。

//带头结点
bool ListDelete(LinkList &L,int i,ElemType &e){
	if(i<1)
		return false；
	LNode *p;//p指向当前扫描的结点
	int j=0; //当前p指向的是第几个结点
	p=L;     //L指向头结点，头结点是第0个结点（不存放数据）
	while(p!=NULL && j<i-1){//循环找到第i-1个结点
		p=p->next;
		j++;
	}
	if(p==NULL)   //i值不合法
		return false;
	if(p->next==NULL) //第i-1个结点之后已无其他结点
		return false;
	LNode *q=p->next; //q指向被删除的结点
	e=q->data;        //用e返回被删除的元素的值
	p->next=q->next;  //被删除的结点从链表中断开
	free(q);          //释放结点的存储空间
	return true;      //删除成功
}

最坏、平均时间复杂度：O(n)
最好时间复杂度：O(1)

（二）、指定结点删除

同样的道理，如果不传入头指针，那就找不到指定指定结点的前驱结点。

那如果在不传入头指针的情况下该怎么删除呢？我们想到一个办法：把p的后继结点的数据域赋给p,然后再把p的后继结点q所指向的空间释放掉。

//删除指定结点p
bool DeleteNode(LNode *p){
	if(p==NULL)
		return false;
	LNode *q=p->next;//q指向p的后继结点
	p->data=p->next->data;//和后继结点交换数据域
	p->next=q->next;
	free(q);
	return true;
	
}

①初始状态，LNode *q=p->next;

②交换数据域，p->data=p->next->data;

③改变指针指向，p->next=q->next;，最后再释放q所指向的空间，free(q);

注意：如果要删除的是最后一个结点的话，q会指向null，这时候只能采用传入头指针遍历，找到前驱结点的办法来删除。