第一章 鏈表

何謂鏈表

我們知道，一般用數組存放一組數據時，必須事先定義固定的長度（即元素個數）。這在某些問題的解決中，并不是特別的適用。例如，記錄不同班級的學生數據時，由于各班人數不同，會出現開辟過大的數組導致內存浪費、開辟過小的數組導致數組元素不夠用的情況。而鏈表可以根據需要動態開辟內存單元，是一種常見的重要數據結構。圖1.1所示為最簡單的一種鏈表結構。

圖1.1

鏈表如同鐵鏈一樣，一環扣一環，中間是不能斷開的。打個通俗的比方：幼兒園老師帶領小朋友出來散步，老師牽著第一個小朋友的手，第一個小朋友的手牽著第二個小朋友的手……這就是一個“鏈”，最后一個小朋友的手是空的。

老師即“頭指針”變量，圖1.1中以Head表示，它存放一個地址。鏈表中每一個元素稱為“結點”，每個結點都應該包括兩部分：一為實際元素值，一為下一結點的地址。

最后一個元素不指向其他元素，它被稱為“表尾”，以“NULL”表示，“NULL”在C++語言里指向“空地址”。

很顯然，這種鏈表的數據結構，必須要用指針變量才能實現。