How do I insert a new node before first node of a doubly-linked list?

Question

I am looking at how to insert a new node before the first node of a doubly-linked list. I'm getting confused with the auxiliary nodes required for this operation and the sequence of steps in which to perform the operation. I would be grateful for a hint on how to solve this problem i.e. what is wrong with my insertBeforeFirst method. As it stands the method causes a nullPointerException which i find hard to troubleshoot. (note: this is a follow-on to a previous post.)

public DLL()
{
    header = null ;
    tail = null ;
}

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

myList.addFirst(A) ;
myList.insertBeforeFirst(B)

...
public void addFirst(DLLNode v)
{
    v.pred = header ; 
    v.succ = tail ; 
    header = v ;
    tail = v ;
}
...

public void insertBeforeFirst(DLLNode v)
{
    DLLNode aux = v ;
    aux.succ = header.succ ;
    header = aux ;
    DLLNode aux2 = aux.succ ;
    aux2.pred = v ;
}

[EDIT]

I've followed Aaron's advice and made a drawing and i have a slight improvement in that i don't get a nullPointerException anymore but the new mode is inserted after the first node rather than before. So my drawing skills need some polishing too i think :)

public void insertBeforeFirst(DLLNode v)
{
    v.succ = header.succ ; // point new node succ to current first node
    header.succ = v ;  //point header to new node
    DLLNode aux = header.succ ; // auxiliary node for backward insertion
    aux.pred = v ; // point auxiliary's pred backward to new node
}

[EDIT2]

Looking at the post by MahlerFive I see now why some of you might get confused by my header and tail talk. Here is where i got it from: "To simplify programming, it is convenient to add special nodes at both ends of a doubly linked list: a header node just before the head of the list, and a trailer node just after the tail of the list. These "dummy" nodes do not store any elements" source

So it seems that for a starter i need to find a way to implement these dummy nodes correctly before i can add anything and make correct references. these DUMMY nodes seem to require a different Node constructor? Could they be instantiated by the DLL default constructor?

[EDIT3]

@MahlerFive, the DLL constructor will look like this:

public DLL()
{
    DLLNode Header = new DLLNode(null, null, null) ;
    DLLNode Tail = new DLLNode(null, Header, null) ;
    Header.succ = Tail ;
}

and my method something like this, although i'm getting a nullPointerException at the moment:

// insert z before v
public void addBeforeFirst(DLLNode v, DLLNode z)
{
    DLLNode aux = v.pred ;
    z.pred = aux ;
    z.succ = v ;
    v.pred = z ;
    aux.succ = z ;
}

[EDIT4]

I'm making progress. (great feeling!) I am in agreement with MahlerFive that the DUMMY Header and Tail nodes are not a great way to approach this. But as it was mentioned in a published book on the matter it was worth at least exploring. Here goes my new code (without the use of dummy nodes):

...

// DLL Constructor
public DLL()
{
    first = null ;
    last = null ;
}
...
// example insert call
// B is the node in front of which i want to insert
l.insert("Ciao", B) ;
...

public void insert(String elem, DLLNode pred)
{
    // make ins a link to a newly-created node with element elem,
    // predecessor null, and successor null.
    DLLNode ins = new DLLNode(elem, null, null) ;
    // Insert ins at the insertion point in the
    // forward SLL headed by first.
    ins.pred = first ;
    ins.succ = first ;
    // let first be the the new node
    first = ins ;
}

this needs fine tuning as i haven't set any backwards links yet but it's a great starting point. To make sure this works correctly (at least in the forward way) i added print statements to print out the first and last element as i added nodes. Indeed they were updated correctly:

Hi
first: hi
last: hi

Ciao Hi
first: Ciao
last: hi

Moin Ciao Hi
first: Moin
last: hi

The "dummy node" is a pretty poor way to explain the head and tail of a list. The definition of a dummy node from what you quoted is basically "a normal node without data". But this is not true. Should a head node have a pred? A tail have a succ? Can you add or remove the dummy node as you can with a normal node? Nope. Really, you should view the head and tail as just references or "pointers" to the actual nodes that are at the head and tail of the list. You have a DLL object with a header and tail reference, which is the standard way of approaching this. — MahlerFive
You're getting close. Now draw out exactly what you list looks like after each step. You should notice some problems. If not, try printing the list backwards from the tail (following the pred references) and you should notice a problem. — MahlerFive

Aaron Digulla Aaron Digulla · Accepted Answer · 2011-03-15T12:49:09

Instead of doing this all in your brain, sit down five minutes and draw the data structure (DLL and 2-3 couple of nodes) on paper.

Leave a gap and below that, draw how it would look with the node already inserted.

Mark all the changes you need to make with a marker pen. Give each change a number.

Now sit down and implement each change.

This sounds tedious but it will help you deeply understand what is going on. This way, you will have to do this only once.

If you're more the paper and scissors type, get pieces of string, cut out the nodes and glue post it notes to the end of the strings. Now you can use the strings as "references" between elements of your model.

How do I insert a new node before first node of a doubly-linked list?

2 Answers