單鏈表與雙鏈表
鏈表是一種用於存儲數據集合的線性數據結構。鏈表在它自己的內存塊中將內存分別分配給它的元素,通過將這些元素作為鏈中的鏈接鏈接來獲得整體結構。單鏈表由一系列節點組成,每個節點都有對序列中下一個節點的引用。雙鏈接列表包含一個節點序列,其中每個節點都包含對下一個節點和上一個節點的引用。
單鏈表
單鏈鏈表中的每個元素都有兩個字段,如圖1所示。數據字段保存存儲的實際數據,下一個字段保存對鏈中下一個元素的引用。鏈接列表的第一個元素的頭被存儲為鏈表的第一個元素。
圖2描述了一個包含三個元素的單鏈表。每個元素存儲其數據,除最後一個元素外的所有元素都存儲對下一個元素的引用。最後一個元素的下一個字段中包含一個空值。列表中的任何元素都可以通過從開頭開始並跟隨下一個指針來訪問,直到滿足所需的元素為止。
雙鏈表
雙鏈接列表中的每個元素都有三個字段,如圖3所示。下一個數據鏈保存與下一個單獨鏈接的字段的數據,而下一個數據鏈則保存與實際數據鏈相類似的數據。另外,previous字段保存對鏈中上一個元素的引用。鏈接列表的第一個元素的頭被存儲為鏈表的第一個元素。
圖4描述了一個包含三個元素的雙鏈接列表。所有中間元素都存儲對第一個和前一個元素的引用。列表中的最後一個元素在其下一個字段中保留空值,而列表中的第一個元素在其上一個字段中保留空值。雙鏈表可以通過跟隨每個元素中的下一個引用向前遍歷,同樣可以使用每個元素中的前一個引用向後遍歷。
單鏈表和雙鏈表有什麼區別?