轉自：http://segmentfault.com/a/1190000002471232

　　昨天和同事們聚餐，說到鏈表，由于對數據結構的不了解（在學校的時候看過一點，現在早忘了），直接丟人現眼了。意識到自己的不足，所以趕緊充充電。

　　再了解鏈表之前，先來了解線性表的存儲結構：其主要分為兩類，一、順序存儲結構——順序表；二、鏈式存儲結構——鏈表。

　　通過兩者的對比表格，我們能夠更加清楚的了解順序表與鏈式表的特點：

順序存儲結構——順序表	? ? 1、可以隨機訪問。 2、占用連續空間，存儲分配只能預先進行，即靜態分配。 　　一旦分配好了，在對其操作過程中不變。 3、插入操作需要移動多個元素。 ?
鏈式存儲結構——鏈表	1、不可以隨機訪問。 2、不需要占用連續空間，動態分配。即在要創建新結點的 　　時候再進行空間劃分。 3、插入操作不需要移動多個元素。 4、每個結點劃一部分空間存儲指向下一結點位置的指針， 　　故存儲空間利用率比順序表稍低

?

　　接下來分別了解5種形式的鏈表：

　　1、單鏈表

　　頭結點可帶、可不帶。

　　不帶頭結點的，head指針則指向開始結點，當head為null時，鏈表為空。

　　帶頭結點的，head指針始終不為空。head ->頭節點 next 為null時，鏈表為空。

　　頭結點不存儲信息，只是作為標記

　　

　　2、雙鏈表

　　雙鏈表就是在單鏈表結點上增添了一個指針域，指向當前結點的前驅。這樣就可以方便的由其后繼來找到其前驅，而實現輸出終端結點到開始結點的數據序列。

　　同樣，雙鏈表也分為帶頭結點的雙鏈表和不帶頭結點的雙鏈表，情況類似于單鏈表。帶頭結點的雙鏈表 head->next 為null
的時候鏈表為空。不帶頭結點的雙鏈表head為null的時候鏈表為空。

　　3、循環單鏈表

　　只要將單鏈表的最后一個指針域（空指針）指向鏈表中第一個結點即可（這里之所以說第一個結點而不說是頭結點是因為，如果循環單鏈表是帶頭結點的則最后一個結點的指針域要指向頭結點；如果循環單鏈表不帶頭結點，則最后一個指針域要指向開始結點）。

　　帶頭結點的循環單鏈表當head等于head->next時鏈表為空；
　　不帶頭結點的循環單鏈表當head等于null時鏈表為空。

　　4、循環雙鏈表

　　

　　循環雙鏈表的構造源自雙鏈表，即將終端結點的next指針指向鏈表中第一個結點，將鏈表中第一個結點的prior指針指向終端結點。

　　帶頭結點的循環雙鏈表當head->next和heaad->prior兩個指針都等于head時鏈表為空。
　　不帶頭結點的循環雙鏈表當head等于null的時候為空。

　　5、靜態鏈表

　　這種鏈表借助一維數組來表示，例如：

轉載于:https://www.cnblogs.com/hcw136156133/p/5043164.html

總結

以上是生活随笔為你收集整理的数据结构之线性存储结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。