python 中链表尾部添加元素 append 函数的时间复杂度

Question

1.python 中使用 l=deque()创建链表或队列这两种数据结构,以链表为例,尾部添加元素方式为:l.append(x)
2.不同于数组,我们知道链表读慢,写快,插入元素的时间复杂度为 O(1),这里不包括查找元素.deque 模块中使用 append()方法实现元素添加,即在尾部添加元素
3.这里有个疑问,尾部添加元素,即将要加入的元素 next 指针指向 None,原本的尾部元素 next 指针指向当前需添加的元素即可,这样看来时间复杂度为 O(1),但修改指针前需遍历整个链表找到最后一个元素,这样时间复杂度就是 O(N)了,时间复杂度就和数组是一样的?
4.所以 deque 模块的 append()方法尾部添加元素的时间复杂度到底是多少?
5.或者可以拿出 append()函数源码?看一下具体实现方式?
6.语言有点混乱,求解答!

Answer 1

1、导入collections模块查看路径

2、找到后，将文件夹拖入vs code，查找deque，看到其是从_collections模块导入的，蛋疼，_collections是内置模块

3、涉及到了知识盲区，去堆栈溢出上看一下，找到了个链接，https://hg.python.org/cpython/file/tip/Modules/_collectionsmodule.c

deque_append_internal(dequeobject *deque, PyObject *item, Py_ssize_t maxlen)
{
    if (deque->rightindex == BLOCKLEN - 1) {
        block *b = newblock();
        if (b == NULL)
            return -1;
        b->leftlink = deque->rightblock;
        CHECK_END(deque->rightblock->rightlink);
        deque->rightblock->rightlink = b;
        deque->rightblock = b;
        +
−MARK_END(b->rightlink);
        deque->rightindex = -1;
    }
    Py_SIZE(deque)++;
    deque->rightindex++;
    deque->rightblock->data[deque->rightindex] = item;
    if (NEEDS_TRIM(deque, maxlen)) {
        PyObject *olditem = deque_popleft(deque, NULL);
        Py_DECREF(olditem);
    } else {
        deque->state++;
    }
    return 0;
}

static PyObject *
deque_append(dequeobject *deque, PyObject *item)
{
    Py_INCREF(item);
    if (deque_append_internal(deque, item, deque->maxlen) < 0)
        return NULL;
    Py_RETURN_NONE;
}

4、deque是双端链表。。。append是O(1)