Thread: Alphabetical Linked List Insertion

Hey guys, I'm trying to figure out what's wrong with my code. The goal here is to insert linked list entries alphabetically. The basic construct of this program is as follows: You start off with a base list of nodes called p2d nodes (they are brought in automatically through the command line). These nodes are connected to one another vertically. From each one of these base nodes extends another linked list in a horizontal direction (conceptually that is). These horizontal nodes are called p1d nodes. These p1d nodes are the ones I'm trying to insert alphabetically. The variable "first" represents the first horizontal p1d attached to the vertical p2d node. Here is the code segment of interest:

Code:

if(p2d->first==NULL){
           p2d->first=p1d;
	   }
	   else{
		while(strcmp(p2d->first->name, p1d->name) != 1){
			p2d->first=p2d->first->next;
		}
			p1d->next= p2d ->first;
			p2d->first = p1d;
						
	 }

you must consider that strcmp() returns a value greater than 0 if the second string is greater (aphabetically) than the first, 0 if they are equal and a value less than 0 otherwise, plus I suggest to use a binary search tree to do this kind of thing, since the use of strcmp at every iteration is quite a waste of space

Originally Posted by iMalc

Well you had it right up to the word "otherwise".
But then I kept reading and found that you'd suggested a binary search on a linked-list (which is a no-no). Then you suggested that using strcmp repeatedly wastes space, which makes no sense at all, as the amount of space required for iteratively searching a list, or using strcmp, is constant.

I think we're waiting to hear back from the OP now.

Yes you're right, I have expressed myself wrong (I'm not english), what I'm suggesting is to insert each string into a binary search tree which is lg(N) on the average case, instead of making an insertion sort into a singly linked list, I'd make something like:

Code:

struct node* sorted_insert(struct node* node, char* string)
{
if(node == NULL) return newNode(string);
else {
if(strcmp(string, node->string) <= 0) node->left = sorted_insert(node->left, string);
else node->right = sorted_insert(node->right, string);
}

Isn't it better than doing an insertion sort into a singly linked list?