1. 首頁 > 生活百科 > >

鏈表存儲的優缺點

生活百科鏈表


鏈表存儲的優缺點

文章插圖
鏈表優點和缺點如下：
優點：在插入和刪除操作時，只需要修改被刪節點上一節點的鏈接地址，不需要移動元素，從而改進了在順序存儲結構中的插入和刪除操作需要移動大量元素的缺點 。
缺點：
1、沒有解決連續存儲分配帶來的表長難以確定的問題 。
2、失去了順序存儲結構隨機存取的特性 。
擴展資料：
線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的） 。
根據情況，也可以自己設計鏈表的其它擴展 。但是一般不會在邊上附加數據，因為鏈表的點和邊基本上是一一對應的（除了第一個或者最后一個節點，但是也不會產生特殊情況） 。
對于非線性的鏈表，可以參見相關的其他數據結構，例如樹、圖 。另外有一種基于多個線性鏈表的數據結構：跳表，插入、刪除和查找等基本操作的速度可以達到O(nlogn），和平衡二叉樹一樣 。
其中存儲數據元素信息的域稱作數據域（設域名為data），存儲直接后繼存儲位置的域稱為指針域（設域名為next） 。指針域中存儲的信息又稱做指針或鏈 。
參考資料來源：百度百科-鏈表
線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的） 。因此，為了表示每個數據元素 與其直接后繼數據元素 之間的邏輯關系，對數據元素 來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置） 。由這兩部分信息組成一個結點（如概述旁的圖所示），表示線性表中一個數據元素 。線性表的鏈式存儲表示，有一個缺點就是要找一個數，必須要從頭開始找起，十分麻煩 。
根據情況，也可以自己設計鏈表的其它擴展 。但是一般不會在邊上附加數據，因為鏈表的點和邊基本上是一一對應的（除了第一個或者最后一個節點，但是也不會產生特殊情況） 。不過有一個特例是如果鏈表支持在鏈表的一段中把前和后指針反向，反向標記加在邊上可能會更方便 。
對于非線性的鏈表，可以參見相關的其他數據結構，例如樹、圖 。另外有一種基于多個線性鏈表的數據結構：跳表，插入、刪除和查找等基本操作的速度可以達到O(nlogn），和平衡二叉樹一樣 。
其中存儲數據元素信息的域稱作數據域（設域名為data），存儲直接后繼存儲位置的域稱為指針域（設域名為next） 。指針域中存儲的信息又稱做指針或鏈 。
【鏈表存儲的優缺點】由分別表示,，…，的N 個結點依次相鏈構成的鏈表，稱為線性表的鏈式存儲表示，由于此類鏈表的每個結點中只包含一個指針域，故又稱單鏈表或線性鏈表 。

    推薦閱讀