我发现这篇文章对于理解如何使用python代码实现列表非常有帮助。

class OhMyList:
    def __init__(self):
        self.length = 0
        self.capacity = 8
        self.array = (self.capacity * ctypes.py_object)()

    def append(self, item):
        if self.length == self.capacity:
            self._resize(self.capacity*2)
        self.array[self.length] = item
        self.length += 1

    def _resize(self, new_cap):
        new_arr = (new_cap * ctypes.py_object)()
        for idx in range(self.length):
            new_arr[idx] = self.array[idx]
        self.array = new_arr
        self.capacity = new_cap

    def __len__(self):
        return self.length

    def __getitem__(self, idx):
        return self.array[idx]

我发现这篇文章对于理解如何使用python代码实现列表非常有帮助。

class OhMyList:
    def __init__(self):
        self.length = 0
        self.capacity = 8
        self.array = (self.capacity * ctypes.py_object)()

    def append(self, item):
        if self.length == self.capacity:
            self._resize(self.capacity*2)
        self.array[self.length] = item
        self.length += 1

    def _resize(self, new_cap):
        new_arr = (new_cap * ctypes.py_object)()
        for idx in range(self.length):
            new_arr[idx] = self.array[idx]
        self.array = new_arr
        self.capacity = new_cap

    def __len__(self):
        return self.length

    def __getitem__(self, idx):
        return self.array[idx]

它是一个动态数组。实践证明:无论索引如何，索引都需要相同的时间(当然差异非常小(0.0013µs !)):

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

如果IronPython或Jython使用链表，我会感到震惊——它们会破坏许多广泛使用的库的性能，这些库建立在链表是动态数组的假设之上。

在CPython中，列表是指针的数组。Python的其他实现可以选择以不同的方式存储它们。

这取决于实现，但IIRC:

CPython使用指针数组 Jython使用数组列表 IronPython显然也使用数组。您可以浏览源代码来找到答案。

因此它们都有O(1)个随机访问。

我推荐Laurent Luce的文章“Python列表实现”。对我来说真的很有用，因为作者解释了如何在CPython中实现列表，并为此使用了出色的图表。

List object C structure A list object in CPython is represented by the following C structure. ob_item is a list of pointers to the list elements. allocated is the number of slots allocated in memory. typedef struct { PyObject_VAR_HEAD PyObject **ob_item; Py_ssize_t allocated; } PyListObject; It is important to notice the difference between allocated slots and the size of the list. The size of a list is the same as len(l). The number of allocated slots is what has been allocated in memory. Often, you will see that allocated can be greater than size. This is to avoid needing calling realloc each time a new elements is appended to the list.

...

附加 我们在列表中添加一个整数:l.p append(1)。会发生什么呢? 我们继续添加一个元素:l.p append(2)。当n+1 = 2时调用List_resize，但因为分配的大小是4，所以不需要分配更多的内存。当我们再加两个整数l.append(3)， l.append(4)时也会发生同样的事情。下面的图表显示了我们目前所拥有的。

...

插入 让我们在位置1插入一个新的整数(5):l.insert(1,5)，看看内部发生了什么。

...

Pop When you pop the last element: l.pop(), listpop() is called. list_resize is called inside listpop() and if the new size is less than half of the allocated size then the list is shrunk. You can observe that slot 4 still points to the integer but the important thing is the size of the list which is now 4. Let’s pop one more element. In list_resize(), size – 1 = 4 – 1 = 3 is less than half of the allocated slots so the list is shrunk to 6 slots and the new size of the list is now 3. You can observe that slot 3 and 4 still point to some integers but the important thing is the size of the list which is now 3.

...

删除 Python列表对象有一个删除特定元素的方法:l.remove(5)。