深刻了解：帶頭結點和不帶頭結點的差別 使用頭結點的優勢

一、概念辨析

線性表的插入删除需要移動大量的元素，是以引傳入連結表（本文讨論單連結清單）的概念，連結清單元素之間通過“鍊”來連結，是以插入和删除時不需要大量的移動元素，而隻需要改變“鍊”的關系即可。

• 頭指針：通常使用“頭指針”來辨別一個連結清單，如單連結清單L，頭指針為NULL的時表示一個空連結清單。
• 頭結點：在單連結清單的第一個結點之前附加一個結點，稱為頭結點。頭結點的Data域可以不設任何資訊，也可以記錄表長等相關資訊。

[注意]無論是否有頭結點，頭指針始終指向連結清單的第一個結點。如果有頭結點，頭指針就指向頭結點。

二、引入頭結點的優勢

剛剛提到，連結清單可以沒有頭結點，但是必須要有頭指針，因為要用頭指針來辨別一個連結清單。設連結清單的頭指針為pHead。除了頭結點之外，還需要一個指向連結清單一般元素的指針pNode（因為pHead隻能指向表頭，不能指向其他元素，故需要另設指針）。

優勢1：第1個位置的插入删除更加友善

若使用頭結點，則第1個位置的插入和删除都是對p—>next進行操作，而不用動p本身，而且減少了算法分支（即if else分支）具體的流程為：

插入操作如下

1. p指向要插入結點的前驅結點，若要插入的結點為第1個位置，則其前驅結點就是頭結點，此時p指向頭結點。
2. 讓新結點s的next指向p的next，即s—>next = p—>next;
3. 讓p—>next指向s，即p—>next = s;

删除操作如下

1. p指向要删除結點的前驅結點，若要删除的結點為第1個位置，則其前驅結點就是頭結點，此時p指向頭結點。
2. 讓臨時指針q指向要删除的結點，即q = p—>next；
3. 讓p的next指向要删除結點的下一個結點，即p—>next = q—>next；
4. 釋放q的空間，即free(q);

1. 判斷要插入的是否是第1個位置，若是需要特殊處理。
2. 若是第1個位置，讓新結點s的next指向頭指針PtrL。
3. return s，此時s作為連結清單的頭指針。此時的更新了連結清單的頭指針。
4. 若不是第1個位置，首先找到要插入結點的前驅結點，讓p指向這個前驅結點。
7. return PtrL，此時PtrL還是作為連結清單的頭指針，沒有被修改，但考慮到一緻性需要這樣寫。

1. 判斷要删除的是否是第1個位置，若是需要特殊處理。
2. 若是第1個位置，讓s指向要删除的結點。首先判斷PtrL是否為空，若是直接return NULL;若不為空，則将連結清單的頭結點挪到下一個位置，即PtrL = PtrL—>next；
3. free(s);然後return PtrL
4. 若不是第1個位置，首先找到要删除結點的前驅結點，讓p指向這個前驅結點。
8. return PtrL

優勢2:統一空表和非空表的處理