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 并不是傳統（計算機科學）意義上的列表。傳統的列表，也叫做鏈表（Linked List），通常是由一系列的節點來實現的，其每個節點（尾節點除外）都有一個指向下一個節點的引用。
使用 python 實現一個鏈表的節點類如下：

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

            
          

接下來，我們就可以用其實現一個列表了：

            
              # L 即一個鏈表的頭節點
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)

            
          

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

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

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

這樣做似乎會使得 append 和 insert 一樣糟糕，其實不然，因為盡管這兩種情況都有可能迫使我們去搬動大量的元素，但是主要的不同點在于，對于 append 操作，發生這樣的可能性要小得多。事實上，如果我們能確保所搬入的數據都大過原來數據一定的比例（例如 20% 甚至 100%），那么該操作的平均成本（或者說得更加確切一些，將這些搬運開銷均攤單每次 append 操作中去）通常是常數的。
我們可以認為，對于 python 中的 list 而言，append n 個數字所需要的運行時間是 O(n), 而在首端 insert 相同數量的數字需要的時間約為 O(n^2)。

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