sorted insert and linked lists

[towelrack]

Hi, I posted the other day but removed it because I thought it was a bit sloppy and because I thought I had figured out the solution. However, I'm still having the same problem.

The custom CompareTo(book a, book b) method returns true if book a comes before book be alphabetically. Otherwise, it returns false. I've already done a lot of testing on it and it works just fine.

void BookList::Insert(Book *newBook){

	BookNode *node = new BookNode(newBook);
	
	if (head == NULL){   //makes node the new head if the list is empty
		head=node;		
	} 
	else if (CompareTo(node, head)==true) {  // if node is less than head
		node->next = head;               // node is linked to head
		head = node;                     // node is made the new head
                                       //this is where i think the problem is
	}

//finally, this for loop walks through the linked list making comparisons //between "node", and temp is made to represent the next node in the list at //the end of the loop.


	else{
		for(BookNode *temp = head; temp->next != NULL; temp=temp->next ){
  
//in every iteration, node is checked against temp. if "node" is less than temp //it is inserted between temp and the node after temp

			if(CompareTo(node, temp->next)==true){      
				node->next = temp->next;  
				temp->next = node;
				break;
			}

//if temp is the last node in the list, "node" is made the tail.

			if( temp->next == NULL ){     
				temp->next = node;       
				node->next = NULL;
			}
		}
	}
}

The input is:
F title
D title
G title (G comes after D)
A title
E title (E comes after A)
H title (H comes after E)

I've been messing around with the input and it seems that when I try to insert information that is already in alphabetical order, it won't work. It only inserts items that are out of order. G, E, and H are not inserted.

The output is:

A title
D title
F title

I've already tried separating this in to three methods (insertion at head, insertion in body, insertion at tail) with similar results. If anyone would be willing to explain to me how to sort a singly linked list by insertion it would be greatly appreciated, thanks.

[kempofighter]

Not enough info for someone reading this thread. Comment your code better. I have no idea what your intentions are. I have no idea what compareTo return value means. I assume that means that the two things are equal? However I cannot see the function to determine if it is correct. I'm not sure why you are only doing '==' tests. That seems like an error to me. It seems like you ought to be doing a '<' test and looping when head != NULL. The second block is unnecessary if you code the for loop correctly. If the list isn't empty there should be a loop that determines where to put the new node. I only see two top level branches that are necessary but you are trying to do it with 3. when you get to the node where the next == NULL and haven't inserted then you know that the new node has to be put at the end.

Post a more complete example that is as minimal as possible. All that we need to see is the complete linked list as well as a simiple main function that attempts to insert data within a loop. By the way what is the debugger telling you? This is the kind of problem that is typically very easy to debug.

[towelrack]

sorry about that, I put the comments outside of the code.

I'm trying to set this up so that it can either insert something alphabetically in to an empty list, or a list that already has one or more items in it.

the CompareTo(node a, node b) method will return true if node a comes before node b, otherwise it will return false. The CompareTo method itself takes information as two nodes then executes a "getbook" function on both nodes, which gets the title contained within the node, before comparing them alphabetically

The main method separately inputs 6 titles(no loop) beginning with the letters F, D, G, A, E, H. Currently, the linked list only seems to be storing the titles that have been inserted out of order so the list looks like this: A, D, F.

If I were to change the input to insert the titles in this order "A, D, E, F, G, H" the list would only contain "A". If I insert it in the reverse order "H, G, F, E, D, A" the list contains "A, D, E, F, G, H".

The insert method should be inserting everything in to the list, not just the stuff that is input out of order.

the debugger seems to be telling me that the problem lies in the "else if" statement. Rather than inserting the new node, its just replacing the old one.