单链表的常用算法
取值：取单链表中第i个元素的内容（有头结点的单链表）
算法思路
从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构，是顺序结构
算法步骤
-
从第一个结点（L - > next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L - > next。
-
j做计数器，累计当前扫描过的结点数，j初值为1。
-
当p指向扫描到的下一结点时，计数器j加1。
-
当j==i时，p所指的结点就是要找的第i个结点。
Status GetElem_L(LinkList L,inti,ElemType&e){ //获取线性表L中的某个数据元素的内容，通过变量e返回
p=L->next;j=1; //初始化
while(p&&j<i){ //向后扫描，直到p指向第i个元素或p为空
p=p->next;++j;
}
if(!p || j>i)return ERROR; //第i个元素不存在
e=p->data; //取第个元素
return OK;
}//GetElem_L
查找1：根据指定数据获取该数据所在的位置（该数据的地址）
算法步骤
-
从第一个结点起，依次和e相比较
-
如果找到一个其值与e相等的数据元素，则返回其在链表中的"位置"或"地址"
-
如果查遍整个链表都没有找到其值和e相等的元素，则返回0或"NULL"。
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;
}
查找2：根据指定数据获取该数据位置序号
//在线性表L中查找值为e的数据元素的位置序号
int LocateELem_L(LinkList L,Elemtype 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;
}
插入：在第i个结点前插入值为e的新结点
算法步骤
-
首先找到$a_$ 的存储位置p
-
生成一个数据域为e的新结点s
-
插入新结点：①新结点的指针域指向结点$a_i$（$s-> next = p-> next$）
②结点$a_$的指针域指向新结点($p->next = s$)
//在L中第i个元素之前插入数据元素e
Status ListInsert_L(LinkList &L,int i,ElemType 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;
}//ListInsert L
住：$p->next$有两层意思，
-
$p->next$ 作为指针： 在这种情况下，p是一个指向链表中某个结点的指针。因为链表的每个结点都有一个指向下一个结点的指针（通常称为 next 指针），因此p->next 表示 p 指针所指向的结点的下一个结点的地址。
-
$p->next$ 作为结点的指针域： 在这种情况下，p 是指向链表中某个结点的指针。每个结点都有一个 next域，用于存储指向下一个结点的指针。所以，p->next 表示 p 指针所指向的结点的 next 域，也就是指向下一个结点的指针。
删除：删除第i个结点
算法步骤
-
首先找到$a_$的存储位置p，保存要删除的$a_i$值。
-
令$p->next$指向$a_{i+1}$
-
释放结点$a_$的空间
//将线性表L中第个数据元素删除 Status ListDelete_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; }//ListDelete_L
单链表的查找、插入、删除算法时间效率分析
1.查找：
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间
复杂度为$O(n)$
2.插入和删除
因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度
为$O(1)$。
但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱
结点，所耗时间复杂度为$O(n)$)。
单链表的建立（头插法）
算法步骤：
-
从一个空表开始，重复读入数据
-
生成新结点，将读入 数据存放到新结点的数据域中
-
从最后一个结点开始，依次将各结点插入到链表的前端
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)i
p->next=L->next; //插入到表头
L->next=p;
}
}//CreateList_H
算法的时间复杂度是：$O(n)$
单链表的建立（尾插法）
算法步骤：
-
从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针指向链表
的尾结点。
-
初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点,
将新结点插入到尾结点后，r指向新结点。
//正位序输入个元素的值，建立带表头结点的单链衣L
void CreateList_R(LinkList &L,int n){
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指向新的尾结点
}
}//CreateList_R
算法的时间复杂度是：$O(n)$