Hello!

I am writing a code of linked list in which user can insert or delete names but the list must remain sorted alphabetically. I have written the given piece of code by now but it is not correct. Please help me out.
I took help from this link:

http://stackoverflow.com/questions/2941368/sorting-names-in-a-linked-list

//function to add a node
	void add(node *&pi,string newname)
	{
		node *temp;
		temp = new node;
    
		if(p== NULL)
		{
			temp->info= newname;
			temp->link=p;
			p=temp;
		}
		else
		{
			node *add;
			add = new node;
			bool done=true;

			while (p!=NULL)
			{
				if((p->info)>newname)
				{
					add->info= newname;
					add->link= p->link;
					done=true;
					break;
				}
				p=p->link;
			}
			if(done==false)
			{
				node *anew;
				anew=new node;

				anew->info=newname;
				anew->link=NULL;

				if(head==NULL)
				{
					head=anew;
					tail=anew;
					count++;
				}
				else
				{
					tail->link=anew;
					tail=anew;
					count++;
				}
			}
		}
	}

First of all, keeping a sorted linked-list is never useful, because it requires linear time for a look-up and linear time for insertion. Keeping it unsorted requires linear time for look-up and constant time for insertion, tha's much better. But I guess you are doing this as an exercise.

The algorithm you posted is very weird. Where is the logic in it? The variables names are incorrect (what is head, tail, count, and p, these are all undefined variables).

The pseudo-code for this algorithm is pretty simple and should be followed closely:
1) Create a new node X and store the string in it.
2) If the list is empty (head pointer == NULL),
then set the head node to X, and exit.
3) Find the node A in the list whose name is smaller than X->name, but whose next node is either NULL or with name larger than X->name.
4) If A->next == NULL ,
then A is the last node in the list and X simply is appended at the end of the list, by setting A->next = X; .
5) If A->next != NULL ,
then insert X between A and A->next, i.e. set X->next = A->next; and set A->next = X; .
6) If you are keeping track of the tail node, then, if tail->next != NULL , set tail = tail->next; .

That's all. Your algorithm looks nothing like the above. Also, you should not have more than one occurrence of new node; , because you are only adding one node, this is a clear indication that the logic is broken.

Edited 5 Years Ago by mike_2000_17: n/a

This article has been dead for over six months. Start a new discussion instead.