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
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments