作者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://www.ptt.cc/bbs/C_and_CPP/M.1469626909.A.E25.html
推 LPH66: 你這個叫做雙向鏈結串列, 好處當然就是你說的往前走是常數 07/27 21:43
→ LPH66: 但相對的在插入時就要維護兩個指標而不是一個 07/27 21:43
→ LPH66: 以及因為存兩個指標, 空間用量也比較多 07/27 21:44
→ LPH66: 實際上要用單向或雙向是看使用情形決定 07/27 21:44
→ LPH66: 順帶一提, C++ STL 裡單雙向的都有 07/27 21:46
→ LPH66: 單向的是 std::forward_list, 雙向的是 std::list 07/27 21:46
→ Caesar08: 樓上已經幫你解答完畢。補充C++11才有std::forward_list 07/27 21:49
→ schizophrena: 謝謝解答 07/27 22:50
推 joeywayi: 因為浪費空間? 07/28 03:20
推 steve1012: 看需求吧 有時需要啊 07/28 08:39
推 chchwy: 如果你有十萬個node 那浪費的空間就很可觀了 07/28 11:49
→ schizophrena: 但是如果十萬個node要找到最後的那個再刪除 07/28 12:04
→ schizophrena: 時間也很可觀耶 @_@ 07/28 12:04
→ longlongint: 如果是 stack queue 就不需要刪除最後一個node 了 07/28 15:32
→ longlongint: 從 head tail 插入, 從 head 刪除 07/28 15:34
推 steve1012: 所以就說看需求啊 各有好處 沒有完美的ds 07/29 03:40
→ steve1012: 空間 時間 本身結構複雜難implement 都是考量的選項 07/29 03:41
推 kwpn: 看需求拉，若平台就沒這麼多空間給你，就考慮用時間換 07/30 13:10