append 與 insert 對比：
1 2 3 4 5 6 7 8 9 10 11 12 | # append 操作>>> count = 10**5>>> nums = []>>> for i in range(count):... nums.append(i)...>>> nums.reverse()# insert 操作>>> nums = []>>> for i in range(count):... nums.insert(0, i) |
Python中的列表并不是傳統意義上的列表，這也是Python中列表的append操作比insert操作高效的根本原因。
傳統意義上的列表，通常叫做鏈表，是通過(guò)一系列的節點(diǎn)來(lái)實(shí)現的，每個(gè)節點(diǎn)（尾節點(diǎn)除外）都有一個(gè)指向下一個(gè)節點(diǎn)的指針。
1 2 3 4 5 6 7 8 9 | class Node: def __init__(self,value,next=Node) self.value=value self.next=next將節點(diǎn)構造成列表：>>>L = Node("a",Node("b",Node("c",Node("d"))))>>>L.next.next.value'c' |
但是Python中的列表則與此不同。它不是由若干個(gè)獨立的節點(diǎn)相互引用而組成的，而是一整塊單一連續的內存區塊--我們通常稱(chēng)之為數組。這直接導致其與鏈表之間的一些區別。
盡管兩者在遍歷時(shí)的效率相差無(wú)幾（除了鏈表有一些額外開(kāi)銷(xiāo)），但是如果我們按照既定索引值對某元素進(jìn)行直接訪(fǎng)問(wèn)的話(huà)，顯然使用數組會(huì )更加的高效。
因為在數組中，我們通?？梢灾苯佑嬎愠瞿繕嗽卦趦却嬷械奈恢?，并對其進(jìn)行直接訪(fǎng)問(wèn)。而對于鏈表，我們需要從頭開(kāi)始遍歷整個(gè)鏈表。
對于insert操作來(lái)說(shuō)，情況又有所不同。
對于鏈表而言，只要知道了在哪里執行insert操作，其操作成本是非常低的。無(wú)論該鏈表中有多少元素，其操作時(shí)間大致相同。
對于數組而言，每次執行insert操作都需要移動(dòng)插入點(diǎn)右邊所有的元素，甚至在必要時(shí)需要把所有數組元素復制到另外一個(gè)更大的數組中。
聯(lián)系客服
