Doubly Linked List class - InsertAfter method 2

[weevilofdoom]

well, I've got this generic doubly linked list written, all except for the InsertAfter method, this seems to be giving me some trouble. Anyways, I think I'll share what I've got, and if anybody has any input, please please please help.


What I'm doing here is inserting a node after the node
that contains "data". So, we've got access to the node class via friends.

template <typename U>
void DLList<U>::InsertAfter(U newData, U data)
{

DLListNode<U>* temp = new DLListNode<U>;
DLListNode<U>* tempHead = head;

temp->m_data = newData;

if(IsEmpty())
throw &quot;Empty List!&quot;;

//if head and tail are the same:
else if(head->m_data == tail->m_data)
{
temp->prev = tail;
temp->next = 0;
tail = temp;
}
//if the node is off the tail:
else if(tail->m_data == data)
{
temp->prev = tail;
if(tail != NULL)
{
tail->next = temp;
}
tail = temp;
}
//else it's in the middle (TROUBLE HERE !!! )
else
{
while(tempHead->m_data != data)
{
/*
if(tempHead->m_data == data)
{
temp->next = tempHead;
tempHead->next = temp;
temp->prev = tempHead;
}
*/
tempHead = tempHead->next;
/*
if(tempHead == NULL)
{
throw &quot;Node not found.&quot;;
return;
}
*/
}

head = temp;
}



//ARGH! Couldn't figure this out for the life of me, I AM SO STUPID!
}

 

[BoulderBum]

I'm wondering what m_data is. Is it an index of the node in the tree? I assume not, and if I'm right, then saying something like &quot; else if(head->m_data == tail->m_data)&quot; is dangerous, because different nodes can have the same data independant of other nodes. &quot;head&quot; may have the same data as &quot;tail&quot; and still be a different node. Just a heads up.

A note about your final blocks:

[tt]
else
{
while(tempHead->m_data != data)
{
tempHead = tempHead->next;
}
head = temp;
}

The above should find the data, but your problem is saying &quot;head = temp&quot;. &quot;head&quot; should never change if this is an InsertAfter function. Rather look at it this way...

If you have 4 nodes:
head tail
1-> 2-> 3-> 4-> NULL

and you want to insert a fifth after node 2, then you would change 2's &quot;next&quot; pointer to point to 5 ( 2-> 5 ) and assign 5's &quot;next&quot; pointer to point to 3 ( 5-> 3 ) such that:


head tail
1-> 2-> 5-> 3-> 4-> NULL

As you can see, the head and tail did not change.

In the case of a doubly-linked list, you not only make the manipulations shown above, but you change a couple of more pointers. Namely, you set 3's &quot;previous&quot; pointer to 5 (5<-3) and set 5's &quot;previous&quot; pointer to 2 (2<-5) such that:

(for previous pointers)
head tail
NULL <-1 <-2 <-5 <-3 <-4

If you do both of the above steps, you will acheive what you want to do.

PS- conceptually, it would help to change the name of &quot;tempHead&quot; to &quot;current&quot;.

PSS- what if the data is never found? you don't account for that.
[/tt]

 

[jgartee]

May I make a suggestion? Take a look at the STL as an alternative to building these sort of routines on your own. I've found it a wonderful tool to avoid much of the mundane grunt work I used to have to do...it's been a real timesaver.