Re: [問題] 請教Singly Linked List的實作問題

看板C_and_CPP作者 (永遠睡不著 @@)時間10年前 (2014/01/06 16:18), 編輯推噓2(2推 0噓 3→)
留言5則, 3人參與, 最新討論串2/2 (看更多)
※ 引述《Hyozero (1)》之銘言： : 照小弟的寫法，關於code裡的Insert與Delete，有些問題想請教 : 1. 不論Insert與Delete，都要先找到目標node之位置 : 目前我只記錄last位置，這樣為了找出目標node， : 就得要整個list都找一遍嗎？感覺很沒有效率... : 但如果記錄了很多位置，好像就失去list的意義，不如用vector或array就好... : 請問有更好的方法嗎？ : 2. Delete時，我想要把目標node移除， : 然後把 "link到目標node的node" 重新link到 "目標node本來的link目標" : 但是就算找到了目標node之位置，還是無法馬上知道 "link到目標node的node" 是誰， : 得再另外用欄位去記錄的樣子... : 這樣算是單邊link list的缺點嗎？還是我的想法上有缺失呢？ : 3. class cl_Node和class cl_List的destructor : 應該是要清除node和list，但是該怎麼寫才對呢？
推
01/06 04:27,
1. list只是找而已, 比起來,vector insert delete會更沒效率.
01/06 04:27
→
01/06 04:30,
2.的想法很奇怪, 應該是先知道"link到目標node的node"是誰,
01/06 04:30
→
01/06 04:31,
才會找的到"目標node"之位置, 怎你的講法是反的.
01/06 04:31
→
01/06 04:36,
另外你的list寫法不太好, class user不需要知道Node這class,
01/06 04:36
→
01/06 04:37,
只需要知道List可以insert某種data就好了, 例如int
01/06 04:37
→
01/06 08:19,
1. insert與delete，vector還要移動元素，因此很慢
01/06 08:19
→
01/06 08:19,
但如果只說"找"這件事，list會比較有效率嗎？
01/06 08:19
→
01/06 08:21,
2. 所以應該是刪除"目標node link到的node"嗎？但是我如果
01/06 08:21
→
01/06 08:22,
是想要刪除目標node，而不是他link到的node，怎麼辦呢?
01/06 08:22
→
01/06 08:23,
請問您是說只要統一放在class cl_List就好了嗎？
01/06 08:23
→
01/06 12:41,
1. 只比較找的效率是沒有參考價值的. 2.假設有A->B->C你想刪
01/06 12:41
→
01/06 12:46,
掉B,指標tmp1指向A知道下一個是B,就儲存tmp2指向B,這時把tmp1
01/06 12:46
→
01/06 12:48,
指向的A的next改成tmp2指向的下一個C,最後利用tmp2來free.
01/06 12:48
→
01/06 12:49,
3. node可以隱藏在list裡,良好的list資料結構用起來應該非常
01/06 12:49
→
01/06 12:50,
像std::vector或array, 你可以參考std::list如何使用.
01/06 12:50
其實這些問題我覺得答案很複雜. 上課時花了很多時間跟例子才勉強說清楚. 我稍微簡答一下, 再請大家指教. 問題: 當我知道要新增或刪除的節點位址時為什麼我不能做新增或刪除 ? 這問題可以參考 C++11 的單向鏈結串列: std::forward_list. C++11 裡面單向鏈結串列 (std::forward_list) 與雙向鏈結串列 (std::list) 明顯不一樣的地方就是新增跟刪除的方法叫做 insert_after 跟 erase_after, 意味著他是新增或刪除目標節點後一個元素, 而不是目標元素本身. 為什麼要這樣設計呢? 原因就是當你只知道目標節點的指標 (或迭代器 [iterator]) 時是 "無法" 把該 節點從單向鏈結串列中移除. 因為你需要修改到目標節點的 "上一個" 節點, 而你卻沒辦法從目標節點中得知上一個節點的資料 解決方法如上所述, 可以選擇改成 insert_after 和 erase_after 表示是新增 或刪除後一個節點 但是這樣可能用起來不夠直覺, 所以可以選擇付出多一點成本改成雙向鏈結串列 就不會有這問題, 因為雙向鏈結串列中知道目標節點的指標時, 可以從目標節點 得知上一個節點位址. 再來回歸到推文的 "找" 的效率問題. 首先要先考慮到你的 "找" 的含義. 一般我們說的 "找" 是 search 或 find 的意思. 也就是我們不知道容器內哪個位置要被新增或刪除 當然你這裡的 "找" 應該是 index 的意思,. 也就是 "移動" 到需要的位置後做新增或刪除的 "移動" 在串列中移動跟陣列中移動, 直觀上陣列中移動的效率比較好, 因為陣列的元素 是連續擺放, 我們可以快速地算出任一個元素的位址去存取他 但是單向鏈結串列中每個節點的位址是由 "上一個" 節點所儲存, 我們 "可能" 需要依序存取才可以 "找" 到你要的節點位址 所以串列理論上 "找" 會比較慢. 有甚麼解決方法呢? 這又回到你使用單向鏈結串列的情境, 例如你想連續在串列某個位置 (例如尾端) 新增很多個元素, 那事實上你只需要找 一次要新增的位置, 那這樣你的成本就會被攤提在每個新增動作上. 簡言之是如果我們知道 "大量" 新增或刪除的動作要作用在那些元素上, 我們是有 技巧把成本攤提掉. 但是整體新增跟刪除的效率到底誰比較好? 以 C++ 可動態改變大小的線性容器實作品 std:vector, std::forward_list, 與 std::list 而言 我們直觀的可能覺得 std::forward_list 除了使用上的不方便之外, 做新增刪除 應該是最快的. 因為不像 std::vector 一樣可能要搬移元素, 也不像 std::list 一樣要維護雙向鏈結的正確性. 但事實上這會跟你存取順序、容器內部元素大小 (搬移要付出的代價大小) 和元素 個數等等因素都有關. 以隨機位置新增或刪除為例, 元素大小不大和元素個數不多的情況下, std::vector 實際上會比串列都快. 這也是 C++ 中用泛型設計的一個好處: 我們可以很容易的切 換不同容器. 只要我們只使用相同效用的功能. 至於提到的封裝問題, 是不是要讓節點的類別成為串列的私有類別之類的問題. 其實我覺得是個設計選擇. 怎樣設計比較好我覺得是不好說的. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.29.148 ※ 編輯: Feis 來自: 140.112.29.148 (01/06 16:28)
推
01/06 16:30, , 1F
忘記在哪裡看到加上cache等因素，「一般而言」
01/06 16:30, 1F
→
01/06 16:31, , 2F
vector還是最快，就算在中間插入刪除
01/06 16:31, 2F
推
01/06 16:43, , 3F
可是 array 的找也是要從頭找起, 會比較快嗎?不都是 o(n)
01/06 16:43, 3F
→
01/06 16:44, , 4F
以移動來說, 是 O(1). 因為這裡的找不是搜尋的意思
01/06 16:44, 4F
→
01/06 16:45, , 5F
如果算上新增或刪除的成本最慢情況是 O(N) 沒錯.
01/06 16:45, 5F
※ 編輯: Feis 來自: 140.112.29.148 (01/06 16:51)
‣ 更多 Feis 的文章
文章代碼(AID): #1IocRD_6 (C_and_CPP)
‣ 更多 Feis 的文章
文章代碼(AID): #1IocRD_6 (C_and_CPP)