我想知道使用append()構建的Python v2.7列表的複雜性順序是什麼? Python列表是雙重鏈接的,因此它是不變的複雜性,還是單個鏈接,因此線性複雜?如果它是單獨鏈接的,那麼我怎麼能夠在線性時間內從迭代中建立一個列表,以從頭到尾的順序提供列表的值?Python列表是單列還是雙列鏈表?
例如:
def holes_between(intervals):
# Compute the holes between the intervals, for example:
# given the table: ([ 8, 9] [14, 18] [19, 20] [23, 32] [34, 49])
# compute the holes: ([10, 13] [21, 22] [33, 33])
prec = intervals[0][1] + 1 # Bootstrap the iteration
holes = []
for low, high in intervals[1:]:
if prec <= low - 1:
holes.append((prec, low - 1))
prec = high + 1
return holes
根本不是鏈表。它基本上被稱爲動態數組。你從哪裏知道這是一個鏈表? – delnan 2013-02-27 20:42:58
@delnan排序。與某些其他語言不同,它不是靜態的,否則「追加」根本不起作用。它更接近Java的ArrayLists,以及其他語言中的類似結構。請參見[Dynamic Arrays](http://en.wikipedia.org/wiki/Dynamic_array)。編輯:對不起,我一開始沒有看到「動態」。當然,你是對的。 – 2013-02-27 20:45:42
@StjepanBakrac這就是爲什麼我編輯它說幾乎立即發佈後的「動態數組」;-) – delnan 2013-02-27 20:46:26