Question

c++
modify the attached unsorted linked list class into a sorted linked list class

#include <iostream>
using namespace std;

template<class T>
struct Node {
    T data;//data field
    Node * next;//link field

    Node(T data) {
      this->data = data;
    }
};

template<class T>
class linked_list{
private:
      Node<T> *head,*current;
public:
      linked_list(){//constructor, empty linked list
        head = NULL;
        current = NULL;
      }

      ~linked_list(){
        current = head;
        while(current != NULL) {
          head = current->next;
          delete current;
          current = head;
        };

      }

      linked_list& add_node(int n) {//add a node at the end of the list

          if(head == NULL) {//empty list
            head = new Node<T>(n);
            head->next = NULL;
            current = head;
          } else {//non-empty list
            current->next = new Node<T>(n);
            current = current->next;
            current->next = NULL;
          }

          return *this;
      }

      void display(){
        //Node * tmp;
        current = head;
        while(current != NULL) {
          cout << current->data << endl;
          current = current->next;
        };
      }
};



int main() {

std::cout << "Hello World!\n";

linked_list<char> a;
a.add_node('a').add_node('c').add_node('b');
a.display();


return 0;
}

Answer 1

The sorting technique which i am going to use to sort the values of linked list is bubble sort . In sort() function , i have initialized two pointers namely start and end to point to head and NULL respectively . If the linked list is empty then it returns nothing. I have used a do-while loop until the end pointer points to the head node . In while loop the start pointer gets traversed upto the end pointer and compares the adjacent values . If the adjacent values are not in increasing order , then the values gets swapped using swap() function .

Note : in swap() function , the values gets swapped but not the pointers . we are not disturbing the pointers in the swap() function .

I have used a swapped variable so that after the values have been successfully sorted then the do-while loop should terminate . Please see my comments for better understanding .

CODE :

#include <iostream>
using namespace std;

template<class T>
struct Node {
T data;//data field
Node * next;//link field

Node(T data) {
this->data = data;
}
};

template<class T>
class linked_list{
private:
Node<T> *head,*current;
public:
linked_list(){//constructor, empty linked list
head = NULL;
current = NULL;
}

~linked_list(){
current = head;
while(current != NULL) {
head = current->next;
delete current;
current = head;
};

}

linked_list& add_node(int n) {//add a node at the end of the list

if(head == NULL) {//empty list
head = new Node<T>(n);
head->next = NULL;
current = head;
} else {//non-empty list
current->next = new Node<T>(n);
current = current->next;
current->next = NULL;
}

return *this;
}

void display(){
//Node * tmp;
current = head;
while(current != NULL) {
cout << current->data << endl;
current = current->next;
};
}
  

// BUBBLE SORT TECHNIQUE
void sort() // for sorting the values in a linked list
{
int swapped; // if all the values are in sorted order , then swapped is used to terminate the loop  
struct Node<T> *start=head;   
struct Node<T> *end = NULL;
  
/* Checking for empty list */
if (head == NULL)
return;
  
do
{
swapped = 0;
start = head;
  
while (start->next != end) // traversing the start pointer upto the end pointer
{
if (start->data > start->next->data) // comparing the adjacent values (bubble sort )
{
swap(start, start->next); // swapping the values if they are not sorted
swapped = 1; // inorder to run the loop again
}
start = start->next;
}
end = start; // traversing the end pointer in the reverse direction
}
while (swapped);
}

// for swapping the values of a and b
void swap(struct Node<T> *a, struct Node<T> *b)
{
T temp = a->data;
a->data = b->data;
b->data = temp;
}

};

int main() {

std::cout << "Hello World!\n";

linked_list<char> a;
a.add_node('a').add_node('c').add_node('b');
a.display();
a.sort();
cout<<"after sorting \n " ;
a.display();

return 0;
}

Answer 2

I only modified insertion method of above code. The idea is while inserting new node, we traverse through entire linked list and find first node which has greater data value than new node. Then we insert the new node before that node. Below is the code of entire program.

#include <iostream>
using namespace std;
template<class T>
struct Node {
T data;//data field
Node * next;//link field

Node(T data) {
this->data = data;
}
};
template<class T>
class linked_list{
private:
Node<T> *head,*current;
public:
linked_list(){//constructor, empty linked list
head = NULL;
current = NULL;
}

~linked_list(){
current = head;
while(current != NULL) {
head = current->next;
delete current;
current = head;
};

}

linked_list& add_node(int n)
{//add a node at the end of the list
  
if(head == NULL) {//empty list
head = new Node<T>(n);
head->next = NULL;
current = head;
}
else
{ //non-empty list
Node<T> *prev = NULL; // pointer to point previous node
current = head; // initalized with head
while (current!=NULL && current->data < n) // we traverse until n is greater
{
prev = current; // previous node
current = current->next; // moving to next node
}
if (prev==NULL) // if newly created should come first in list
{
head = new Node<T>(n); // making head as newly created list
head->next = current; // making head next as old head
  
}
else
{ // we are at a node with greater data value than n
prev->next = new Node<T>(n); // so we put new node in between previous and current nodes
prev->next->next = current; // new node next will be current
}
}
return *this;
}

void display(){
//Node * tmp;
current = head;
while(current != NULL) {
cout << current->data << endl;
current = current->next;
};
}
};

int main() {

std::cout << "Hello World!\n";

linked_list<char> a;
a.add_node('b').add_node('d').add_node('c').add_node('a').add_node('f');
a.display();

return 0;
}

add node method screenshot:

Sample output: