Thread: Inserting alphabetically into a Linked List

I'm having trouble figuring out how to do this. I think I'm sort of close.

Code:

void compclass::addstudent(char tname[]) {
	student *newstud = new student;
	student *head = studentlist;
	student *tail = studentlist;
	int count = 0;
	
	if (count >= 1) {
		head = studentlist->retnext();
	}
	newstud->setname(tname);
	if (studentlist == NULL) {
		newstud->setnext(NULL);
		studentlist = newstud;
		count++;
		return;
	}
	else {
		if (strcmp(tail->retname(), newstud->retname()) > 0) {
				newstud->setnext(studentlist);
				studentlist = newstud;
				return;
			}
		while (strcmp(head->retname(), newstud->retname()) < 0) {
			
			if (strcmp(head->retname(), newstud->retname()) < 0) {
				newstud->setnext(head);
				tail->setnext(newstud);
				return;
			}
			tail = tail->retnext();
			head = head->retnext();
		}
		tail = newstud->retnext();
		newstud = head->retnext();
	}
}

It just goes into an infinite loop, because somehow I'm linking them to each other. If I add it to where it's alphabetically lower, it works fine. When I add something alphabetically higher however, it actually looks to add ok. But when I try to print the list of students, that's when it goes into the loop.

> while (strcmp(head->retname(), newstud->retname()) < 0)
I think you need to cater for the case when the new node is appended to the end of the list

Code:

while ( head != NULL &&
        strcmp(head->retname(), newstud->retname()) < 0)

If you exit the loop with head == NULL, then you need to append the new node to the end of the list

Apart from the initial test, you don't use the tail variable, so there seems to be no point updating it

> if (count >= 1)
Why is this a special case?

Yeah, my code really makes no sense the more I look at it. I actually changed the count statement to

Code:

 if (studentlist != NULL)

No luck though getting this function to work properly though...

Ok, well, I got it partially working now. It will add on to the top of the list and to the end of the list, but will not add any names in between. So i can add say, John, then I can add Jim, then add Stuart. But If I try to add Kim, it just doesn't show up. Here's my code now:

Code:

void compclass::addstudent(char tname[]) {
	student *newstud = new student;
	student *head = studentlist;
	student *tail = studentlist;
	
	
	if (studentlist != NULL) {
		tail = studentlist->retnext();
	}
	newstud->setname(tname);
	if (studentlist == NULL) {
		newstud->setnext(NULL);
		studentlist = newstud;
		
		return;
	}
	else {
		if (strcmp(head->retname(), newstud->retname()) > 0) {
				newstud->setnext(studentlist);
				studentlist = newstud;
				return;
			}
		if ((strcmp(head->retname(), newstud->retname()) < 0) && (tail == NULL)) {
			head->setnext(newstud);
			newstud->setnext(NULL);
			return;
		}
		while (tail != NULL && strcmp(tail->retname(), newstud->retname()) < 0) {
			if (strcmp(tail->retname(), newstud->retname()) > 0) {
				newstud->setnext(tail);
				head->setnext(newstud);
				return;
			}
			tail = tail->retnext();
			head = head->retnext();
			if (tail == NULL) {
				head->setnext(newstud);
				newstud->setnext(NULL);
			}
			
		}
		
		
	}
}

Ok, I think I got it working now. In case anyone wants to see what seems to be working code, here it is:

Code:

void compclass::addstudent(char tname[]) {
	student *newstud = new student;
	student *head = studentlist;
	student *tail = studentlist;
	
	
	if (studentlist != NULL) {
		tail = studentlist->retnext();
	}
	newstud->setname(tname);
	if (studentlist == NULL) {
		newstud->setnext(NULL);
		studentlist = newstud;
		
		return;
	}
	else {
		if (strcmp(head->retname(), newstud->retname()) > 0) {
				newstud->setnext(studentlist);
				studentlist = newstud;
				return;
			}
		if ((strcmp(head->retname(), newstud->retname()) < 0) && (tail == NULL)) {
			head->setnext(newstud);
			newstud->setnext(NULL);
			return;
		}
		while (tail != NULL && strcmp("head"->retname(), newstud->retname()) < 0) {
			if (strcmp(tail->retname(), newstud->retname()) > 0) {
				newstud->setnext(tail);
				head->setnext(newstud);
				return;
			}
			tail = tail->retnext();
			head = head->retnext();
			if (tail == NULL) {
				head->setnext(newstud);
				newstud->setnext(NULL);
			}
			
		}
		
		
	}
}

Only one change since my last post, so it may be hard to see, so I put Quotes around the change.