雙向鏈接列表

我創建了雙向圓形鏈接列表。雙向鏈接列表

我需要知道每個節點到頭部的距離。

因爲當我必須刪除或獲取一個節點與特定鍵，如果2個節點具有相同的密鑰和相同的距離，兩者都必須被刪除或獲得，否則必須刪除最接近頭節點。

我不知道如何計算距離，因爲是圓形的......

這樣這個鏈表工作的插入。

所有節點後頭部去。

實施例：

1）頭部

2）頭 - A（插入的）

3）機頭-BA（插入的B）

4）頭-CBA（插入的C）

現在，我只做一個正常的取消沒有距離。這是我的代碼。

/* Function to delete node with the key */ 
public void deleteWithKey(int key) { 
    if (key == head.getData()) { 
     if (size == 1) { 
      head = null; 
      end = null; 
      size = 0; 
      return; 
     } 
     head = head.getLinkNext(); 
     head.setLinkPrev(end); 
     end.setLinkNext(head); 
     size--; 
     return; 
    } 
    if (key == end.getData()) { 
     end = end.getLinkPrev(); 
     end.setLinkNext(head); 
     head.setLinkPrev(end); 
     size--; 
    } 
    Node current = head.getLinkNext(); 
    for (int i = 2; i < size; i++) { 
     if (key == current.getData()) { 
      Node p = current.getLinkPrev(); 
      Node n = current.getLinkNext(); 

      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      size--; 
      return; 
     } 
     current = current.getLinkNext(); 
    } 
    System.out.println("Don't exist a node with this key"); 
}

感謝所有。

來源

2017-05-28 Master-Antonio

爲什麼它來計算的距離的問題？ –

因爲是循環的。每個節點都鏈接到左側和右側。我需要知道從頭到每個節點的距離。 –

示例：我有一個列表Head-B-A，B和A的距離相同。因爲A與Head關聯。將是A <-->頭<--> B <---> A –

這是我所做的最終工作代碼。

你有沒有改進？

感謝所有的幫助。

複雜= O（n）的

/* Function to delete node with the key */ 
public void deleteWithKey(int key) { 
    if (key == head.getData()) { 
     if (size == 1) { 
      head = null; 
      end = null; 
      size = 0; 
      return; 
     } 
     head = head.getLinkNext(); 
     head.setLinkPrev(end); 
     end.setLinkNext(head); 
     size--; 
     return; 
    } 
    if (key == end.getData()) { 
     end = end.getLinkPrev(); 
     end.setLinkNext(head); 
     head.setLinkPrev(end); 
     size--; 
    } 
    Node next = head; 
    Node back = head; 
    while (next != end) { 
     next = next.getLinkNext(); 
     back = back.getLinkPrev(); 
     if ((key == next.getData()) && (key == back.getData()) && (next != back)) { 
      Node p = next.getLinkPrev(); 
      Node n = next.getLinkNext(); 
      Node p1 = back.getLinkPrev(); 
      Node n1 = next.getLinkNext(); 
      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      p1.setLinkPrev(n1); 
      n1.setLinkPrev(p1); 
      size -= 2; 
      return; 
     } 

     if ((key == next.getData()) && (next != back)) { 
      Node p = next.getLinkPrev(); 
      Node n = next.getLinkNext(); 
      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      size--; 
      return; 
     } 
     if ((key == next.getData()) && (next == back)) { 
      Node p = next.getLinkPrev(); 
      Node n = next.getLinkNext(); 
      p.setLinkNext(n); 
      n.setLinkPrev(p); 
      size--; 
      return; 
     } 
    } 
    System.out.println("Don't exist a node with this key"); 
}

來源

2017-05-28 14:39:40

這是我能想到的解決問題的僞代碼。

鑑於head，

// no data 
if(head==null) return; 
// next and prev are always at same distance 
next = head; 
prev = head.prev; 

// ensure nodes are not same or crossed half way through the list 
while (next == prev || next.prev == prev){ 
// delete nodes if values are same 
if (next.val == prev.val){ 
    if(next!=head) { 
     next.prev.next = next.next; 
     next.next.prev = next.prev; 
     prev.prev.next = prev.next; 
     prev.next.prev = prev.prev; 
    } 
    // list has only two nodes 
    else if(head.next==prev){ 
     head = null; 
     return; 
    // remove head and its prev node 
    else{ 
     head = head.next; 
     head.prev = prev.next; 
     head.prev.next = head 
    } 
} 
// traverse through the list 
next = next.next 
prev = prev.prev 
}

來源

2017-05-28 10:44:50

該類的next和prev參數節點可幫助我們滾動節點 –

（項目文本）說，頭是插入的第一個節點，並且末尾將始終是爲插入模式插入的第二個節點。 –

他們是數據節點。你應該保留兩個空指針，這些數據節點只是你的impl代碼 –

你其實並不需要知道的距離。相反，你需要找到最接近頭的。

因爲它是一個循環雙向鏈表，這個任務很簡單：

定義兩個變量a和b，初始化兩個頭
如果其中任何一個目標，刪除匹配的節點和出口
分配a = a.next和b = b.previous
轉到2

來源

2017-05-28 11:29:02 Bohemian

沒錯。我沒有想過。我喜歡這個解決方案。我測試得很快。 –

雙向鏈接列表

回答

相關問題