Re: [問題] linked list插入的複雜度
我想問一下
答案是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
推
07/27 21:43, , 1F
07/27 21:43, 1F
→
07/27 21:43, , 2F
07/27 21:43, 2F
→
07/27 21:44, , 3F
07/27 21:44, 3F
→
07/27 21:44, , 4F
07/27 21:44, 4F
→
07/27 21:46, , 5F
07/27 21:46, 5F
→
07/27 21:46, , 6F
07/27 21:46, 6F
→
07/27 21:49, , 7F
07/27 21:49, 7F
→
07/27 22:50, , 8F
07/27 22:50, 8F
推
07/28 03:20, , 9F
07/28 03:20, 9F
推
07/28 08:39, , 10F
07/28 08:39, 10F
推
07/28 11:49, , 11F
07/28 11:49, 11F
→
07/28 12:04, , 12F
07/28 12:04, 12F
→
07/28 12:04, , 13F
07/28 12:04, 13F
→
07/28 15:32, , 14F
07/28 15:32, 14F
→
07/28 15:34, , 15F
07/28 15:34, 15F
推
07/29 03:40, , 16F
07/29 03:40, 16F
→
07/29 03:41, , 17F
07/29 03:41, 17F
推
07/30 13:10, , 18F
07/30 13:10, 18F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：