跳轉到一個雙向鏈表真快

的中間是有跳躍到一個雙向鏈表的中間元素的真快，而不是做跳轉到一個雙向鏈表真快

for(int i = 0; i <= numOfElements/2; i++){ 
element = element.next; 
}

這需要那麼多的時間在我的代碼的任何方式，如果我會優化它，它會非常酷:)

來源

2011-05-09 reox

鏈接（或雙向鏈接）列表的一點是隨機訪問速度慢（O(n)）。

您需要使用不同種類的列表，例如skip list。

來源

2011-05-09 13:46:30 SLaks

偉大的思想思考。 ;-) – 2011-05-09 13:48:38

@Konrad：偉大的思想就像一個想法！ – Jay 2011-05-09 13:58:35

鏈表的整點在於這是不能完成的。但是，還存在其他（間接）允許此操作的數據結構。一個這樣的數據結構是skip list，它的名字來源於它可以做到的事實：跳過項目。

此數據結構不適用於您的案例，因爲跳過列表實現字典，不允許直接訪問索引項目。但是，總體結構可以相應調整。

來源

2011-05-09 13:47:18

我不確定這樣做會有很大的意義，這取決於你需要一個雙向鏈表的原因。理想情況下，你可以選擇不使用它。但是，如果這不可能，你可以用另一種類型的數據結構來支持它，例如以整數作爲關鍵字的hashmap。然後，你可以這樣類似：

element.get(numOfElements/2);

來源

2011-05-09 13:47:40

當你說「跳到中間的」，你的意思是字面上每次正中間元素？或者只是「開始或結束之外的某個地方，但確切的地方會有所不同」？

如果你的意思是確切的中間，你可以保持一個指向列表中間的指針以及通常的開始和結束指針。每當一個條目被添加到列表中或從列表中刪除時，就有可能這個指針必須移動。請注意，在兩側將兩個插入物移動到一個位置，並且一個插入點在下方，另一個插入點將抵消。所以你必須保留一個「半個櫃檯」。當一個項目插入下面時，從半計數器中減去一個。當一個項目插入上面時，添加一個。如果半計數器現在爲-2，則將中間指針向下移動一個插槽，並將半計數器復位爲0.如果半計數器現在爲+2，則將中間指針向上移動一個插槽並重置半計數器。我在一年前做過這個。我忘記了爲什麼。

如果你不是確切的中間，那麼我認爲答案是「它不能做」。我想，你可以保留一些指向列表中各個點的指針。像第一個A，第一個B等的字典一樣。

或者我想如果你知道你經常需要「非常接近中間」，你可以維護一箇中間指針，正如我描述的然後從那裏搜索。

是否有任何這些有助於您真正想要解決的問題，我不能說沒有更多信息。

來源

2011-05-09 13:57:56 Jay

你可以保持一箇中間指針，但將需要在每次更新列表的時間進行調整，如果你只需要一個近似，足以

或保留2名獨立的名單和每次訪問中您的時間調整它們，直到它們的長度相等（保持長度爲每個單獨的VAR）

public class DoubledLickedList{ 
    private Node fhead,ftail,shead,stail; 
    private AtomicInteger fsize,sSize; 

    public Class Node{ 
     private Node next; 
     private Node prev; 
     public Node getNext(){ 
      if(next==null && next==ftail)return shead; 
      return next; 
     } 

     public Node getPrev(){ 
      if(prev==null && prev==shead)return ftail; 
      return prev; 
     } 
    } 

    public Node getMiddle(){ 
     adjustToMiddle(); 
     return ftail; 
    } 

    private void adjustToMiddle(){ 
     while(fsize.get()>sSize.get()+1){ 
      //pop first and push it to the second 
      fsize.incrementAndGet(); 
      sSize.decrementAndGet(); 
     } 
     while(sSize.get()>fsize.get()+1){ 
      //pop second and push it to the first 
      sSize.incrementAndGet(); 
      fsize.decrementAndGet(); 
     } 
    } 

}

來源

2011-05-09 14:02:39

如果你真的不需要一個列表中的所有，你可以使用Array，一個TreeMap，或HashMap。

所有有更快的隨機存取。

來源

2011-05-09 14:11:38

跳轉到一個雙向鏈表真快

回答

相關問題