sorted doubly linked list

**alzar** · 01-01-2008

We have got this code in order to insert a value into a list sorted

Code:

void insertValue(node *newNode)
{
   node *curr, *prev;

   curr = nodeHead;  // nodeHead is a global
   prev = NULL;
   
   // Scan for place to insert (sorted numerically)
   while (curr && curr->data < newNode->data)
     {
	prev = curr;
	curr = curr->next;
     }
   
   // Update pointers
   newNode->next = curr;
   newNode->prev = prev;
   
   if (prev == NULL)
     nodeHead = newNode;
   else
     prev->next = newNode;
   
   if (curr == NULL)
     nodeTail = newNode;
   else
     curr->prev = newNode;
}

Why the code works also without the last if statement?
can anyone tell me what is nodetail(probably is the last node of the list)
in the main program there is no where decleration of nodetail.
Thanks

**tabstop** · 01-01-2008

Originally Posted by alzar

Why the code works also without the last if statement?

It doesn't. The "true" part triggers when the list is empty, or the new element sorts to the back of the list (to set nodeTail to the last (or maybe, only) member of the list).

can anyone tell me what is nodetail(probably is the last node of the list)
in the main program there is no where decleration of nodetail.
Thanks

I would guess that nodeTail is declared on the same line as nodeHead (or maybe one line after it). If you didn't find it, check your capitalization (if the code compiled, the variable was declared!).

**alzar** · 01-01-2008

will the code work if i put
current = newNode; instead of
nodeTail = newNode;

**tabstop** · 01-01-2008

Originally Posted by alzar

will the code work if i put
current = newNode; instead of
nodeTail = newNode;

Well, but what is current supposed to be? That's not defined anywhere.

You'll need nodeTail if you ever plan to walk the list backwards (i.e., starting at the end of the list and working your way back home). If you do plan to do that, then you need to keep nodeTail set correctly in this manner. If you don't ever plan to do that (and your code doesn't ever plan to do that, either) then you can get away without having nodeTail around. However, you still need that if statement with the else part, because that's what sets the backward link to the new element.

**alzar** · 01-01-2008

so can anyone correct the code to work good?
I also need to walk the list backwards
Thanks

**tabstop** · 01-01-2008

What was wrong with the code you originally posted?

**alzar** · 01-01-2008

Originally Posted by tabstop

What was wrong with the code you originally posted?

we didn't know what nodetail was? So as i asked if we put current you said that it will not work.What must we put in nodetail or how should i declare it(or what nodetail is: maybe the last node) in order to work the code as i want?Thanks

**iMalc** · 01-01-2008

Originally Posted by alzar

so can anyone correct the code to work good?
I also need to walk the list backwards
Thanks

There isn't really anything wrong with the original code you posted.
Any time you said that the code would work if you did XXXXX, you were wrong and the original code is right.

You need to show effort if you want us to help you make it work backwards.

**tabstop** · 01-01-2008

nodeTail is the end of the list, just as nodeHead is the beginning. They should be declared and initialized together, wherever that is in your program.

**alzar** · 01-01-2008

Originally Posted by tabstop

nodeTail is the end of the list, just as nodeHead is the beginning. They should be declared and initialized together, wherever that is in your program.

so i declare it initial in the programm like as struct node *nodetail=NULL;
and then in a while loop and something like :
curr = curr->next;
i will find the last node(which is nodetail).Am i correct?

**tabstop** · 01-01-2008

Originally Posted by alzar

so i declare it initial in the programm like as struct node *nodetail=NULL;

Sounds fine.

Originally Posted by alzar

and then in a while loop and something like :
curr = curr->next;
i will find the last node(which is nodetail).Am i correct?

Well, why would you need to find it? As you meddle with the list (inserting or deleting elements), you update nodeTail (and nodeHead, for that matter) as necessary. If you add an element at the back of the list, you make sure nodeTail points there now. (That's what we were doing originally.) If you delete an element from the back of the list, you make sure nodeTail points to the previous node that is now the end of the list.

**alzar** · 01-02-2008

Thanks I understand it

Thread: sorted doubly linked list

Thread Tools

Search Thread

Display

sorted doubly linked list-why this code work

Similar Threads

singly linked to doubly linked

Linked List Help

Contest Results - May 27, 2002

Linked list with two class types within template.

singly linked list