inserting first node into empty doubly-linked list [how to]

1
votes

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 ; 
}

[EDIT]

Solution as proposed by typo.pl:

public void addFirst(DLLNode v)
{
    v.pred = first ;
    v.succ = last ;
    first = v ;
    last = v ;
}
3
javalinked-list
Do you have any thing that points to the Length or the DDL? This would be easiest because there are different situations when inserting a node, you want to know whether there is another node after the one you would be inserting. Then you would set the insert node to point to the next node, and front to that first node. - Jim

3 Answers

1
votes

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.

0
votes

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

0
votes

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.