由于順序表的插入，刪除操作需要移動大量的元素，影響了運算效率，由此線性表的鏈式存儲便應運而生。鏈式存儲線性表時，邏輯上連續的元素物理結構上不需要連續，它們彼此可以通過“鏈”建立起數據元素之間的邏輯關系，因此對于線性表的插入，刪除操作并不需要移動元素，只需修改指針即可。 ## 一.單鏈表的定義 線性表的鏈式存儲又稱為單鏈表，它是通過一組任意的存儲單元來存儲線性表中的數據元素。為了建立起數據元素之間的線性關系，對每個鏈表結點，除了存放元素自身的信息外，還需要存放一個指向其后繼的指針。 單鏈表結點的結構如下圖所示，其中，data為數據域，存放數據元素；next為指針域，存放其后繼結點的地址。  對于每一個結點的描述如下： ~~~ typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; ~~~ 利用單鏈表在解決順序表需要大量的連續存儲空間的缺點的同時，也引入了一些不可避免的缺點。比如因為需要額外的指針域，因此需要額外的存儲空間；由于單鏈表是離散的分布在存儲空間中，所以單鏈表不能完成隨機存取的操作。 為了方便標識一個單鏈表，我們一般需要引入頭指針來操作整個單鏈表。此外，為了統一增加和刪除元素的操作，我們一般會在單鏈表的第一個結點之前附加一個結點，稱為頭結點。頭結點的指針域指向單鏈表的第一個元素結點。 注：這里應該注意區分頭指針和頭結點。而不管單鏈表有沒有頭結點，頭指針總是指向單鏈表的第一個結點。簡單說就是如果單鏈表有頭結點，那么頭指針將指向頭結點；如果單鏈表沒有頭結點，頭指針將指向單鏈表的第一個結點。此處我們應該注意到一般情況下頭結點內不存儲任何信息。這里說明下，如果后面的例題中沒有具體說明，一般都是建立有頭結點的單鏈表。  引入頭節點后，可以帶來兩個優點： - 由于開始節點的位置被存放在頭節點的指針域中，所以在鏈表的第一個位置上操作與表其他位置上的操作一致，無需進行特殊處理。 - 無論鏈表是否為空，其頭指針都是指向頭節點的非空指針（在空表中，頭節點的指針域為空），因此也使得空表和非空表的處理方式變得統一。 ## 二.單鏈表基本操作的實現 ### 2.1建立單鏈表 ### 2.1.1頭插法建立單鏈表 該方法中，首先建立一個具有頭結點的空單鏈表，然后每生成一個讀取到數據的新節點，就將其放置到頭結點之后。如下圖所示：  算法描述如下： ~~~ typedef int ElemType; LinkList CreateLink(LNode *head) { LNode *s; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=head->next; head->next=s; scanf("%d",&x); } return head; } ~~~ 注：采用頭插法建立單鏈表，讀入數據的順序與生成的鏈表中的元素的順序剛好是相反的。 每個結點插入的時間復雜度為O(1)，設單鏈表長為n，則總的時間復雜度為O(n)。 ### 2.1.2尾插法建立單鏈表 該方法中同樣首先建立一個具有頭結點的空單鏈表，然后每生成一個讀取到數據的新節點，就將它插入到表尾；為了達到這樣的目的，必須增加一個尾指針r，使其始終指向當前鏈表的尾結點。如下圖所示  算法描述如下 ~~~ LinkList CreatLink(LNode *head) { LNode *s; LNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } s->next=NULL; return head; } ~~~ 注：因為附加設置了一個指向表尾的尾指針r，因此每個結點插入的時間復雜度同樣為O(1)，設單鏈表長為n，則總的時間復雜度為O(n)。 ### 2.2按序號查找結點值 從單鏈表的第一個結點出發，順著指針next域逐個從上往下搜索，直到找到第i個結點為止，否則返回最后一個結點指針域NULL。 算法描述如下： ~~~ LNode* GetElem(LNode *head, ElemType i) { LNode *p=head->next; int j=1; if(i==0){ printf("The Link is empty!\n"); return head; } if(i<=0){ printf("The postion is illegal!\n"); return NULL; } while(p){ if(j==i){ printf("Find success!\n"); break; } p=p->next; j++; } return p; } ~~~ 注：按序號查找的時間復雜度為O(n)。 ### 2.3按值查找結點值 從單鏈表的第一個結點開始，由前往后依次比較各結點數據域的值，若某結點數據域的值等于給定值x，則返回該結點的指針。若整個單鏈表中沒有這樣的結點，則返回NULL。 算法描述如下： ~~~ LNode* GetElem(LNode *head, ElemType x) { LNode *p=head->next; if(head==NULL){ printf("The LinkList is empty!\n"); return head; } while(p){ if(p->data==x){ printf("Find the number!\n"); return p; } p=p->next; } printf("Not Find the number!\n"); return NULL; } ~~~ 注：按值查找的時間復雜度為O(n)。 ### 2.4插入結點 ### 2.4.1插入后繼結點 插入操作是將值為x的新結點插入倒單鏈表的第i個位置上。先檢查插入位置的合法性，然后找到待插入位置的前驅結點，即第i?1個結點，再在其后插入新的結點。 算法首先需要調用`GetElem(L,i-1)`查找第i?1個結點。假設返回的第i?1個結點為*p，然后令新結點*s的指針域指向*p的后繼結點，再令結點*p的指針域插入新的結點*s。其操作過程如下圖所示：  算法描述如下： ~~~ LNode* GetElem(LNode *head, int i) { if(i==0){ printf("The LinkList is empty!\n"); return head; } if(i<=0){ printf("The LinkList is illegal!\n"); return NULL; } LNode *p=head->next; int j=1; while(p){ if(j==i){ printf("Find it!The postion is %dth\n", j); break; } j++; p=p->next; } return p; } void InertElem(LNode *p, ElemType x){ LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=p->next; p->next=s; } ~~~ 算法中，時間的主要開銷是查找第i?1個元素，時間復雜度為O(n)。若是在給定的結點后面插入新結點，則時間復雜度僅為O(1)。 ### 2.4.1插入前驅結點 在方法一中，我們可以在指針p指向的結點后面插入新的結點s，但是有時如果我們需要在指針p指向的結點前面插入新的結點s時，上述算法明顯是辦不到的。 但是如果我們換個思路，將指針p指向的結點和s結點它們之間的數據域做一次交換，依舊將s結點插入到指針p指向的結點后面，如此我們便將前插操作變為了向指針p指向的結點的后插操作，并且在邏輯上仍舊滿足條件。 算法描述如下： ~~~ void InertElem(LNode *p, ElemType x){ LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; ElemType temp; temp=p->data; p->data=s->data; s->data=temp; s->next=p->next; p->next=s; } ~~~ 注：同方法一相同，時間的主要開銷是查找第i?1個元素，時間復雜度為O(n)。若是在給定的結點后面插入新結點，則時間復雜度僅為O(1)。 ### 2.5刪除結點 #### 2.5.1刪除后繼結點 刪除結點操作即將單鏈表的第i個結點刪除。先檢查刪除位置的合法性，然后查找表中第i?1個結點（即將要被刪除結點的前驅結點），然后在刪除第i個結點。其操作過程如下圖所示：  假設我們要刪除指針q指向的結點，那么我們首先通過遍歷所有結點找到指針q指向的結點的前驅結點p，為了實現算法，我們只需修改指針p的指針域，將指針p的指針域next直接指向指針q指向的結點的指針域next所指的下一個結點便可。 算法描述如下： ~~~ void DelLNode(LNode *head, int i) { LNode *p=head; LNode *q=head->next; while(i){ p=q; q=q->next; i--; } p->next=q->next; free(q); } ~~~ 注：刪除操作中，時間的主要開銷是查找第i?1個元素，因此時間復雜度為O(n)。若是刪除給定結點的后繼結點，則時間復雜度為O(1)。 #### 2.5.2刪除自身結點 有時我們需要刪除指針所指向的自身結點（比如指針p指向的結點），此時如果繼續使用上述方法明顯是不可能的。我們采用與`2.4.1插入前驅結點`相似的方法，將指針p所指向的結點的數據域與指針q所指向的結點的數據域進行一次交換（因為是一次刪除操作，我們只需要將指針q指向的結點的數據域直接賦值為指針p指向的結點的數據域便可），這樣，我們就又變成了刪除指針q指向的結點的操作。 算法描述如下： ~~~ void DelList(LNode *head, int i) { LNode *p=head; LNode *q=p->next; while(i){ p=q; q=q->next; i--; } p->data=q->data; p->next=q->next; free(q); } ~~~ 注：與上述算法一樣，刪除操作中，時間的主要開銷是查找第i個元素，因此時間復雜度為O(n)。若是刪除給定的結點，則時間復雜度為O(1)。 ### 2.5求鏈表長度 求表長實際上就是計算單鏈表中數據結點（不含頭節點）的個數。為了達到這個目的，我們只需對鏈表進行一次遍歷，同時設置計數器對每次訪問到的結點計數便可。 算法描述如下： ~~~ int LenLink(LNode *head) { int cnt=0; LNode *p=head->next; while(p){ p=p->next; cnt++; } return cnt; } ~~~ 注：遍歷操作中需要訪問所有結點，因此時間復雜度為O(n)。