inserting first node into empty doubly-linked list [how to]
This is a follow-on to a previous post. I am now looking at how to insert a first node into an empty doubly-linked list. It's kind of tricky at first it seems...i would be grateful for a hint as to what is missing in my addFirst method
...
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 ;
}
开发者_JAVA百科
[EDIT]
Solution as proposed by typo.pl:
public void addFirst(DLLNode v)
{
v.pred = first ;
v.succ = last ;
first = v ;
last = v ;
}
You've only updated the node's information.
Now you need to update the DLL's information as to what the first/last nodes in the list are. And it's really easy to update when you're adding one node to an empty list. There's only one choice for first node and one choice for last node.
you can do something like that
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;
}
you can also use Sentinel nodes
You can actually improve on this by pretending that you're using a circularly linked list:
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;
}
}
Note how push works even when the list is empty: this.next is the same as this and this.next.prev is the same as this.prev.
精彩评论