靜態(tài)鏈表

用數(shù)組描述的鏈表叫做靜態(tài)鏈表；

數(shù)組的元素由兩部分組成， data和cur， data存儲數(shù)據(jù)；cur存儲該元素的后繼在數(shù)組中的下標（類似單鏈表中的next指針）；
數(shù)據(jù)元素類似下面結(jié)構(gòu)體

typedef struct{
ElemType data; 
int cur;
} Componet,StaticLinkList[MAXSIZE];

備用鏈表

• 數(shù)組中未使用的數(shù)組元素；
• 數(shù)組的第一個元素，即下標為0的元素的cur就存放備用鏈表的第一個結(jié)點下標，而數(shù)組的最后一個元素的cur 則存放第一個有數(shù)值的元素的下標，相當于單鏈表中的頭結(jié)點的作用，當鏈表為空時，為0；

靜態(tài)鏈表的插入操作

如下圖所示；

初始鏈表

插入操作

將丙插入乙和丁之間；

• 將元素丙添加到備用鏈表；
• 將乙的cur 改為 丙的游標；
• 將丙的cur 改為 丁的游標；

靜態(tài)鏈表的優(yōu)缺點；

1、優(yōu)點

• 在插入和刪除操作時，只需要修改游標，不需要移動元素，從而改進了在順序存儲結(jié)構(gòu)中的插入和刪除操作需要移動大量元素的缺點；

2、缺點

• 沒有解決連續(xù)存儲分配帶來的表長難以確定的問題；
• 失去了順序存儲結(jié)構(gòu)隨機存取的特性；

循環(huán)鏈表

將單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點，就使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表；簡稱循環(huán)鏈表；

• 尾指針： rear；
• 開始結(jié)點： rear->next->next;

雙向鏈表

在單向鏈表的每個鏈表結(jié)點中

每一個鏈表元素結(jié)構(gòu)類似下面

typedef struct{
ElemType data;
struct DuLNode *prior   /* 直接前驅(qū)指針*/;
struct DuLNode  *next;  /*直接后驅(qū)指針 */
}DuLNode, *DuLinkList

非空的循環(huán)帶頭結(jié)點的雙向鏈表

雙向鏈表的插入操作

假設(shè)存儲元素e的結(jié)點為s，要實現(xiàn)將結(jié)點s插入到結(jié)點p與p->next之間；
算法思路：

s->prior = p;  /*把p賦值給s的前驅(qū)*/
s->next = p->next; /*把p->next賦值給s->next*/
p->next->prior = s; /*將s賦值給p->next的前驅(qū)*/
p->next = s; /*將s賦值給p->next*/

雙向鏈表的刪除操作

p->prior->next = p->next;   /*把p->next 賦值給p->prior的后繼*/
p->next->prior = p->prior;  /*把p->prior賦值給p->next 的前驅(qū)*/
free(p);