喜歡《數據結構》部分筆記的小伙伴可以訂閱專欄，今后還會不斷更新。
此外，《程序員必備技能》專欄和《程序員必備工具》專欄（該專欄暫未開設）日后會逐步更新，

插入

按位序插入

（1）帶頭結點

ListInsert(&L, i, e)插入操作——在表L中的第i個位置上插入指定元素e
找到第i-1個結點，將新結點插入其后
具體代碼實現：

//在第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個結點（不存數據）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;//將結點s連到p之后return true;//插入成功
}

代碼分析：

• 如果i=1（插在表頭）
• 如果i=3，那么i-1=2，那么j=0，p會指向下個結點，所以j=1，因為j=1 < 2，所以j會再+1變成2
• 如果i=5（插在表尾），這種情況是最壞的，最壞時間復雜度=$O(n)$
• 如果i=6（i>length），執行之后發現p == NULL，返回false
  需要注意的是：
  s->next = p->next;和p->next = s;兩句順序不能顛倒

（2）不帶頭結點

ListInsert(&L, i, e)插入操作——在表L中的第i個位置上插入指定元素e
找到第i-1個結點，將新結點插入其后
但是因為不存在所謂的“第0個”結點，因此當i=1時需要進行特殊處理
具體代碼實現：

bool ListInsert(LNode &L, int i, ElemType e){if(i>1)return false;if(i==1){//插入第一個結點的操作和其他結點的操作不同LNode *s = (LNode *) malloc (sizeof(LNode));s->data = e;s->next = L;L = s;//頭指針指向新結點return true;}LNode *p;//指針p指向當前掃描到的結點int j = 1;//當前p指向的是第幾個結點p = L;//p指向第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;//插入成功
}

代碼分析：

• i=1時，如果單鏈表不帶頭結點，則插入、刪除第1個元素時，需要修改頭指針L
• i>1時，這種情況和帶頭結點的情況是一樣的，唯一需要注意的是：我們修改了int j = 1

指定結點的后插操作

//后插：在p結點之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){if(p == NULL)return false;LNode *s = (LNode *) malloc (sizeof(LNode));if(s == NULL)return false;s->data = e;//用結點s保存元素es->next = p->next;p->next = s;//將結點s連到p之后return true;
}

指定結點的前插操作

//前插：在p結點之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e)

前插的困難在于，單鏈表只能往后查找結點，對于給定的結點p，之前有哪些結點都是未知的
那么如何操作呢？我們可以傳入頭指針

bool InsertPriorNode(LinkList L, LNode *p, ElemType e)

傳入頭指針之后，通過循環的方式查找p的前驅結點q，然后再對q進行后插操作，并且通過這種方式操作時，時間復雜度為$O(n)$

---

但是還有另一種實現方式：

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)$

---

王道書版本：

bool InsertPriorNode(LNode *p, LNode *s){if(p == NULL || s == NULL)return false;s->next = p->next;p->next = s;               //s連到p之后ElemType temp = p->data;   //交換數據部分p->data = s->data;s->data = temp;return true;
}

代碼分析：

1. p->data: 訪問指針p所指向的結點的data成員
2. ElemType temp: 聲明一個類型為ElemType的局部變量temp。ElemType通常是一個自定義的類型（例如int、float、結構體等），它表示結點中存儲的數據類型
3. temp = p->data: 將p->data的值賦值給temp

ElemType temp = p->data; // 將 p 結點的 data 值存儲到 temp 變量中
p->data = s->data;       // 將 s 結點的 data 值賦值給 p 結點的 data
s->data = temp;          // 將 temp 中保存的原 p 結點的 data 值賦值給 s 結點的 data

通過以上步驟，p和s之間的data值就被交換了，但結點本身的位置沒有改變。這樣做的目的是為了在邏輯上實現插入前驅結點的效果。

刪除

按位序刪除

只探討帶頭結點的情況：
ListDelete(&L, i, &e)刪除操作——刪除表L中第i個位置的元素，并用e返回刪除元素的值
找到第i-1個結點，將其指針指向第i+1個結點，并釋放第i個結點
頭結點可以看做“第0個”結點
具體代碼實現：

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;            //將 *q 結點從鏈中斷開free(q);                      //釋放結點的存儲空間return true;
}

代碼分析：

• 在這部分代碼中：
  • LNode *q = p->next;： q 指向要刪除的第 i 個結點
  • e = q->data;： 將被刪除結點的數據存儲在 e 中
  • p->next = q->next;： 這是關鍵的一步，將 p 的 next 指針指向 q 的后繼結點，從而將 q 結點從鏈表中斷開。具體來說，p->next 本來指向 q，現在改為指向 q 的后繼結點 q->next
  • free(q);： 釋放 q 結點的內存。
• 我們來更詳細地解釋 p->next = q->next; 的意義：
  • 在這條語句之前，鏈表的鏈接是這樣的：
    p --> q --> q->next
  • 執行這條語句后，鏈表的鏈接變成了這樣：
    p -> q->next
  • 這樣，q 結點就從鏈表中被移除了
• 平均、最壞時間復雜度：$O(n)$，最好時間復雜度：$O(1)$

指定結點的刪除

//刪除指定結點p
bool DeleteNode(LNode *p)

刪除結點p，需要修改其前驅結點的next指針
解決方法：

1. 傳入頭指針，循環尋找 p 的前驅結點
2. 偷天換日（類似于結點前插的實現）

bool Delete(LNode *p){if(p == NULL)return false;LNode *q = p->next;       //令q指向*p的后繼結點p->data = p->next->data;  //和后繼結點交換數據域p->next = q->next;        //將*q結點從鏈中斷開free(q);                  //釋放后繼結點的存儲空間return true;
}

讓p->next指向 q 結點的后繼結點（可能是NULL），這個時候 q 結點就被斷開了，釋放存儲空間即可
時間復雜度：$O(1)$
但是，如果 p 是最后一個結點，這一段代碼是有 bug 的。這種情況下，我們只能從頭開始依次尋找 p 的前驅
時間復雜度：$O(1)$

單鏈表的局限性

無法逆向檢索，有時候不太方便。如果有指向前面的指針，情況就不一樣了
這種表就是雙鏈表