將第一個節點插入空的雙向鏈表[如何]

這是前一個post的後續操作。我現在正在研究如何將第一個節點插入到空雙向鏈表中。這是一種棘手起初似乎......是什麼在我的addfirst僅方法缺失，我會爲有一絲感激將第一個節點插入空的雙向鏈表[如何]

... 
public DLL() 
{ 
    first = null ; 
    last = null ; 
} 

... 
DLL myList = new DLL() ; 
DLLNode A = new DLLNode("Hello", null, null) ; 
... 

myList.addFirst(A) ; 

... 
public void addFirst(DLLNode v) 
{ 
    v.pred = first ; 
    v.succ = last ; 
}

[編輯]提議typo.pl

解決方案：

public void addFirst(DLLNode v) 
{ 
    v.pred = first ; 
    v.succ = last ; 
    first = v ; 
    last = v ; 
}

來源

2011-03-14 raoulbia

你有任何指向Length或DDL的東西嗎？這將是最容易的，因爲在插入節點時存在不同的情況，您想知道是否在您要插入的節點之後存在另一個節點。然後，您將設置插入節點指向下一個節點，並指向該第一個節點。 – Jim 2011-03-14 23:31:30

您只更新了節點的信息。

現在您需要更新DLL有關列表中第一個/最後一個節點的信息。當您將一個節點添加到空列表時，更新非常容易。第一個節點只有一個選擇，最後一個節點只有一個選擇。

來源

2011-03-14 23:31:07

啊:)謝謝！ – raoulbia 2011-03-14 23:33:25

你好typo.pl，如果你不介意請看看我關於這個話題的下一個問題。 http://stackoverflow.com/questions/5311865/inserting-new-node-before-first-node-of-a-doubly-linked-list-how-to – raoulbia 2011-03-15 13:56:10

你可以做這樣的事情

public void addFirst(DLLNode v){ 

    v.pred = null ; //v will be first node so its pred. is null 
    v.succ = first; //v successor is the old first node 

    if (first != null) 
     first.pred = v; //the first pred. is the new node 

    first = v;  //v is now the first node in the linked list 

    //if that was the first node to add , update the last pointer      
    if (last == null) 
     last = v; 
}

你也可以使用Sentinel nodes

來源

2011-03-14 23:41:39

您可以假裝你使用圓鏈表這實際上提高：

public class DLLNode { 
    Object contents; 
    DLLNode next, prev; 
} 

public class DLL extends DLLNode { 
    public DLL() { 
     // next and prev are the first and last entry 
     // but they are set to this to indicate an empty list 
     next = prev = this; 
    } 
    public void push(DLLNode v) { 
     v.next = this; 
     v.prev = this.next; 
     this.next.prev = v; 
     this.next = v; 
    } 
    public void shift(DLLNode v) { 
     v.prev = this; 
     v.next = this.prev; 
     this.prev.next = v; 
     this.prev = v; 
    } 
    public DLLNode pop() { 
     return this.remove(this.next); 
    } 
    public DLLNode unshift() { 
     return this.remove(this.prev); 
    } 
    public DLLNode remove(DLLNode v) { 
     if (v == this) throw new IllegalArgumentException(); 
     v.next.prev = v.prev; 
     v.prev.next = v.next; 
     v.next = null; 
     v.prev = null; 
     return v; 
    } 
}

請注意即使列表爲空時，推送是如何工作的：this.next與此相同，this.next.prev與this.prev相同。

來源

2011-03-14 23:55:03 Neil

將第一個節點插入空的雙向鏈表[如何]

回答

相關問題