O(1)刪除鏈表節點？

01-05

這只是本人的一個思路，看看大家的意見，覺得可不可行？
簡單說下思路：
首先得對鏈表建立一個Hash結構，用下一個節點的值來進行哈希；
當要刪除某個節點的時候，直接通過該節點的值直接找到該節點的前一個節點，然後通過簡單的指針變換就能把節點刪除。

這裡假如要刪除34這個節點
通過對這個節點的值 hash，便能找到34的前一個節點66。然後在O(1)時間複雜度內就能把34這個節點刪除。
-----------分割線---------
寫了簡單的代碼模型：
//先對鏈表hash
public void prepareHashDelNode(){
Node last = head;
Node cur = last.next;
while(cur != null){
hash[cur.data] = last;

last = cur;
cur = cur.next;
}
}
// hash 刪除節點
public boolean hashDelNode(int data){
if(data == head.data){//刪除頭節點
hash[head.next.data] = null;
head = head.next;
return true;

}else if(data!=head.data hash[data]==null){
System.out.println("no such node!");
return false;
}
Node delPre = hash[data];
//如果是刪除最後一個節點
if(delPre.next.next == null){
delPre.next = null;
hash[data] = null;
}else{//不是最後一個節點

hash[delPre.next.next.data] = delPre;
delPre.next = delPre.next.next;
hash[data] = null;
}
return true;
}

重新發明了一個奇怪版的HashedLinkedList，區別就是每個Node是單向，而HashedLinkedList的Node是雙向的，但問題是你已經用HashMap那麼耗空間的數據結構，難道還在乎每個Node省一個指針？

聽起來就像是雙向鏈表。以前看過一種辦法可以把雙向鏈表的兩個指針通過猥瑣的辦法壓縮在一個指針裡面，名字已經不記得了，題主可以去找一找。

空間換時間的方法多了去了，只是這麼做真的值得嗎

刪除節點k，可以把succ(k)的值複製給k，再刪掉succ(k)，這樣刪單向鏈表可以省一次找pred(k)的pass

把該節點的值和鏈表下一節點的值互換，然後刪除下一節點，對於尾節點還是需要遍歷整個鏈表，平均下來O(1)

雙向鏈表就是O(1)刪除節點的,

改用hash維護跳轉關係, 優點在哪裡?

輪子哥提的那個是抑或鏈表, xor linked list,

特點是可以用單向鏈表的空間佔用進行雙向遍歷, 但制約是遍歷的時候必須知道head或者tail.

不能說完全沒有意義，可以看成是一個有序的hash表，既可以保持順序，也可以執行hash操作，跟Python的OrderedDict差不多，實現也差不多。不需要hash操作的時候還是直接保持指針簡單。用單鏈表代替雙鏈表除了xor以外，可以加個表頭然後直接保存上一節點的指針，這樣前插後插刪除都是O(1)了。

題主你說的就是我這兩點合起來。

所以這個hash不就是鏈表結點上放了一個向前的指針嗎？而且顯然節點上放一個指針比維護一個hash表更環保。。。

致輪子哥 @vczh 我只知道linux clib是只實現了雙端列表的節點基礎結構，結構里只放兩個方向的指針，然後節點的值是由各個其他模塊猥瑣的實現進去的。。。（逃。。。

這不就是cache的實現么....鏈表最好改成雙鏈表，訪問之後的每個元素移動到cache的尾部，淘汰的時候從cache頭部淘汰..

完全可行，犧牲一點空間換取實踐，空間複雜度依然是O(N)，不會因為多了一個Hashtable增加。

考慮刪除也要考慮添加，如果添加函數要求是在某個節點之後添加，單向鏈表就能O(1)時間搞定，根據hash找到前一個節點，然後插入節點更新Hashtable就行了；如果要求在某個節點前面添加，單向列表就沒法O(1)了。

其實這個就相當於一個特殊的拉鏈式哈希表了。

如果鏈表已經在那裡了，變不了。這樣的解法可行的。

如果鏈表可以設計，那使用一個dummy head會幫你省不少邊緣情況。

雙向鏈表可以用一個dummy node成環狀邏輯更加簡潔通暢。

參考了intro to algo關於sentinel的部分

真要工程實現，搞個雙向鏈表也沒啥，既然是hash何不hash自己的值，hash下一個怎麼看都鬧心

查找元素的時候，你這個hash怎麼快速定位到元素？還有hash衝突怎麼處理？

不就是LinkedHashSet嗎？

不明白何來O(1)之說，是指單單「刪除」這個動作嗎？那什麼刪除不是O(1)呢？刪除操作花費時間的點在於找到要刪除的結點在哪兒吧

要麼改造成雙向鏈表；或者將其下一個節點的數據賦值給自己，然後刪除下一個節點，不過如果這個節點是最後一個或者該需要刪除節點不存在於鏈表中的話，就需要遍歷了。不過這兩種情況比較少，平均下來大概也是o(1)吧。

單鏈表也可以 O(1) 刪除啊，只要 iterator 里存前一個節點的指針就好了，完全不需要額外的空間。

感覺可以用跳錶吧？Hash總會有hash碰撞的問題

你覺得維護一個hash表和多加一個指針，哪個成本較高？

不可行。

1. 值與哈希值不是一一對應關係。

2. 把查找一個哈希值的時間，直接去查值的位置，少了中間過程，更快，更省空間。

一前一後倆指針可行？

去看看演算法導論，學學oi或者acm，就應該不會再問這個問題了吧