一 建立單連結清單
延續前面的定義，資料取字元型，以/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