lzytanxc 2022-04-07 21:30 采纳率: 100%
浏览 65
已结题

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

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.语言有点混乱,求解答!

  • 写回答

1条回答 默认 最新

  • ash062 2022-04-08 13:46
    关注

    1、导入collections模块查看路径

    img

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

    img

    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)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 5月4日
  • 已采纳回答 4月26日
  • 创建了问题 4月7日

悬赏问题

  • ¥30 这是哪个作者做的宝宝起名网站
  • ¥60 版本过低apk如何修改可以兼容新的安卓系统
  • ¥25 由IPR导致的DRIVER_POWER_STATE_FAILURE蓝屏
  • ¥50 有数据,怎么建立模型求影响全要素生产率的因素
  • ¥50 有数据,怎么用matlab求全要素生产率
  • ¥15 TI的insta-spin例程
  • ¥15 完成下列问题完成下列问题
  • ¥15 C#算法问题, 不知道怎么处理这个数据的转换
  • ¥15 YoloV5 第三方库的版本对照问题
  • ¥15 请完成下列相关问题!