将第一个节点插入空的双向链表[如何]

这是前一个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

将第一个节点插入空的双向链表[如何]

回答

相关问题