爲什麼長度屬性爲O（n）鏈接列表

Question

根據這個非常精彩的book，「大小，另一方面，將始終需要n步驟，因爲沒有辦法知道鏈接列表中有多少節點沒有從頭到尾遍歷，因此長度爲O（n）「。

我想知道爲什麼你不能在UnorderedList類中有一個屬性，當分別添加或刪除一個節點時，它可以增加或減少。這是特定於本書中「大小」的實現嗎？

Answer 1

我想知道你爲什麼不能在UnorderedList類 當一個節點被添加或刪除分別是 可以遞增或遞減的特性。這是否特定於在這本 書中實現「大小」？

顯然，一些鏈表實現可以優化通過增加或減少一個數值屬性計數的項目。

但是在沒有這種優化的情況下，除了迭代整個集合，沒有其他方法可以計算鏈接列表項目。

Answer 2

當然，您可以將長度保存在一個變量中，因此您不必一次又一次地查詢它。本書使用不需要此加變量的實現，但大小函數的複雜性爲O（N）。大小折衷的複雜性。