【Python算法】列表中的 append 比 insert 效率高的实质

　　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操作高效的根本原因。

　　传统意义上的列表，通常叫做链表，是通过一系列的节点来实现的，每个节点（尾节点除外）都有一个指向下一个节点的指针。

?

1 2 3 4 5 6 7 8 9

class Node:     def __init__(self,value,next=Node)         self.value=value         self.next=next 将节点构造成列表： >>>L = Node("a",Node("b",Node("c",Node("d")))) >>>L.next.next.value 'c'

　　但是Python中的列表则与此不同。它不是由若干个独立的节点相互引用而组成的，而是一整块单一连续的内存区块--我们通常称之为数组。这直接导致其与链表之间的一些区别。

　　尽管两者在遍历时的效率相差无几（除了链表有一些额外开销），但是如果我们按照既定索引值对某元素进行直接访问的话，显然使用数组会更加的高效。

　　因为在数组中，我们通常可以直接计算出目标元素在内存中的位置，并对其进行直接访问。而对于链表，我们需要从头开始遍历整个链表。

　　对于insert操作来说，情况又有所不同。

• 对于链表而言，只要知道了在哪里执行insert操作，其操作成本是非常低的。无论该链表中有多少元素，其操作时间大致相同。

• 对于数组而言，每次执行insert操作都需要移动插入点右边所有的元素，甚至在必要时需要把所有数组元素复制到另外一个更大的数组中。