1、單鏈表
如下圖為單鏈表示意圖： 
只列出頭文件以及單鏈表相關(guān)函數(shù)實(shí)現(xiàn)代碼，均來源于書上，并整理出分析過程。
_List_H.h// _List_H.h#ifndef _List_Hstruct Node;typedef struct Node * PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;List MakeEmpty(List L);int Isempty(List L);int IsLast(Position P,List L);Position Find(ElementType X,List L);Position FindPRevious(ElementType X,List L);void Delete(ElementType X,List L);void Insert(ElementType X,List L,Position P);void DeleteList(List L);Position Header(List L);Position First(List L);Position Advance(Position P);ElementType Retrieve(Position P);#endif /*_List_H*/List_Function.c// List_Function.c/*Place the implemention of the functions*/#include '_List_H.h'struct node{ ElementType Element; Position Next;};/*return true if L is empty*/int IsEmpty(List L){ return L->Next==NULL;}/*return true if P is the last position in list L*//*parameter L is unused in this implementation*/int IsLast(Position P,List L){ return P->Next==NULL;}/*return the podsition of X in L;Null if not found*/Position Find(ElementType X,List L){ Position P; P=L->Next; while(P!=NULL && P->Element!=X) P=P->Next; return P;}/*return the previous position of X;Null if not found X*/Position FindPrevious(ElementType X,List L){ Position P; P=L; /*Let P=L,for easier to check the next one*/ while(P->Next!=NULL && P->Next->Element!=X) P=P->Next; return P;}/*//Another version of FindPrevious(may some mistakes)Position FindPrevious(ElementType X,List L){ Position P_now,P_next; P_now=P->Next; //Difference:P_now!=L P_next=P_now->Next; if(P_now->Element==X) return P_now; else { while(P_now->Next!=NULL && P_next->Element!=X) { P_now=P_next; P_next=P_next->Next; } }}*//*Delete first occurrrence of X from a list*//*Assume use of a header node*/void Delete(ElementType X,List L){ Position P,TmpCell; /*TmpCell is used for free function*/ P=FindPrevious(X,L); if(!IsLast(P,L)) /*If IsLast(P,L) is true,then X must be NULL*/ { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } /*Attention:this is a 'void' function*/}/*Insert X after position P*/void Insert(ElementType X,List L,Position P){ Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) { printf("Out of space"); return -1; } TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell;} 重要經(jīng)驗(yàn)：當(dāng)編寫涉及指針的數(shù)據(jù)結(jié)構(gòu)或者算法時(shí)，最好先畫出結(jié)構(gòu)圖分析過程，再進(jìn)行寫代碼。（其實(shí)，除了涉及指針的要，很多數(shù)據(jù)結(jié)構(gòu)、圖論等相關(guān)算法都先畫圖分析，清楚思路后才碼代碼較好）
以下為分析過程圖 
2、雙鏈表
雙向鏈表如下圖所示： 
即在單鏈表的每一個(gè)節(jié)點(diǎn)Node結(jié)構(gòu)體上，加多一個(gè)struct Node * 的指針指向上一個(gè)結(jié)構(gòu)體
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：簡化刪除操作，因?yàn)橛鞋F(xiàn)成的指向前一個(gè)指針可以更改指向即可缺點(diǎn)：增大空間需求（代碼量），插入開銷增加一倍，有雙向指針要搞3、循環(huán)鏈表
如下圖所示，即在單（雙）鏈表末端不接NULL，使其返回指向表頭。 如下圖為雙向循環(huán)，同理也有單向循環(huán)。 
4、幾個(gè)栗子
多項(xiàng)式ADT（數(shù)組實(shí)現(xiàn)）//定義多項(xiàng)式組成typedef struct { int CoeffArray[MaxDegree+1]; int HighPower;} * Polynominal;//多項(xiàng)式初始化為0的操作void ZeroPolynominal(Polynominal Poly){ int i; /*系數(shù)全部變?yōu)?*/ for(i=0;i<=MaxDegree;i++) { Poly->CoeffArray[i]=0; } /*最高階為0*/ Poly->HighPower=0;}//多項(xiàng)式相加操作void AddPolynominal(const Polynominal P1,const Polynominal P2,Polynominal Psum){ int i; ZeroPolynominal(Psum); Psum->HighPower=( P1->HighPower > P2->HighPower ?(P1->HighPower):(P2->HighPower) ); for(i=0;i<=Psum->HighPower;i++) Psum->CoeffArray[i]=P1->CoeffArray[i]+P2->CoeffArray[i];}//多項(xiàng)式乘法操作void MultPolynominal(const Polynominal P1,const Polynominal P2,Polynominal Pmult){ int i,j; ZeroPolynominal(Pmult); Psum->HighPower=P1->HighPower+P2->HighPower; if(Psum->HighPower > MaxDegree) /* 容易忽視的地方*/ { printf("Exceed size!"); return -1; } else { for(i=0;i<=P1->HighPower;i++) for(j=0;j<P2->HighPower;j++) Psum->CoeffArray[i+j]+=P1->CoeffArray[i] * P2->CoeffArray[j]; /* 多項(xiàng)式乘法：分分配律乘法 */ }}優(yōu)點(diǎn)：簡單易行，假設(shè)所有階系數(shù)均不為0，對稠密型多項(xiàng)式（即1-N次階系數(shù)均不為0）缺點(diǎn)：對于非稠密型多項(xiàng)式運(yùn)算緩慢
2.多項(xiàng)式ADT（單鏈表實(shí)現(xiàn)）（暫時(shí)不會(huì)。。。） 只有一部分聲明。。
// 鏈表實(shí)現(xiàn)直接不要系數(shù)為0的項(xiàng),且按階數(shù)遞減排序typedef struct Node * PtrToNode;struct Node{ int Coefficient; int Power; PtrToNode Next;};typedef PtrToNode Polynomial;3.桶式排序&基數(shù)（卡式）排序
桶式排序思想：要求N個(gè)整數(shù)排序，且已知范圍為1-M。 步驟： Step1：設(shè)置一個(gè)空數(shù)組count[M]，并初始化為0數(shù)組。 Step2：讀入N個(gè)數(shù)數(shù)列Ai，并有count[Ai]++。循環(huán)完N個(gè)數(shù) Step3：對數(shù)組打印出順序。規(guī)則：從count[0]到count[M]遍歷，在數(shù)組第 i 個(gè)元素處輸出count[M]個(gè)數(shù)字 i基數(shù)排序思想： 對一組數(shù)先計(jì)算數(shù)字最高位數(shù)A。先按個(gè)位排序，之后接著按十位排序，直到按A位排序完。（當(dāng)在某次排序中，兩個(gè)數(shù)的某一個(gè)位數(shù)一致時(shí)，按上一級(jí)原排序，如下面的十位排序時(shí)的125，27排序） 如：一組數(shù)：64，8，216，512，27，729，0，1，343，125。 按個(gè)位排序：0，1，512，343，64，125，216，27，8，729。 接著按十位排序：0，1，8，512，216，125，27，729，343，64。 接著按百位排序：0，1，8，27，64，125，216，343，512，729。4.注冊表 eg：要知道一個(gè)學(xué)校的每個(gè)班的注冊人以及每個(gè)學(xué)生對應(yīng)注冊的班級(jí) 可以利用如下多重表 
5、游標(biāo)
有些編程語言，如Basic等沒有指針，此時(shí)就不能基于指針來寫鏈表了。此時(shí)引入新的ADT”游標(biāo)”來代替指針，且此時(shí)要重寫關(guān)于malloc與free的游標(biāo)形式的函數(shù)。
注意鏈表有以下特性：
因此，游標(biāo)鏈表也應(yīng)該具有以上特點(diǎn)。
游標(biāo)節(jié)點(diǎn)的實(shí)現(xiàn) 在游標(biāo)節(jié)點(diǎn)實(shí)現(xiàn)中，引入數(shù)組實(shí)現(xiàn)，以下為游標(biāo)節(jié)點(diǎn)的例子。 
// Cursor List// _Cursor_H.h#ifndef _Cursor_Htypedef int PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;void InitializeCursorSpace(void);List MakeEmpty(List L);int Isempty(List L);int IsLast(Position P,List L);Position Find(ElementType X,List L);Position FindPrevious(ElementType X,List L);void Delete(ElementType X,List L);void Insert(ElementType X,List L,Position P);void DeleteList(List L);Position Header(List L);Position First(List L);Position Advance(Position P);ElementType Retrieve(Position P);#endif /*_Cursor_H*//* implementation file */#include '_Curvor_H.h'struct Node{ ElementType Element; Position Next; /* data */};struct CurvorSpace[ SpaceSize ]; /*SpaceSize為自定空間*//*相當(dāng)于指針鏈表中的malloc*/static Position CurvorAlloc(void){ Position P; P=CurvorSpace[0].Next; CurvorSpace[0].Next=CurvorSpace[P].Next; return P;}/*相當(dāng)于指針函數(shù) free*/static void CurvorFree(Position P){ CurvorSpace[P].Next=CurvorSpace[0].Next; CurvorSpace.Next=P;}/*剩下游標(biāo)操作函數(shù)的實(shí)現(xiàn)和_List_Function.c里面的差不多List MakeEmpty(List L);int Isempty(List L);int IsLast(Position P,List L);Position Find(ElementType X,List L);Position FindPrevious(ElementType X,List L);void Delete(ElementType X,List L);void Insert(ElementType X,List L,Position P);void DeleteList(List L);Position Header(List L);Position First(List L);Position Advance(Position P);ElementType Retrieve(Position P);*/
