一、定義一個單鏈表

struct LNode{          //定義單鏈表節點類型ElemType data;     //存放節點數據元素struct LNode *next; //指針指向下一個結點
};
//增加一個新節點：在內存中申請一個結點所需空間，并用指針p指向這個結點
struct LNode * p =(struct LNode *)malloc(sizeof(struct LNode));

typedef 關鍵字 —— 數據類型重命名，所以上述代碼還可以寫成：

typedef struct LNode LNode; //struct LNode重命名為LNode
LNode * p =(LNode *)malloc(sizeof(LNode));

書本上的寫法

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;/*
上述寫法與下面寫法等價
*/
struct LNode{ElemType data;struct LNode *next;
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;

這里有一點需要注意：
雖然LNode *和LinkList效果一樣，但是兩者的意義不一樣。

強調這是一個單鏈表——LinkList
強調這是一個結點——LNode *

二、初始化一個單鏈表

1.帶頭結點

帶頭結點：頭指針指向一個節點，這個結點不存放數據，這個結點的next存放指向第一個數據的指針，這樣的節點叫頭結點。

不帶頭結點：頭指針指向的第一個節點就是數據元素結點。

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
//初始化一個單鏈表（帶頭結點）
bool InitList(LinkList &L){L = (LNode *)malloc(sizeof(LNode));//分配一個頭結點if(L==NULL)        //內存不足，分配失敗return false;L->next = null;    //頭結點之后暫時還沒有節點return true;
}
//判斷單鏈表是否為空（帶頭結點）
bool Empty(LinkList L){if(L->next == NULL)return true;elsereturn false;
}
void test(){LinkList L; //聲明一個指向單鏈表的指針InitList(L);//初始化一個空表//......
}

2.不帶頭結點

空表判斷條件

L == NULL

三、單鏈表的插入

（一）按位序插入（帶頭結點）

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//在第i個位子插入元素e
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;LNode *p; //p指向當前掃描到的結點int j=0;  //當前p指向的是第幾個結點p=L;      //L指向頭結點頭結點是第0個結點（不存放數據）/*因為要插入到第i個結點，所以我們只要找到第i-1個結點，然后將結點插入				到第i-1個結點即可。*/while(p!=NULL && j<i-1){ //循環到第i-1個結點p=p->next;j++;}if(p==NULL)   //i值不合法return false;LNode *s=(LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true; //插入成功}

代碼解析：
1.j=0,以i=1為例，不滿足j<i-1,直接跳過循環。

• 第一步，LNode *s=(LNode *)malloc(sizeof(LNode)); 開辟一塊結點內存空間；將e賦給s結點的data域：s->data = e
• 第二步，改變指針指向：s->next = p->next; p->next = s;
  需要注意的是①和②的操作不能顛倒，否則就會導致s結點之后的數據丟失。
  
  2.j=0,以i=3為例，i-1=2，j<i-1，滿足循環條件
• 下面分析一下循環部分的代碼
  ① j=0，j<2，執行p=p->next，滿足循環條件，p向后移動
  
  ②j++=1，j<2，執行p=p->next，滿足循環條件，p向后移動
  
  ③j++=2，不滿足循環條件，跳出循環

之后插入的操作跟上述i=1的操作一樣

• 開辟結點空間，并給結點空間賦值：LNode *s=(LNode *)malloc(sizeof(LNode)); s->data = e;
  
• 改變指針指向：s->next = p->next; p->next = s;
  
  3.如果i=6，當p指向第5個結點時不滿足p!=null（即找不到第i-1個結點），會跳出循環

時間復雜度分析：

• 插入表頭時間復雜度為 O(1)
• 插入到表尾時間復雜度為O(n)
• 平均時間復雜度為O(n)

（二）按位序插入（不帶頭結點）

思路：跟帶頭結點一樣，找到第i-1個結點，然后把結點插入第i-1個結點之后。
需要注意的是，如果不帶頭結點，則插入、刪除第一個元素時，需要更改頭指針。

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
bool ListInsert(LinkList &L,int i,ElemType e){if(i==1){//插入第一個結點操作與其他結點不同LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = L;L=s; //頭指針要指向新的結點return true;}LNode *p;int j=1;//當前p指向的是第幾個結點p=L;    //p指向第一個結點，不是頭結點while(p!=NULL && j<i-1){//循環找到第i-1個結點p=p->next;j++;}if(p==NULL){return false;//i值不合法}LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true; //插入成功}

四、指定結點的插入操作

（一）指定結點的后插操作

//后插操作：在p結點之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){if(p==NULL)return false;s->data = e;s->next = p->next;p->next = s;return true;
}

（二）指定結點的前插操作
思路1：如果要在p的前驅插入一個結點，那就循環查找p的前驅q，再對q后插
但是如果要找到p的前驅就要傳入頭指針。

//前插操作：在p結點之前插入元素e
bool InsertPriorNode(LinkList L,LNode *p,ElemType E){
}

時間復雜度：O(n)
思路2：
新建一個結點，讓這個結點作為p的后繼結點。然后調換一下兩個結點里的數據，這樣需要插入的數據依舊在p的前面，依然可以實現前插操作。

bool InsertPriorNode(LNode *p,ElemType e){if(p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));if(s==NULL)return false;s->next=p->next; p->next=s;       //新結點s連接到p之后s->data=p->data; //p中的元素復制到s中p->data=e;       //p中存放新插入的數據ereturn true;
}

時間復雜度：O(1)

關鍵代碼圖解：

①s->next=p->next; ②p->next=s;

s->data=p->data; p->data=e;

五、刪除

(一)、按位序刪除

刪除表L中第i個位置的元素

思路：如果要刪除第i個元素，那么找到第i-1個元素，讓其指向第i+1個元素，再把第i個元素的空間釋放掉。

//帶頭結點
bool ListDelete(LinkList &L,int i,ElemType &e){if(i<1)return false；LNode *p;//p指向當前掃描的結點int j=0; //當前p指向的是第幾個結點p=L;     //L指向頭結點，頭結點是第0個結點（不存放數據）while(p!=NULL && j<i-1){//循環找到第i-1個結點p=p->next;j++;}if(p==NULL)   //i值不合法return false;if(p->next==NULL) //第i-1個結點之后已無其他結點return false;LNode *q=p->next; //q指向被刪除的結點e=q->data;        //用e返回被刪除的元素的值p->next=q->next;  //被刪除的結點從鏈表中斷開free(q);          //釋放結點的存儲空間return true;      //刪除成功
}

最壞、平均時間復雜度：O(n)
最好時間復雜度：O(1)

（二）、指定結點刪除

同樣的道理，如果不傳入頭指針，那就找不到指定指定結點的前驅結點。

那如果在不傳入頭指針的情況下該怎么刪除呢？我們想到一個辦法：把p的后繼結點的數據域賦給p,然后再把p的后繼結點q所指向的空間釋放掉。

//刪除指定結點p
bool DeleteNode(LNode *p){if(p==NULL)return false;LNode *q=p->next;//q指向p的后繼結點p->data=p->next->data;//和后繼結點交換數據域p->next=q->next;free(q);return true;}

①初始狀態，LNode *q=p->next;

②交換數據域，p->data=p->next->data;

③改變指針指向，p->next=q->next;，最后再釋放q所指向的空間，free(q);

注意：如果要刪除的是最后一個結點的話，q會指向null，這時候只能采用傳入頭指針遍歷，找到前驅結點的辦法來刪除。