在Java中使用基於Vector
的Stack
而不是鏈接列表實現的動機是什麼?我知道一個Vector
是同步的,並且繼承了優點(和開銷),但是我覺得這些數據結構通常不是在文本中作爲基於鏈表的結構教導的,而是因爲底層數組填充時避免了昂貴的調整大小。在Java中使用基於矢量的堆棧實現而不是鏈接列表的動機是什麼?
我明白Vectors
,使用攤銷分析,即使與調整大小O(1)。所以也許考慮到這一點,它沒有什麼區別,但我會好奇地理解理論基礎。
在Java中使用基於Vector
的Stack
而不是鏈接列表實現的動機是什麼?我知道一個Vector
是同步的,並且繼承了優點(和開銷),但是我覺得這些數據結構通常不是在文本中作爲基於鏈表的結構教導的,而是因爲底層數組填充時避免了昂貴的調整大小。在Java中使用基於矢量的堆棧實現而不是鏈接列表的動機是什麼?
我明白Vectors
,使用攤銷分析,即使與調整大小O(1)。所以也許考慮到這一點,它沒有什麼區別,但我會好奇地理解理論基礎。
鏈表有以下缺點:
當然,這些只是鏈接列表的一般缺點;我不知道他們是否影響了基於Queue
和Stack
的決定。
第二點不會以任何方式影響堆棧,因爲您只需要在一端工作,因此您可以以此爲結局。對於隊列,帶有指向最後一個節點的雙向鏈表可能有效,但我不是100%確定的。 – delnan 2012-07-06 22:24:18
向量將其數據存儲在連續的內存中。這對緩存很有用。
鏈接列表在內存中可能變得非常分散。
這與ArrayLists相比如何? – BlackVegetable 2012-07-06 19:14:02
在別人抱怨之前,Stack和Vector被認爲正在被棄用。您應該考慮使用'ArrayList'來代替,如果需要同步,請將ArrayList與'Collections.synchronizedList(arrayList)'同步。 – Miquel 2012-07-06 19:14:06
Vector爲什麼出來?您可以將多個變量存儲在一個對象中,並將該對象作爲條目存儲在向量中。 – 2012-07-06 19:16:01