單鏈表是一種線性資料結構， 與順序表佔據一段連續的記憶體空間不同， 鏈表是用一組位址任意的存儲單元來存儲資料， 每個存儲單元分散在記憶體的任意位址上， 存儲單元之間用指標連接。 在鏈表中， 每個資料元素都存放到鏈表的一個結點 ， 結點之間由指標串聯在一起， 這樣就形成了一條如同“鏈”的結構， 故稱作鏈表。
通過下面的代碼可定義一個單鏈表：
typedef struct node{
ElemType data; //資料欄
struct node * next; //指針域
} LNode,*LinkList;
其實上面這段代碼定義的是一個單鏈表的結點。 每一個結點包括兩部分：資料欄和指針域。 其中資料欄用來存放資料元素本身的資訊，
上面使用typedef將結構體struct node定義為LNode類型， 表示鏈表中每個結點的類型為LNode， 它等價於結構體類型struct node。 另外， *LinkList是指向LNode類型的指標類型， 當定義一個指向LNode類型資料的指標變數時， LNode *L與LinkList L是等價的。
一個鏈表只要得到了頭指標就可以操作鏈表上的每一個結點， 因此把LinkList類型抽象地看作是單鏈表類型。 也就是說， 只要得到了LinkList類型的鏈表頭結點指標， 就可以操作整個單鏈表。
單鏈表的操作包括單鏈表的創建、結點插入、刪除、鏈表銷毀等， 下以的實例就包括了這些方面的操作。
先看運行效果：
代碼：
對於線性表（順序表和單鏈表）的遍歷， 注意指標移動的細微區別。 在順序表中， 申請一個指標p後， p指示資料元素的存儲位置， 用*p可取得該資料的值， 用p++可以順序進到物理上下一個元素的位置。 在單鏈表的情形下， 指針p指示鏈表的結點位址， 用*p不能取得該結點數據的值， 用p++也不能進到下一個結點位置， 只能使用p->data取得結點數據的值， 用p=p->next進到下一個結點。
結點元素的插入，分為兩種情況：
I 插入到單鏈表的最前面：
II 插入到中間位置:
結點元素的刪除，也分兩種情況：
如果是刪除頭節點，只需要將將頭節點的next指針賦值給單鏈表指針即可：*list = q->next;
如果是刪除中間位置的節點：
源碼：
#include "stdio.h"
#include "malloc.h"
typedef struct node{
int data;
struct node *next;
}LNode,*LinkList;
LinkList GreatLinkList(int n)
{
/*建立一個長度為n的鏈表*/
LinkList p, r, list = NULL;
int e;
int i;
for (i=1;i<=n;i++){
printf("請輸入第%d個結點值（共%d）個：",i,n);
scanf("%d",&e);/*獲取鏈表結點中的資料元素*/
p=(LinkList)malloc(sizeof(LNode));/*分配一個新的鏈表結點*/
p->data=e;
p->next=NULL;
if (list == NULL) {
list = p;/*list指向第一個結點，list是頭指標*/
} else {
r->next = p;/*將新結點連接到鏈表的尾部*/
}
r = p;/*指標r始終指向鏈表的最後一個結點*/
}
return list;/*返回鏈表的頭指針*/
}
void insertListInOrder(LinkList *list,int e)
{
/*向按值有序(遞增序列)的鏈表list中插入包含元素e的結點*/
LinkList p, q, r;
q = *list;
p=(LinkList)malloc(sizeof(LNode));/*生成一個新結點，由p指向它*/
p->data=e;/*向該結點的資料欄賦值e*/
if (*list == NULL || e < (*list)->data) {
p->next = *list;
*list = p;
} else {
while(q != NULL && e >= q->data) {/*迴圈找到插入結點的位置*/
r = q;/*r指向q的前驅結點*/
q = q->next;/*q指標向後移動*/
}
p->next= q; /*插入新的結點*/
r->next = p;
}
}
void delLink(LinkList *list, LinkList q) {
LinkList r;
if (q == *list) {
*list = q->next;/*如果q指向的結點即為第1個結點，則需要修改list的值*/
free(q);/*釋放被刪除結點的空間*/
} else {
r = *list;
while ((r->next != q)&&(r->next != NULL)) {
r = r->next;/*通過迴圈找到q所指結點的前驅結點*/
}
if (r->next != NULL) {
r->next = q->next;/*刪除q所指向的結點*/
free(q);/*釋放被刪除結點的空間*/
}
}
}
void deleteLinkList(LinkList *list) {
LinkList p = *list;/*p指向第一個結點*/
while (p != NULL) {
*list = p ->next;/* list指向p的下一個結點 */
free(p);/*釋放掉p指向結點的記憶體空間*/
p = *list;/*p再指向第一個結點*/
}
}
void printLink(LinkList list) {
while (list != NULL) {
printf("%3d",list->data);/*列印出每個結點中的資料data*/
list = list->next;
}
printf(" ");
}
void main() {
int i;
LinkList q,list = NULL;
list = GreatLinkList(10); /*創建一個長度為10的鏈表*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("插入元素3 ");
insertListInOrder(&list,3);/*插入元素3*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("插入元素0 ");
insertListInOrder(&list,0);/*插入元素0*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("插入元素11 ");
insertListInOrder(&list,11);/*插入元素10*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("刪除鏈表中的第5個元素： ");
q=list;
for (i=0; i<4; i++) {
q = q->next;/*指標q指向鏈表中第5個元素*/
}
delLink(&list, q);/*刪除q指向的結點*/
printLink(list);/*列印出鏈表中的內容*/
deleteLinkList(&list);/*銷毀該鏈表*/
if (list == NULL) {
printf( " This Linklist have been deleted ");
}
system("pause");
}
－End－
結點元素的插入，分為兩種情況：
I 插入到單鏈表的最前面：
II 插入到中間位置:
結點元素的刪除，也分兩種情況：
如果是刪除頭節點，只需要將將頭節點的next指針賦值給單鏈表指針即可：*list = q->next;
如果是刪除中間位置的節點：
源碼：
#include "stdio.h"
#include "malloc.h"
typedef struct node{
int data;
struct node *next;
}LNode,*LinkList;
LinkList GreatLinkList(int n)
{
/*建立一個長度為n的鏈表*/
LinkList p, r, list = NULL;
int e;
int i;
for (i=1;i<=n;i++){
printf("請輸入第%d個結點值（共%d）個：",i,n);
scanf("%d",&e);/*獲取鏈表結點中的資料元素*/
p=(LinkList)malloc(sizeof(LNode));/*分配一個新的鏈表結點*/
p->data=e;
p->next=NULL;
if (list == NULL) {
list = p;/*list指向第一個結點，list是頭指標*/
} else {
r->next = p;/*將新結點連接到鏈表的尾部*/
}
r = p;/*指標r始終指向鏈表的最後一個結點*/
}
return list;/*返回鏈表的頭指針*/
}
void insertListInOrder(LinkList *list,int e)
{
/*向按值有序(遞增序列)的鏈表list中插入包含元素e的結點*/
LinkList p, q, r;
q = *list;
p=(LinkList)malloc(sizeof(LNode));/*生成一個新結點，由p指向它*/
p->data=e;/*向該結點的資料欄賦值e*/
if (*list == NULL || e < (*list)->data) {
p->next = *list;
*list = p;
} else {
while(q != NULL && e >= q->data) {/*迴圈找到插入結點的位置*/
r = q;/*r指向q的前驅結點*/
q = q->next;/*q指標向後移動*/
}
p->next= q; /*插入新的結點*/
r->next = p;
}
}
void delLink(LinkList *list, LinkList q) {
LinkList r;
if (q == *list) {
*list = q->next;/*如果q指向的結點即為第1個結點，則需要修改list的值*/
free(q);/*釋放被刪除結點的空間*/
} else {
r = *list;
while ((r->next != q)&&(r->next != NULL)) {
r = r->next;/*通過迴圈找到q所指結點的前驅結點*/
}
if (r->next != NULL) {
r->next = q->next;/*刪除q所指向的結點*/
free(q);/*釋放被刪除結點的空間*/
}
}
}
void deleteLinkList(LinkList *list) {
LinkList p = *list;/*p指向第一個結點*/
while (p != NULL) {
*list = p ->next;/* list指向p的下一個結點 */
free(p);/*釋放掉p指向結點的記憶體空間*/
p = *list;/*p再指向第一個結點*/
}
}
void printLink(LinkList list) {
while (list != NULL) {
printf("%3d",list->data);/*列印出每個結點中的資料data*/
list = list->next;
}
printf(" ");
}
void main() {
int i;
LinkList q,list = NULL;
list = GreatLinkList(10); /*創建一個長度為10的鏈表*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("插入元素3 ");
insertListInOrder(&list,3);/*插入元素3*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("插入元素0 ");
insertListInOrder(&list,0);/*插入元素0*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("插入元素11 ");
insertListInOrder(&list,11);/*插入元素10*/
printf("The elems of this linklist is ");
printLink(list); /*列印出鏈表的內容*/
printf("刪除鏈表中的第5個元素： ");
q=list;
for (i=0; i<4; i++) {
q = q->next;/*指標q指向鏈表中第5個元素*/
}
delLink(&list, q);/*刪除q指向的結點*/
printLink(list);/*列印出鏈表中的內容*/
deleteLinkList(&list);/*銷毀該鏈表*/
if (list == NULL) {
printf( " This Linklist have been deleted ");
}
system("pause");
}
－End－