線性鍊表

具有連結存儲結構的線性表，它用一組地址任意的存儲單元存放線性表中的數據元素，邏輯上相鄰的元素在物理上不要求也相鄰，不能隨機存取。一般用結點描述：結點（表示數據元素） =數據域（數據元素的映象） + 指針域（指示後繼元素存儲位置）

概念

在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關係可以不一致，而數據元素之間的邏輯關係是由指針域來確定的。鏈式存儲方式即可以用於表示線性結構，也可用於表示非線性結構。

一般來說，線上性表的鏈式存儲結構中，各數據結點的存儲符號是不連續的，並且各結點在存儲空間中的位置關係與邏輯關係也不一致。對於線性鍊表，可以從頭指針開始，沿各結點的指針掃描到鍊表中的所有結點。

實現

(1) 線性表的操作GetElem(L, i, &e)在鍊表中的實現:
基本操作為: 使指針p始終指向線性表中第j個數據元素
Status GetElem_L(LinkList L, int i, ElemType &e)// L為帶頭結點的單鍊表的頭指針。當線性表中存在第i個元素時，則將第i個數據元素的值賦給e並返回OK，否則返 回ERROR

{p = L->next; j = 1; // 初始化，p指向第一個結點，j為計數器

while (p && j); // 順指針向後查找，直到p指向第i個元素或p為空

p = p->next; ++j; }

if ( !p || j>i ) return ERROR; // 第i個元素不存在
e = p->data; // 取第i個元素
return OK;
} // GetElem_L算法的時間複雜度為:O(ListLength(L))
(2) 線性表的操作ListInsert(&L, i, e)在鍊表中的實現:

基本操作為: 找到線性表中第i-1個結點，修改其指向後繼的指針

有序對<a_i-1, a_i> 改變為 <a_i-1, e> 和 <e, a_i>

Status ListInsert_L(LinkList L, int i, ElemType e) {
// 在帶頭結點的單鍊表L中第i個數據元素之前插入數據元素e
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 尋找第i-1個結點
if (!p|| j > i-1) return ERROR; // i小於1或者大於表長
s = (LinkList) malloc (sizeof (LNode)); // 生成新結點
s->data = e; s->next = p->next; // 插入L中
p->next = s;
return OK;
} // LinstInsert_L算法的時間複雜度為:O(ListLength(L))

(3) 線性表的操作ListDelete(&L, i, &e)在鍊表中的實現：

基本操作為: 找到線性表中第i-1個結點，修改其指向後繼的指針

有序對<a_i-1, a_i> 和 <a_i, a_i+1> 改變為<a_i-1, a_i+1>

Status ListDelete_L(LinkList L, int i, ElemType &e)

{ p = L; j = 0;} // 在帶頭結點的單鍊表L中，刪除第i個元素，並由e返回其值

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; free(q);
return OK;
} // ListDelete_L算法的時間複雜度為:O(ListLength(L))

單鏈線性表

線上性表的連結存儲中，為了方便在表頭插入和刪除結點的操作，經常在表頭結點（存儲第一個元素的結點）的前面增加一個結點，稱之為頭結點或表頭附加結點。這樣原來的表頭指針由指向第一個元素的結點改為指向頭結點，頭結點的數據域為空，頭結點的指針域指向第一個元素的結點。
定義一個帶頭結點的線性鍊表類型：
typedef struct LNode // 結點類型

{
ElemType data;
struct LNode *next;
} *Link,*Position;
typedef struct // 鍊表類型
{ Link head, tail; // 指向頭結點和最後一個結點
int len; // 指示鍊表長度
Link current; // 指向當前訪問的結點的指針，初始位置指向頭結點
}

LinkList;
Status MakeNode( Link &p, ElemType e );
// 分配由p指向的值為e的結點，並返回OK；若分配失敗，則返回ERROR
void FreeNode( Link &p ); // 釋放p所指結點

創建帶頭結點的單鏈線性表：

void CreateList_L(LinkList&L, int n) // 逆位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L。

{ L = (LinkList) malloc (sizeof (LNode));
L->next = NULL; // 先建立一個帶頭結點的單鍊表
for (i = n; i > 0; --i) {
p = (LinkList) malloc (sizeof (LNode)); // 生成新結點
scanf(&p->data); // 輸入元素值
p->next = L->next; L->next = p; // 插入到表頭
}
} // CreateList_L算法的時間複雜度為:O(Listlength(L))