import time


def log_time(func, *args, **kwargs):
    def inner():
        t1 = time.time()
        func(*args, **kwargs)
        t2 = time.time()
        print(f"使用的時間是{t2 - t1}s")
    return inner


@log_time
def append_func():
    ll = list()
    for i in range(10000):
        ll.append(i)


@log_time
def insert_func():
    ll = list()
    for j in range(10000):
        ll.insert(0, j)


insert_func()
append_func()

            
          

通過以上程序說明 python 中 list 的 append 要快于 insert。

其實， Python 中的 list 并不是傳統(tǒng)（計算機科學(xué)）意義上的列表。傳統(tǒng)的列表，也叫做鏈表（Linked List），通常是由一系列的節(jié)點來實現(xiàn)的，其每個節(jié)點（尾節(jié)點除外）都有一個指向下一個節(jié)點的引用。
使用 python 實現(xiàn)一個鏈表的節(jié)點類如下：

            
              class Node(object):
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

            
          

接下來，我們就可以用其實現(xiàn)一個列表了：

            
              # L 即一個鏈表的頭節(jié)點
L = Node("a", Node("b", Node("c", Node("d"))))
print(L.value)
print(L.next.value)
print(L.next.next.value)
print(L.next.next.next.value)

            
          

這是一個所謂的單向列表，雙向列表的各節(jié)點里面還有持有一個指向前一個節(jié)點的引用。但是 python 中的 list 則于此有點不同，它不是由若干個獨立的節(jié)點相互引用形成的，而是一整塊單一連續(xù)的內(nèi)存塊 —— 我們通常稱之為數(shù)組（array)。這直接導(dǎo)致了它和鏈表之間的一些重要的區(qū)別。

如果我們想要按照既定的索引值對某元素進行直接訪問的話，顯然使用數(shù)組會更加有效率。因為在數(shù)組中，我們可以直接計算出目標(biāo)元素在內(nèi)存中的位置，并且能對其進行直接訪問，而對于鏈表來說，我們必須從頭開始訪問整個鏈表。

而如果我們想要進行 insert 操作，對于鏈表來說，只要知道了在哪里執(zhí)行 insert 操作，其操作成本是非常低的。無論其中有多少個元素，其操作時間大致上是相同的。而數(shù)組就非常不一樣了，它在每次執(zhí)行 insert 的時候都需要移動插入點右邊的所有元素，甚至在必要時，我們還需要將這些列表元素整體搬到一個更大的數(shù)組中。也正是因為如此，append 操作通常采用一種被稱為動態(tài)數(shù)組或者是向量的特定解決方案。其主要想法是將內(nèi)存分配得大一點，并且等到其溢出時，在線性時間內(nèi)再次重新分配內(nèi)存。

這樣做似乎會使得 append 和 insert 一樣糟糕，其實不然，因為盡管這兩種情況都有可能迫使我們?nèi)グ釀哟罅康脑兀侵饕牟煌c在于，對于 append 操作，發(fā)生這樣的可能性要小得多。事實上，如果我們能確保所搬入的數(shù)據(jù)都大過原來數(shù)據(jù)一定的比例（例如 20% 甚至 100%），那么該操作的平均成本（或者說得更加確切一些，將這些搬運開銷均攤單每次 append 操作中去）通常是常數(shù)的。
我們可以認(rèn)為，對于 python 中的 list 而言，append n 個數(shù)字所需要的運行時間是 O(n), 而在首端 insert 相同數(shù)量的數(shù)字需要的時間約為 O(n^2)。

更新時間： 2019.9.6
參考：《python 算法教程》