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

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 D开发者_StackOverflowLL 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

---

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.

---

It looks like most of your confusion is around how header works. It is just a reference to the first node in the list. Also, there is no need for an "auxiliary" node.

Lets look at the steps you need to take in order:

Step 1: Set the pred of the node you are inserting.

Since the node will become the first node, it will have no nodes behind it, so you can say v.pred = null;

Step 2: Set the succ of the node you are inserting.

Our new node needs to point forward to the old first node. Here's where the confusion comes. You do the following:

v.succ = header.succ ; // point new node succ to current first node

But what is header? It is a reference to the first node. By saying header.succ you are saying you want the first nodes successor, which is the second node. When you see header just think "first node" and you will come up with:

v.succ = header;

Step 3: Point the old first node back to the new node

You already are doing this step correctly (remember, think header is "first node"):

header.succ = v ; //point header to new node

Step 4: Now make the new node the header

header = v;

EDIT (in response to your edit #3): There are some issues about this whole approach which I'll bring up at the end, but those aside for now and assuming you are required to set up your list this way...

Assuming you're passing in the first node of the list (Header.succ) as v, let's take the same steps:

Step 1: Set the pred of the node you are inserting.

You want your new node to point back toward Header. v.pred = Header;

Step 2: Set the succ of the node you are inserting.

You want your new node to point to the old first node, which was Header.succ

v.succ = Header.succ;

Step 3: Point the old first node back to the new node

Make sure you check that a first node exists first (forgot this in my first post)!

if (Header.succ != null) {
    Header.succ.pred = v; // Header.succ is the first node, and you want to set its pred reference
}

Step 4: Now make the new node the first node

Header.succ = v;

Note how you don't even need z since you can get to the first node using Header.succ. This means you shouldn't need it as a parameter.

Now, all that aside there are some issues you should think about:

What is the point of a Header having a pred reference and a data field? What is the point of a Tail having a succ reference and a data field?

If you wanted to use this linked list and insert items, wouldn't it be better if you just had to call add() for every item instead of addFirst() and addBeforeFirst()? What if you could a remove() method, then you'd have to keep track of if the list is empty or not to figure out which method to call, addFirst() or addBeforeFirst(), which is kind of ugly. It's better to write a more generalized add() which takes care of this for the user who is going to use the list.