Re: [問題] dlist的dummy放哪

[ric2k1 (Ric)]

※ 引述《hiroki1139 (小波)》之銘言：
: // 版上好多人都寫完了好可怕
: 請問一下
: dummy要放在頭還是尾巴啊
: 因為有一行註解寫到// _head is dummy node
: 可是同學都說要放最後一個
: 所以要怎麼放呢
: 還是根本沒差XD
: 謝謝~~

1. 在 dlist 剛 construct 時，整個 dlist 只有一個 dummy node,

   所以 _head is dummy node, 而且其 _prev 與 _next 都是指到自己。

2. 但在有 data insert 進去之後，

   _head 就是指到真正的第一筆資料 (i.e. 最小的 data),

   這時 _head->_prev = dummy, dummy->_next = _head.

   同時要注意，有效資料的最後一筆 (i.e. 最大的 data), say "tail",

   要保持 tail->_next = dummy, dummy->_prev = tail.

   也就是說，從 _head 到 tail 到 dummy 再回到 _head，繞成一圈，

   而且因為是 doubly linked list, 所以反向繞也可以通.

3. 注意我們只有 _head 這個 data member,

   上面所述的 dummy 與 tail 只是說明用而已，你要自行保證 link 的連續性。

4. dummy node 從頭到尾都會存在，而且是同一個 ListNode,

   因為 dlist 在做任何操作時頂多只會動到 dummy node 的 _prev or_next,

   不會動到 dummy node 本身。

5. clear() 會把所有 data node 清掉，只剩 dummy node.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.36.52.227
推 TommyKSHS:那如果從頭到尾 dlist 都有一個 dummy node 但是結果是
→ TommyKSHS:對的 這樣可以嗎？ (我一開始誤解了就寫成一直有 dummy.
→ ric2k1:? 從頭到尾都有 dummy node 是沒錯啊! 你的問題是?
→ ric2k1:不過昨天有人問說如果 _head 一直指到 dummy node 可不可以
→ ric2k1:==> 雖然我是說 _head 應該是要指到最小的 element, 但是如
→ ric2k1:果你們已經寫了, 那就算了, 畢竟題目好像也沒有規定清楚...
推 TommyKSHS:呃…我的意思是 _head 一直指到 dummy Orz...
→ TommyKSHS:昨天晚上意識不清 說錯了
→ ric2k1:回樓上，是的，這就是昨天同學問我的，如果你們已經這樣做
→ ric2k1:也 OK 啦!
→ ckmarkoh:也就是直接把_head當成end() 那begin()就取_head+1
→ ckmarkoh:其實這樣比較方便 不需要更改_head所指的位置
→ ric2k1:嗯，也是啦!
推 wintercobra:cool!