一 建立单链表
延续前面的定义，数据取字符型，以/n作为输入结束条件，动态建立单链表通常分为头插法和尾插法，下面将一一描述。
（1）头插法
这种方式生成的链表节点次序与输入的次序相反
头插法具体算法代码
<pre name="code" class="cpp">linklist creatlisth(void)
{
char ch;
linklist head;//头指针
listnode *s; //工作指针
head = null; //链表开始为空
ch = getchar(); //读取第一个字符
while(ch!='\n')
{
s = (listnode *)malloc(sizeof(listnode));//生成新的节点
if（！s）
{
printf（"申请内存失败"）;
return null;
}
s->data = ch; //将读入的数据放入新节点数据域
s->next = head;head = s;
ch = getchar(); //读入下一个字符
return head;
}
（2）尾插法
算法思路：将新节点当前节点的尾部，直到读入结束标识符
这种方式生成的链表顺序与输入顺序一致，但是需要增加一个尾指针r，使其始终指向当前节点的尾节点
尾插法具体算法代码
linklist creatlistt(void)
listnode *s,*r;//工作指针
r = null;
ch = getchar(); //读入第一个字符
s = (listnode *)malloc(sizeof(listnode));//生成新节点
s->data = ch;//将读入的数据放入新节点的数据域
if(head==null)
head = s; //将新节点插入空表
else
r->next = s;//将新节点插入到*r之后
ch = getchar();//读入下一个字符
}
if(r!=null)
r->next = null;//对于非空表，将表尾指向指针域，置空head=s
return head;
注：以上俩个方法时间复杂度均为o（n）
二 单链表查找
（1）按序号查找
计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且j≠i时，则表示找不到第i个结点。
注意：头结点可看做是第0个结点。
算法思想：
listnode * getnode(linklist head,int i)
//在带头结点的单链表head中查找第i个结点，若找到（0≤i≤n），
//则返回该结点的存储位置，否则返回null
int j;
listnode *p;
p = head,j = 0;//从头开始扫描
while(p->next&&j<i){
p = p->next;
j++;
if(i==j)
return p;//找到了第i个结点
else
return null；
算法分析：
最多距离为i，这与气位置有关，在等概率假设情况下，平均时间复杂度为
（2）按值查找
listnode * locatenode(listnode head,datatype key)
listnode *p = head->next;//设置开始比较的节点
while(p&&p->data!=key)//直到p为null或者p->data为key
p = p->next;//扫描下一个节点
return p;
该算法的执行时间亦与输入实例中key的取值相关，其平均时间复杂度分析类似于按序号查找，为o(n)。
三 插入运算
插入运算思想 ：将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
具体步骤：
（1）找到ai-1存储位置p
（2）生成一个数据域为x的新结点*s
（3）令结点*p的指针域指向新结点
（4）新结点的指针域指向结点ai。
具体算法实现 ：
void insertlist(linklist head,datatype x,int i)
//将值为x的新节点插入到带头结点单链表head
//的第i个节点位置
p = getnode(head,i-1);//寻找第i-1个节点
if(p==null)
error("position error");
s = (listnode *)malloc(sizeof(listnode));
s->data = x;
s->next = p->next;
p->next = s;
主要集中在getnode上，因此时间复杂度仍旧为o(n)
四 删除运算
（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）
（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）
（3）释放结点ai的空间，将其归还给"存储池"。
记得释放内存就好
具体算法实现：
void deletelist(linklist head ,int i)
//删除带头结点的第i个节点
listnode *p,*r;
p = getnode(head,i-1);//找到第i-1个节点
if(p==null||p->next==null)
r = p->next;//r指向被删除结点的ai
p->next = r->next;//将ai从链上取下
free(r);//释放节点
时间复杂度也是o(n)
转载：http://blog.csdn.net/xsf50717/article/details/39899193