1. 单链表的初始化（带头结点的单链表 ）
   构造一个空表

Status InitList_L（LinkList &L）{
    L=new LNode；//或L=（LinkList）malloc（sizeof（LNode））；
    L->next=NULL;
    return OK;}

扩展：

• 判断链表是否为空

int ListEmpty(LinkList L){//若L为空表，则返回1，否则返回0
	if(L->next) //非空
		return 0;
	else
		return 1;
		}

2.单链表的销毁（从头指针开始，依此释放所有结点）

Status DestroyList_L（LinkList &L）{  //销毁单链表,依次删除结点
	Lnode *p; //或LinkList p；
	while(L){
		p=L;
		L=L->next;
		delete p;   
}

3.清空链表(链表仍存在，但无元素，成为空链表，头指针和头结点仍在)

Status  ClearList_L（LinkList &L）{  //销毁单链表,依次删除结点
	Lnode *p,*q; //或LinkList p；
	p=L->next;    //从首元结点开始，不是头结点
	while(p){
		q=p->next;
		delete p;
		p=q;}
		L->next=NULL;  //头结点的指针域为空
		return OK；
}

4.求链表表长

int  ListLength_L（LinkList L）{  //返回L中数据元素个数
	Lnode *p; //或LinkList p；
	p=L->next;    //P指向第一个结点（首元结点）
	i=0；
	while（p）{
		i++；
		p=p->next;
	}
	return i;
}

5.取值（取单链表中第i个元素内容化，顺序存取）

Status GetElem_L（LinkList L,int i,ElemType &e）{  //获取线性表L中的某个数据元素的内容，通过变量e返回
	p=L->next;j=1;    //P指向第一个结点（首元结点）
	while（p&&j<i）{
		p=p->next;++j;
	}
	if(!p||j>i) return ERROR; //第i个元素不存在
	e=p->data；   //取第i个元素
	return OK;
}

6.按值查找（根据指定数据获取该数据所在位置（地址））

Lnode *LocateElem_L(LinkList L,Elemtype e){
//在线性表L中查找值为e的数据元素
//找到，则返回L中值为e的数据元素地址，查找失败返回NULL
p=L->next;
while(p&&p->data!=e)
	p=p->next;
	return p;
	}

根据指定数据获取该数据位置序号

int LocateElem_L(LinkList L,Elemtype e){
//在线性表L中查找值为e的数据元素
//找到，则返回L中值为e的数据元素的位置序号，查找失败返回0
p=L->next;j=1;
while(p&&p->data!=e)
	{p=p->next;j++;}
	if(p) return j;
	else return 0;
	}

7.插入（在第i个结点前插入值为e的新结点）

Status ListInsert_L（LinkList &L,int i,ElemType e）{  //在L中第i个元素之前插入数据元素e
	p=L;j=0;
	while(p&&j<i-1){p=p->next;++j;}//寻找第i-1个结点，p指向i-1结点
	if(!p||j>i-1)return ERROR; //i大于表长+1或者小于1，插入位置非法
	s=new LNode;s->data=e; //生成新结点s，将结点s的数据域置为e
	s->next=p->next;       //将结点s插入L中
	p->next=s;
	return OK;
}

7.删除（删除第i个结点）

Status LisDelete_L（LinkList &L,int i,ElemType &e）{  //
   p=L;j=0;
   while(p->next&&j<i-1){p=p->next;++j;}//寻找第i个结点，p指向其前驱
   if(!(p->next)||j>i-1)return ERROR; //删除位置不合理
   q=p->next;             //临时保存被删结点的地址以备释放
   p->next=q->next； //改变删除节点前驱结点的指针域
   e=q->data;         //保存删除节点的数据域
   delete q;             //释放删除节点的空间
   return OK；            
}

单链表的查找、插入、删除算法的时间效率
1.查找：

• 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O（n）。
  2.插入和删除：

• 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O（1）。

• 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O（n）。

单链表的建立
1.头插法（元素插入在链表头部）

void CreateList_H(LinkList &L,int n){
	L=new LNode;]
	L->next=NULL; //先建立一个带头结点的单链表
	for(i=n;i>0;--i){
		p=new LNode;  //生成新结点p=(LNode*)malloc(sizeof(LNode));
		cin>>p->data;  //输入元素值 scanf(&p->data);
		p->next=L->next;   //插入到表头
		L->next=p;
		}
}

2.尾插法（元素插入在链表尾部）

void CreateList_R(LinkList &L,int n){//正位序输入n个元素的值，建立带表头结点的单链表L
	L=new LNode;
	L->next=NULL;
	r=L;   //尾指针r指向头结点
	for(i=0;i<n;++i){
		p=new LNode;cin>>p->data;  //生成新结点，输入元素值
		p->next=NULL;
		r->next=p;   //插入到表尾
		r=p;  //r指向新的尾结点
		}
}

带尾指针循环链表的合并

LinkList Connect(LinkList Ta,LinkList Tb){//假设Ta、Tb都是非空的单循环链表
	p=Ta->next;            //p存表头结点
	Ta->next=Tb->next->next;       //Tb表头连接Ta表尾
	delete Tb->next;         //释放Tb表头结点
	Tb->next=p;       //修改指针
	return Tb；
	}

---

双向链表的插入

void ListInsert_DuL(DuLinkList &L,int i,ElemType e){
//在带头结点的双向循环链表L中第i个位置之前插入元素e
	if(!(p=GetElemP_DuL(L,i)))  return ERROR;
	s=new DuLNode;    s->data=e;
	s->prior=p->prior;
	p->prior->next=s;
	s->next=p;
	p->prior=s;
	return OK;
	}  

双向链表的删除

void ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
//删除带头结点的双向循环链表L的第i个元素，并用e返回
	if(!(p=GetElemP_DuL(L,i)))  return ERROR;
	e=p->data;
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p)
	return OK;
	}