Singly Linked List Question

Jun 20, 2011 at 5:17am
Just starting to learn about linked lists, and I need to enter a last name and a GPA as a char and float respectively into a node, and then sort the list in numerical order of GPA (ascending or descending, doesn't matter).

Would I write this as:
	typedef struct Node;
	{
		char name[20];
		float gpa;
		Node *next;
	};


and then just do for loops to arrange them in order?
for( temp1 = head ; temp1!=NULL ; temp1 = temp1->next )
{
      for( temp2 = temp1->next ; temp2!=NULL ; temp2 = temp2->next )
      {
            if( temp1->data > temp2->data )
            {
                  temp = temp1->data;
                  temp1->data = temp2->data;
                  temp2->data = temp;
            }
      }
}


Thanks.
Jun 20, 2011 at 7:23am
You don't really want to sort singly linked lists.
If you need a singly linked list and need it sorted try it this way:
* create a vector out of your singly linked list
* sort the vector
* create a singly linked list out of the sorted vector

If you have really expensive to copy nodes consider using a vector that hold's just pointers to the data.

Have a look at this page:
* http://www.cplusplus.com/reference/algorithm/sort/

Jun 20, 2011 at 7:25am
As for OP's actual question, your algorithm looks fine to me.
Jun 20, 2011 at 7:40am
Thanks huge. Writing the structure like that though
		char name[20];
		float gpa;

will sort the GPA's and not the last names in ascii, right? I wasn't sure which should go first.

@onur thanks for the tip, I'll give it a gander after I finish some of this work that's piling up lol.
Jun 20, 2011 at 8:13am
closed account (D80DSL3A)
Another option is to swap the links instead of swapping the data.
This way, you don't have to swap each individual data element.
Jun 20, 2011 at 9:34am
If you prefer to stay with your version at least use the swap template:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for( temp1 = head ; temp1!=NULL ; temp1 = temp1->next )
{
      for( temp2 = temp1->next ; temp2!=NULL ; temp2 = temp2->next )
      {
            if( temp1->data > temp2->data )
            {

                  temp = temp1->data;
                  temp1->data = temp2->data;
                  temp2->data = temp;

                  std::swap(temp1->data, temp2->data)
            }
      }
}


Also note that the "data" used in the comparison (your key usde for sorting is gpa) is not the same as in the swap part (both name and gpa)!
Topic archived. No new replies allowed.