Insertion sort

Code:

void insertionSort()
	{
		node* temp=head;	
		
		while(temp->next != NULL)
		{
			node* second =temp->next;
			if (second->exponent==temp->exponent)
			{
				temp=temp->next;
			}
			else
			{
				second->previous->next=second->next;
				second->next->previous=second->previous;
				
				if (head->exponent > second->exponent)
				{
					second->next=head;
					second->previous=NULL;
					head->previous=second;
					head= second;
				}
				node* current = head->next;
			
				while(current->exponent < second->exponent)
				{
					current=current->next;
				}
				second->next=current;
				second->previous=current->previous;
				current->previous->next=second;
				current->previous=second;
			}
		}
	}

I have made insertion sort funtion for a doubly linked list , but its not working , i cant figure out the errors.If anybody can guide a bit. =|

Perhaps you've overcomplicated it. You could ignore the case where an item is greater than all items inserted thus far:

Code:

template <class TItem>
void InsertionSort(TItem *&head) {
	TItem *newList = NULL, *oldList = head;
	while (oldList != NULL) {
		//take an item off the old list
		TItem *temp = oldList;
		oldList = oldList->next;
		TItem *curr = newList, *prev = NULL;

		//find the place in the new list for this item
		while (curr != NULL) {
			if (*temp < *curr)
				break;
			prev = curr;
			curr = curr->next;
		}
		//put the item in the new list
		if (prev == NULL)
			newList = temp;
		else
			prev->next = temp;
		temp->next = curr;
	}
	head = newList;
}

Sure that's slower for an already sorted list, but we're not using InsertionSort for sorting long lists anyway, if we know what's good for us.

I dun know how to work with the templates i would be thankful, if u point out where my code needs to changed i would be thnakful.

I have made a doubly linked list of polynomials and now i am using operator overloading to add two polynomials. The add function see its the exponents of the two polynomials are same and then add them. It returns the only node after addition whose addition is being done, but i want to get the whole list of polynomials , whether they are added or not.
e.g
1x^1 2x^2 when added with 1x^1 3x^6
gives
2x^1 2x^2 3x^6
So kindly tell how to insert the terms (those whose exponents dont match) to the result list.

Code:

	list operator + (const list& k)
	{
		node* first;
		first = head;
		node* second;
		second = k.head;
		
		node* result=head;
		list r;
		
		while (first != NULL)
		{
			while (second != NULL)
			{
				if (first->exponent == second->exponent )
				{
					
					result->coefficient	=first->coefficient + second->coefficient;
					result->exponent=first->exponent;
					
				}
				second=second->next;
			}
			first=first->next;
		}
		r.insert(result->coefficient,result->exponent);
		return r;
	}

Originally Posted by Fatima Rizwan

I dun know how to work with the templates i would be thankful, if u point out where my code needs to changed i would be thnakful.

Just ignore that first line and call it with any type you like that has a member called 'next'.

Okay so the code I posted was for a singly-linked list, but it's easy enough to add a few more lines to hook up the links in the opposite direction.

The thing about your code is that it's uncommented and not easy to understand. To be honest, there is no one-line change to make that fixes it. Even this line:

Code:

while(temp->next != NULL)

is wrong because it will crash when head is NULL.

Ok thnks . And what about the second problem

Code:

if (first->exponent == second->exponent )
				{
					result->coefficient	=first->coefficient - second->coefficient;
					result->exponent=first->exponent;
					r.insert(result->coefficient,result->exponent);
                  // AFTER INSERTION I WANT TO DELETE THE NODE OF FIRST AND SECOND whose exponent are same, but m having problem with this. 
				
				}