Python数组添加元素append的时间复杂度分析

由于数组需要连续的存储空间，append（）函数的时间复杂度可能为1也可能为n，主要看在后面添加元素时，当前位置是否可以添加，有位置可以添加的话，则直接在后面添加，此时时间复杂度为1，若后面已有其他元素，则需要把整个数组复制到另一个能满足存储条件的位置，此时时间复杂度为n

而插入函数insert（）的时间复杂度一般为n，因为是在中间插入

附python插入数据的三个方法比较

一、append()函数操作
append函数将元素追加到列表的尾部，每次只能追加一个元素（元素可以为列表、元组等）。追加元素可以直接写入，append()函数中的元素外加[]，表示该元素为数组，会将[]直接写入列表中与后面讲述的extend方法不同。追加多个元素需变成列表形式,将该元素列表写入原列表尾部。示例代码如下：
 

list = [1,2,3]
list.append('a')
#list: [1, 2, 3, 'a']
 
list.append(['a'])
#list: [1, 2, 3, 'a', ['a']]
 
list.append(['b','c'])
#list: [1, 2, 3, 'a', ['a'], ['b', 'c']]

二、extend()函数和'+='运算符
列表的extend()函数也是将元素添加到列表尾部，添加元素与append函数略微区别是添加的[]会被删除。添加元素数组，需要添加2层方括号，添加一层[]时，函数会将数组中元素作为独立元素写入列表中。extend函数与'+='运算符等价。示例代码与上面append书写方式一样，但结果略有不同。
 

list = [1,2,3]
 
list.extend('a')
#list: [1, 2, 3, 'a']
 
list.extend(['a'])
#list: [1, 2, 3, 'a', 'a']
 
list.extend(['b','c'])
#list: [1, 2, 3, 'a', 'a', 'b', 'c']
 
#添加数组需添加2层[]
list.extend([['b','c']])
#list: [1, 2, 3, 'a', 'a','b', 'c', ['b', 'c']]

将示例代码用'+='符号操作一遍，结果与extend函数相同

list = [1,2,3]
list += 'a'
#list: [1, 2, 3, 'a']
 
list += ['a']
#list: [1, 2, 3, 'a', 'a']
 
list += ['b','c']
#list: [1, 2, 3, 'a', 'a', 'b', 'c']
 
#添加数组需添加2层[]
list += [['b','c']]
#list: [1, 2, 3, 'a', 'a', 'b', 'c', ['b', 'c']]

三、insert()函数

list.insert(self,index,object)函数中的index参数表示插入的索引位置，实际插入位置为index参数指示位置的前一个位置。object参数为插入的实参值。insert函数的示例代码：

list = [1,2,3]
list.insert(0,'a')
#list: ['a', 1, 2, 3]
 
list.insert(-1,['b'])
#list: ['a', 1, 2, ['b'], 3]

四、列表生成式错误举例

上文提到的三种方法都是将元素写入原列表，直接应用于列表生成式时无法提取元素会返回None,如果想在列表生成式中对列表末尾添加元素需要使用列表拼接的方式。

#本代码主要实现将单个数字添加到列表尾部，并生成新列表
 
list_1 = ['a','b','c']
new_list = [ list_1.append([i]) for i in range(3)]
#new_list: [None, None, None]
 
#修改后正确代码
list_1 = ['a','b','c']
list_1 = [ list_1+[i] for i in range(3)]
#list_1: [['a', 'b', 'c', 0], ['a', 'b', 'c', 1], ['a', 'b', 'c', 2]]