當前位置:成語大全網 - 新華字典 - python中鏈式存儲有哪些

python中鏈式存儲有哪些

順序存儲結構最大的缺點是插入和刪除時需要移動大量元素,耗費大量時間。

如果讓相鄰元素間留有足夠余地,也就是不考慮相鄰位置了,那麽,我們這裏可以引入鏈式存儲結構。

鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。

二、鏈表的定義

鏈表(Linked list)是壹種常見的基礎數據結構,是壹種線性表,但是不像順序表壹樣連續存儲數據,而是在每壹個節點(數據存儲單元)裏存放下壹個節點的位置信息(即地址)。

1、單向鏈表

單向鏈表也叫單鏈表,是鏈表中最簡單的壹種形式,壹個信息域(元素域)和壹個鏈接域組成壹個節點。

這個鏈接指向鏈表中的下壹個節點,而最後壹個節點的鏈接域則指向壹個空值。

鏈表的每個結點中只包含壹個鏈接域,所以叫做單鏈表。

表元素域elem用來存放具體的數據。

鏈接域next用來存放下壹個節點的位置(python中的標識)

變量p指向鏈表的頭節點(首節點)的位置,從p出發能找到表中的任意節點。

鏈表中第壹個結點的長處位置叫做頭指針

顯著性鏈表的最後壹個結點指針為“空”(通常用NULL或“^”符號表示)

通常會在單鏈表的第壹個結點前附設壹個結點,稱為頭結點。它的信息域可以不存儲數據,也可以存儲線性表長度等附加信息,頭結點的鏈接域指向第壹個結點的指針。

頭指針與頭結點的異同

無論鏈表是否為空,頭指針均不為空,頭指針是鏈表的必要元素;頭結點不壹定是鏈表的必要要素。

頭指針具有標識作用,所以常用頭指針冠以鏈表的名字。