sorted doubly-linked list

[ogward]

Hi there!
I've been trying to make this doubly-linked list and so far I've made an add() and an destructor.
I first started with making an add function singly-linked and when I tried to add an Item to the list I got memory leaks so I thought if I made it doubly-linked somehow the leaks will disappear. But now my add doesn't work at all, it crashes and then when I debug it complains about line thats //.
The list is doubly-linked but it doesn't have a last pointer, only a first.

template <typename T>
void SortedList<T>::add(const T & item)
{
	Node *e=new Node (item);
	if(this->first!=NULL)
	{
		if(this->first->value<item)
		{
			e->next=this->first;
			this->first=e;
			(this->first->next)->prev=this->first;

		}
		else
		{
			Node * walker=this->first;
			while(walker->next!=NULL&&item<walker->next->value)
				walker=walker->next;
				
			
			e->next=walker->next;
			walker=this->first;
			while(walker->next->next!=NULL &&item<walker->next->value)
				walker=walker->next;
			
			walker->next=e;
			//walker->next->next->prev=walker->next;
		
		}


	}

	else
	{
	e->next = this->first;
	this->first=e;
	
	}
	this->nrOfNodes++;
}

destructor

template <typename T>
SortedList<T>::~SortedList()
{
	if(this->nrOfNodes>0)
	{
		Node *walker=this->first->next;
		while(walker!=NULL)
		{
			this->first=walker->next;
			delete walker;
			walker=this->first;
		}
	}
}

few pairs of Internet eyes are better than one, any kind of help is appreciated.

[D80DSL3A]

When your code reaches line 21 I think you want to insert the new node e between walker and walker->next.
Lines 21 and 26 are good but I don't get what is going on in lines 22-24. I don't think they belong.
I think the linkage you want is:

e->next=walker->next;// existing line 21 is OK
e->prev = walker;// point e back to preceding node
walker->next->prev = e;// point following node back to e
walker->next = e;// existing line 26 is OK 

Another point. If you ever were to iterate through your list in reverse (using the prev pointers) then you will want first->prev = NULL so you have a way of detecting that first has been reached.
I suggest you assign first->prev = NULL; following lines 11 and 37.

[ogward]

Thanks for replying!
When I remove my code on lines 22-24 and replace it with your code my console crashes and points to (walker->next)->prev=e;, then when I add first->prev = NULL to lines 11 and 37 it crashes also but then it points to line 37.
what could be the problem?

[D80DSL3A]

It could be because I forgot to consider that the while loop (lines 23,24) may end because walker->next = NULL, as when adding a 2nd node to the list when item < first->value (it appears you are sorting in descending order).
In this case only assign a value to walker->next->prev if it exists.
ie:

if(walker->next)
    (walker->next)->prev=e;

Sorry about that and I hope that's the problem.
I can't imagine why first->prev = NULL would cause a crash unless first = NULL.
When does it crash? When the first node is added? The second?
Is your list created empty, or with an initial node (in the constructor)?

I figured I was qualified to respond to your thread because I have written my own sorted list template class and it's working. If my advice is bogus please feel free to ignore it!
I'll review my own code and see if I can find anything else.

[ogward]

no, I appreciate your help.
Looks like the add function works now and I don't get any memory leaks, my problem now is that when I remove the first item from the list and then try to "cout" the first value in the list the console crashes :-/
The only thing I can think of is that when the first value is removed that the pointers aren't assigned as they should...

[D80DSL3A]

Glad that (apparently) did the trick.

I found that my own class was a singly linked list, so I modified it to be doubly linked (it seemed like a good exercise). It's working now. If you continue having trouble with your remove() then please post it.

My remove() takes a value (item) to search for. The first node found with value == item->value is removed. I suppose a remove() could be written to take a pointer to the node to be removed, instead of an item. Which way does yours work?

[ogward]

my list is a "sorted doubly-linked list" so items are sorted in a ascendant order
(does it make sense? :S) when they are added.
So my remove function should only remove the first node.
It shouldn't be complicated to implement such a function but I think that I'm doing something wrong with my this->first->next->prev because the first node is deleted so I think I have to redefine that pointer to point to something else.

Hope you understand, If I don't figure it out Ill post it.