Swapping And InsertSorted of a Singly LInked List

[HolaAmigo]

Hi,
I have completed almost everything but i was't able to implement my swapping and insertionsort function in a singly linked list. All i can think of is to physically sort and swap the nodes but i wasn't able to implement it.

#include <iostream>
#include <string>
using namespace std;


class Student
{

	friend ostream &operator<< (ostream &out, Student s); 
    friend istream & operator>> (istream &in,  Student &s);

	private:
		string roll_no;
		string name;
		double cgpa;
	public:
		Student();
		Student(string,string,double);
		void setName(string);
		void setcgpa(double);
		void setroll(string r);
		string getname();
		string getroll();
		double getcgpa();


/*Other public functions as needed you might need to overload certain operators*/
};


Student::Student()
{


	roll_no="";
		 name="";
		cgpa=0.0;

}

Student::Student(string r,string n,double gg)
{
	

	
	roll_no=r;
		 name=n;
		cgpa=gg;

}

double Student::getcgpa()
{
return cgpa;


}


string Student::getname()
{
return name;


}

string Student::getroll()
{
return roll_no;


}
void Student::setName(string n)
{
name=n;


}

void Student::setroll(string r)
{
roll_no=r;


}

void Student::setcgpa(double gg)
{
	cgpa=gg;

}


ostream & operator<< (ostream &out, Student s) 
{ 
 out<<s.getname()<<" ";
 out<<s.getroll()<<" ";
 out<<s.getcgpa()<<" ";

 return out;


} 
  
istream & operator >> (istream &in,  Student &s) 
{ 
	string n, r;
	float c;

    cout << "Enter the Name of the Student";
    in >>n;
	s.setroll(n);
	cout<<endl;

	cout << "Enter the roll number of the Student";
	in>>r;
	s.setroll(r);
	cout<<endl;

	cout << "Enter the cgpa of the Student";
	in>>c;
	s.setcgpa(c);
	cout<<endl;


    return in; 
} 
template <typename T>
class Node
{
public:
// constructor
	Node(T element);
//sets the KeyType data in the Node
	void setData(T pVal);
// returns the KeyType data in the Node
	T getData();
// returns the link to the next node
	Node* GetNext();
// sets the link to the next node
	void SetNext(Node *x);
private:
	T data;
	Node *link ;
};
template <typename T>
class SList
{
public:
// constructor of the Singly Linked List
	SList();
//Inserts the node pNew after the node pBefore
// if the list is empty, it makes pNew the first node of the list
	void Insert(Node<T>* pBefore, Node<T>* pNew);
//Deletes the node pToBeDeleted
	bool Delete(Node<T>* pToBeDeleted);
//prints the contents of the list
	void printList();
	Node<T>* getFirst()
	{
		return first;
	}

//ADD ONE OR TWO MEMBER FUNCTION(s) DIFFERENT FOR EACH LAB SECTION
	void reverse(Node<T>* temp);
private:
	Node<T> *first ;
};

template <typename T>
Node<T>::Node(T element)
{
	data = element;
	link = 0;
};


template <class T>
void Node<T>::setData(T pVal)
{
	data = pVal; 
};
template <class T>
T Node<T>::getData()
{
	return data;
};
template <class T>
Node<T>* Node<T>::GetNext()
{
	return link;
};
template <class T>
void Node<T>::SetNext(Node *x)
{   
    link = x;
	
};

/***************************************************************/
template<class T>
SList<T>::SList()
{
	first = NULL;
};
template <class T>
void SList<T>::Insert(Node<T>* pBefore, Node<T>* pNew)
{
	if(!first)
	{
		first = pNew;
	}
	else if(!pBefore && first)
	{
		pNew->SetNext(first);
		first=pNew;
	}
	else
	{
		pNew->SetNext(pBefore->GetNext());
		pBefore->SetNext(pNew);
	}
};
template <class T>
void SList<T>::printList()
{
	cout<<" *********************"<<endl;
      Node<T> *temp ;
	  temp=first;
	  int i=0;

    while(temp)
	{
		T test2 = temp->getData();
	    cout<<"Value in Node # "<< i+1<<" is "<<test2<<endl;
	    temp=temp->GetNext();
	    i++;
	}

};

template <class T>
bool SList<T>::Delete(Node<T>*pToBeDeleted)
{
	Node<T>*temp = first;
	
	if(pToBeDeleted=first)
	{
		first = first->GetNext();
	}
	else
	{
		while(temp->GetNext() != pToBeDeleted && temp!=NULL)
		{
			temp = temp->GetNext();
		}
		temp->SetNext(pToBeDeleted->GetNext());
	}
	return true;
};

template <class T>
void SList<T>::reverse(Node<T>* temp)
{
	
	if(temp)
	{
		reverse(temp->GetNext());
		cout<<temp->getData()<<" ";
	}
};

int main()
{

	SList<Student> *studlist;
	studlist = new SList<Student>();
	studlist->getFirst();

	
	//declare and initialize 3 students with random data
	Student *stu1 = new Student("L15-3452","Taha Lughmani", 3.45);
	Student *stu2 = new Student("L17-1526","Ahmed Hassan", 3.14);
	Student *stu3 = new Student("L19-1754","Ghulam Hussain", 2.78);
	//studlist->InsertSorted(*stu1);
	//studlist->InsertSorted(*stu2);
	//studlist->InsertSorted(*stu3);
	studlist->printList();
	//studlist->DeleteLast();
	//studlist->PrintList();
	studlist->reverse(studlist->getFirst());
	studlist->printList();
	delete studlist;

	SList<int> *ilist;
	ilist = new SList<int>;
	Node<int> *a, *b, *c, *d;
	b = new Node<int>(2);
	c = new Node<int>(3);
	d = new Node<int>(4);
	a = new Node<int>(1);
	ilist->Insert(0, a);
	ilist->Insert(a, b);
	ilist->Insert(b, c);
	ilist->Insert(c, d);
	ilist->printList();
	//studlist->swap(b, c);
	//ilist->PrintList();
	delete ilist;
	return 0;
	system("pause");
}

P.S I need to get this done within two days. Please Help me out.

[coder777]

Swapping in a singly linked list means removing the node at the old position and insert it at the new position. Thus you need to implement a remove function first.

[HolaAmigo]

template<class T>
void SList<T>::swapNodes(Node<T>*X, Node<T>*Y)  
{  
	int x=X->getData();
	int y=Y->getData();

	Node<T>*head;
	head=first;


// Nothing to do if x and y are same  
if (x == y) return;  
  
// Search for x (keep track of prevX and CurrX  
Node<T> *prevX = NULL;
X = head;  

while (X && X->getData() != x)  
{  
    prevX = X;  
    X = X->GetNext();  
}  
  
// Search for y (keep track of prevY and CurrY  
Node<T> *prevY = NULL;
Y = head;  
while (Y && Y->getData() != y)  
{  
    prevY = Y;  
    Y = Y->GetNext();  
}  
  
// If either x or y is not present, nothing to do  
if (X == NULL || Y == NULL)  
    return;  
  
// If x is not head of linked list  
if (prevX != NULL)  
    prevX->SetNext(Y);  
else // Else make y as new head  
    head = Y;  
  
// If y is not head of linked list  
if (prevY != NULL)  
    prevY->SetNext(X);  
else // Else make x as new head  
    head = X;  
  
// Swap next pointers  
Node<T>*temp = Y->GetNext();  
Y->SetNext(X->GetNext());  
X->SetNext(temp);  
}  

This is what i came up with but was unable to swap other nodes with the first one.
Also, i still haven't understood of how to insertsort with the given student data.

[jonnin]

honestly its easier to build the list sorted than to sort it after the fact.
you can also just swap data instead of nodes, and that is much more efficient if the data is smallish.

swapping the first node is just like any other, except you need to update the 'head' pointer as well.

your code looks broken for head, though.
if y is the head, then you need:
head = y; // you did this.
head next = old head next ... /// are you doing this? I do not see it?