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

时间：2021-04-23 21:32:30

　　append 与 insert 对比：

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

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

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操作都需要移动插入点右边所有的元素，甚至在必要时需要把所有数组元素复制到另外一个更大的数组中。

相关文章