[問題] 請教Singly Linked List的問題

[Hyozero (1)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 
Linux

程式碼(Code)：(請善用置底文網頁, 記得排版) 
理論上，Linked List可以很方便的增加與刪除list中的node
只要打斷link再重新接上即可

小弟試著練習寫單邊link的list(這是個circular list，最後一個(last)會連到第一個)

list.cpp: http://codepad.org/3xTvmAnB
list.h  : http://codepad.org/yK31YvqU
class cl_Node是關於node的資訊
class cl_List是關於list的操作

照小弟的寫法，關於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，但是該怎麼寫才對呢？

麻煩大家幫忙解惑一下
感恩

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 180.176.221.68
推 kwpn:1. list只是找而已, 比起來,vector insert delete會更沒效率.
→ kwpn:2.的想法很奇怪, 應該是先知道"link到目標node的node"是誰,
→ kwpn:才會找的到"目標node"之位置, 怎你的講法是反的.
→ kwpn:另外你的list寫法不太好, class user不需要知道Node這class,
→ kwpn:只需要知道List可以insert某種data就好了, 例如int
→ Hyozero:1. insert與delete，vector還要移動元素，因此很慢
→ Hyozero:   但如果只說"找"這件事，list會比較有效率嗎？
→ Hyozero:2. 所以應該是刪除"目標node link到的node"嗎？但是我如果
→ Hyozero:   是想要刪除目標node，而不是他link到的node，怎麼辦呢?
→ Hyozero:請問您是說只要統一放在class cl_List就好了嗎？
→ kwpn:1. 只比較找的效率是沒有參考價值的. 2.假設有A->B->C你想刪
→ kwpn:掉B,指標tmp1指向A知道下一個是B,就儲存tmp2指向B,這時把tmp1
→ kwpn:指向的A的next改成tmp2指向的下一個C,最後利用tmp2來free.
→ kwpn:3. node可以隱藏在list裡,良好的list資料結構用起來應該非常
→ kwpn:像std::vector或array, 你可以參考std::list如何使用.
推 damody:去看 stlport比較快？