作者schizophrena (你很记者你很脑残)
看板C_and_CPP
标题Re: [问题] linked list插入的复杂度
时间Wed Jul 27 21:41:45 2016
我想问一下
答案是A 我也知道为什麽
为何 listNode不设计成
struct listNode
{
struct listNode* prevPtr;
struct listNode* nextPtr;
}
这样当最後一个是 L , 然後要delete L就是
listNode* L = getLastNode(); // L是现在最後一个node
new_L = L->prevPtr; // 将现在的倒数第二个node指定成new_L
delete L; // delete L
L = new_L; // 将 L 指定成倒数第二个node
这样的作法应该A所要作的时间复杂度就不会等比於list的长度了吧?
是这种作法不好? 还是? 有什麽原因吗?
※ 引述《einna (Annie)》之铭言：
: http://i.imgur.com/30Wsgfu.png
: 想请问一下为什麽答案是C呀？
: 以下的code的概念应该可以实现C的动作，但不需要跑遍整个linked list。
: struct listNode {
: char data;
: struct listNode *nextPtr;
: };
: typedef struct listNode *ListNodePtr;
: void insert(listNode F, listNode L, listNode new_point, int new_value)
: {
: new_point->data = new_value; //指定值给main alloc好，传进来的新指标
: L->nextPtr = new_point; //利用L去把这个新指标加到串列後面。
: L = L->nextPtr; //更新L的位置。
: }
: 还是我有甚麽地方没有考虑到，希望网友可以告诉我盲点。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.15.65.242
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1469626909.A.E25.html
1F：推 LPH66: 你这个叫做双向链结串列, 好处当然就是你说的往前走是常数 07/27 21:43
2F：→ LPH66: 但相对的在插入时就要维护两个指标而不是一个 07/27 21:43
3F：→ LPH66: 以及因为存两个指标, 空间用量也比较多 07/27 21:44
4F：→ LPH66: 实际上要用单向或双向是看使用情形决定 07/27 21:44
5F：→ LPH66: 顺带一提, C++ STL 里单双向的都有 07/27 21:46
6F：→ LPH66: 单向的是 std::forward_list, 双向的是 std::list 07/27 21:46
7F：→ Caesar08: 楼上已经帮你解答完毕。补充C++11才有std::forward_list 07/27 21:49
8F：→ schizophrena: 谢谢解答 07/27 22:50
9F：推 joeywayi: 因为浪费空间? 07/28 03:20
10F：推 steve1012: 看需求吧 有时需要啊 07/28 08:39
11F：推 chchwy: 如果你有十万个node 那浪费的空间就很可观了 07/28 11:49
12F：→ schizophrena: 但是如果十万个node要找到最後的那个再删除 07/28 12:04
13F：→ schizophrena: 时间也很可观耶 @_@ 07/28 12:04
14F：→ longlongint: 如果是 stack queue 就不需要删除最後一个node 了 07/28 15:32
15F：→ longlongint: 从 head tail 插入, 从 head 删除 07/28 15:34
16F：推 steve1012: 所以就说看需求啊 各有好处 没有完美的ds 07/29 03:40
17F：→ steve1012: 空间 时间 本身结构复杂难implement 都是考量的选项 07/29 03:41
18F：推 kwpn: 看需求拉，若平台就没这麽多空间给你，就考虑用时间换 07/30 13:10