对 Python 列表常见操作的理解

写这篇文章的原因是前几天做了一道面试题,问题大致是这样的:

1
2
3
4
5
6
7
l = [1, 2, 3, 4, 5]
l.insert(1, 6)
l.append(6)
的时间复杂度分表是什么

我理所应当的认为,Python 列表的内部实现应该是一个链表,而链表的插入和追加操作应该都是 O(1),但今天看到一篇文章原文地址,发现并不是我认为的那样。

Python 在 C 实现中,存储数据的部分是一块连续的内存数组,不过这个数组里存放的也是指针,指向具体的元素,并且会在 结构体 中记录元素的实际个数,结构体如下。

1
2
3
4
5
6
7
8
typedef struct {
# 列表元素的长度
int ob_size;
# 真正存放列表元素容器的指针,list[0] 就是 ob_item[0]
PyObject **ob_item;
# 当前列表可容纳的元素大小
Py_ssize_t allocated;
} PyListObject;

当追加新元素的时候,可以直接通过 ob_item[ob_size]=n 来完成,所以时间复杂度为 O(1)

在插入元素时,操作如下,将要插入位置下方的所有元素向下移动一个位置,然后将要插入位置指向我们插入的元素即可。所以时间复杂度其实是 O(n)

(以上都没有考虑 allocated 分配的情况)

再来看下 pop 这个操作,pop 时只需将 ob_size 减一即可,所以时间复杂的也是 O(1)

remove 就没这么简单了,需要先通过遍历的方式找到要移除的元素,然后将找到的位置到最后一个有效位置这之间的指针都指向其 next 指向的元素(也就是 ob_item[i]=ob_item[i+1]),然后 ob_size-1,所以时间复杂度也为 O(n)

这就是我对 list 几个常见操作的理解,如有错误之处请通过邮件方式指出: jiapan.china#gmail.com