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.语言有点混乱,求解答!
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
python 中链表尾部添加元素 append 函数的时间复杂度
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- ash062 2022-04-08 13:46关注
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)
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 关于arduino编程toCharArray()函数的使用
- ¥100 vc++混合CEF采用CLR方式编译报错
- ¥15 coze 的插件输入飞书多维表格 app_token 后一直显示错误,如何解决?
- ¥15 vite+vue3+plyr播放本地public文件夹下视频无法加载
- ¥15 c#逐行读取txt文本,但是每一行里面数据之间空格数量不同
- ¥50 如何openEuler 22.03上安装配置drbd
- ¥20 ING91680C BLE5.3 芯片怎么实现串口收发数据
- ¥15 无线连接树莓派,无法执行update,如何解决?(相关搜索:软件下载)
- ¥15 Windows11, backspace, enter, space键失灵
- ¥15 cfx离心泵非稳态计算