數據結構-鏈表

鏈表是一種物理存儲單元上非連續、非順序的存儲結構。

數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。

每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。

相比于線性表順序結構，鏈表比較方便插入和刪除操作。

鏈表最明顯的好處就是，常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序，數據的存取往往要在不同的排列順序中轉換。

而鏈表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（鏈接）。

鏈表還有幾種常用的類型：

單鏈表，雙鏈表，循環鏈表

雙向鏈表其實是單鏈表的改進。

當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。

這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后繼結點地址的鏈域，那么能不能定義一個既有存儲直接后繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。

在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接后繼結點地址，一般稱之為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。

循環鏈表是與單鏈表一樣，是一種鏈式的存儲結構。

所不同的是，循環鏈表的最后一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點，從而構成一個環形的鏈。

循環鏈表的運算與單鏈表的運算基本一致。