# Thread: Sorting singly linked list using insertion sort and deleting certin nodes

1. ## Sorting singly linked list using insertion sort and deleting certin nodes

So the whole concept is to sort a singly linked list using insertion sort and deleting the nodes in order. The other codes are given, so all I have to do is fill in the "void InsertNode(int v)" and "void DeleteNode(int v)" and I am having trouble with it.

The result should be something like:
50 30 20 10 70 80 60 90 100 40
50 is inserted
30 is inserted
20 is inserted
...
100 is inserted
10 20 30 40 50 60 70 80 90 100
Good Job!
50 is deleted
10 20 30 40 60 70 80 90 100
30 is deleted
10 20 40 60 70 80 90 100
20 is deleted
10 40 60 70 80 90 100
10 is deleted
40 60 70 80 90 100
70 is deleted
40 60 80 90 100
80 is deleted
40 60 90 100
60 is deleted
40 90 100
90 is deleted
40 100
100 is deleted
40
40 is deleted
But mine would be like:
50 30 20 10 70 80 60 90 100 40
50 is inserted
30 is inserted
20 is inserted
...
100 is inserted
0
Good Job!
0
0
0
0
0
0
0
0
0
0
Code:
```#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
class Node{
public:
int value;
Node *next;
};
public:
}
void SubMain(){
bool result;
UniqueRandomData(10);
CallInsertNode();
PrintNode();
result=CheckNode();
CallDeleteNode();
}
void UniqueRandomData(int n){
int i, j, k, temp;
this->n=n;
x=new int[n];

for(i=0; i<n; i++)
x[i]=(i+1)*10;

for(i=0; i<n; i++){
j=rand()%n;
k=rand()%n;

temp=x[j];
x[j]=x[k];
x[k]=temp;
}

for(i=0; i<n; i++)
cout<<x[i]<<" ";
cout<<endl;
}

void InsertNode(int v){
cout<<v<<" is inserted."<<endl;

}
else
{
}
}
}
void PrintNode(){
while(cur!=0){
cout<<cur->value<<" ";
cur=cur->next;
}
cout<<endl;
}
void CallInsertNode(){
int i;
for(i=0; i<n; i++)
InsertNode(x[i]);
}

bool CheckNode(){
while(cur !=NULL && cur->next !=NULL)
if(cur->value > cur->next->value){
cout<<"Error!"<<endl;
cout<<cur->value<<", "<<cur->next->value<<endl;
return false;
}
else
cur=cur->next;

cout<<"Good job!"<<endl;
return true;
}

void CallDeleteNode(){
int i;
for(i=0; i<n; i++){
DeleteNode(x[i]);
this->PrintNode();
}
}

void DeleteNode(int v){
while(current->value != v)
{
current = current->next;
prev = prev->next;
}
if(current->value == v)
{
prev->next = current->next;
delete current;
}

cout<<v<<" is deleted.";
}

private:
int *x;
int n;

};
int main(){
a.SubMain();
}```

2. I was going to look at your code only, it doesn't even compile.

3. Originally Posted by Aslaville
I was going to look at your code only, it doesn't even compile.
strange 'cause it does in my dev c++

4. Originally Posted by maria32
strange 'cause it does in my dev c++
May be you made a mistake when pasting ? Well, I can see for instance you have a class definition which is not followed by a semi-colon - that should not compile anywhere.

5. Originally Posted by Aslaville
Well, I can see for instance you have a class definition which is not followed by a semi-colon - that should not compile anywhere.
It is not that there is a class definition which is not followed by a semi-colon: both class definitions are terminated with semi-colons. The problem is that there is an extra closing brace on line 56 (or 57, if you prefer), causing the compiler to mistake it as a class definition that is not terminated with a semi-colon when parsing the code.

6. okay so I corrected the code
Code:
```#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
class Node{
public:
int value;
Node *next;
};
public:
}
void SubMain(){
bool result;
UniqueRandomData(10);
CallInsertNode();
PrintNode();
result=CheckNode();
CallDeleteNode();
}
void UniqueRandomData(int n){
int i, j, k, temp;
this->n=n;
x=new int[n];

for(i=0; i<n; i++)
x[i]=(i+1)*10;

for(i=0; i<n; i++){
j=rand()%n;
k=rand()%n;

temp=x[j];
x[j]=x[k];
x[k]=temp;
}

for(i=0; i<n; i++)
cout<<x[i]<<" ";
cout<<endl;
}
void InsertNode(int v){
cout<<v<<" is inserted"<<endl;

Node* node=new Node();//new Node

while(cur!=NULL){
Node *prev=cur;
cur=cur->next;
if(node>prev && node<cur)
cur=prev->next;
else if(node<prev){
prev=node;
cur=prev;
}
}
}
void PrintNode(){
while(cur!=0){
cout<<cur->value<<" ";
cur=cur->next;
}
cout<<endl;
}
void CallInsertNode(){
int i;
for(i=0; i<n; i++)
InsertNode(x[i]);
}

bool CheckNode(){
while(cur !=NULL && cur->next !=NULL)
if(cur->value > cur->next->value){
cout<<"Error!"<<endl;
cout<<cur->value<<", "<<cur->next->value<<endl;
return false;
}
else
cur=cur->next;

cout<<"Good job!"<<endl;
return true;
}

void CallDeleteNode(){
int i;
for(i=0; i<n; i++){
DeleteNode(x[i]);
this->PrintNode();
}
}
void DeleteNode(int v){
cout<<v<<" is deleted."<<endl;

Node *delNode=cur;

while(cur!=NULL)
find(cur, delNode, );

cur=cur->next;
delete delNode;

}

private:
int *x;
int n;

};
int main(){
a.SubMain();
return 0;
system("pause");
}```
I fixed the codes for void InsertNode(int v) and void DeleteNode(int v) since these are the ones I have to solve and I don't know what to do with the find() in the void deleteNode(int v) btw.

7. Originally Posted by maria32

I don't know what to do with the find() in the void deleteNode(int v) btw.
Do you need the function 'find', I guess not. Myself I could have had.

Code:
```
void DeleteNode(int v){
cout<<v<<" is deleted."<<endl;

Node *previous = head; //you will need to keep track of both the previous and current node.
Node *delNode=cur;

while(cur!=NULL)
if(cur->value == v)
{
previous->next = delNode->next; //link previous node to next node skipping the one that matched.
delete delNode;
return;
}
previous = cur; //move one node next
cur=cur->next;
}```
And of course, I just wrote this out on the browser so I could have missed something.

You should probably also return something as an indicator of either successful deletion or failure( none of the nodes contain the value v)