Question

Question: Write a C++ program to create a linked list and sort that list without the help of any other storage. The values of the list should be given by the user.
My Answer: #include
using namespace std;

//Compiler version g++ 6.3.0

struct node {
int data;
node *left;
node *right;
node *parent;
};

node *createNode(int data) {
node *n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
n->parent = NULL;
return n;
}

void inorder(node *root){
if(root != NULL){
inorder(root->left);
if(root->parent == NULL)
cout parent->data;
inorder(root->right);
}
}

node *insert(node *root, int data) {
node *temp1 = createNode(data);
node *temp2 = new node;
temp2 = root;
if(root == NULL){
root = temp1;
} else {
while(temp2 != NULL) {
if(temp2->data right == NULL) {
temp2->right = temp1;
//node *rchild = insert(root->right, data);
//temp2->right = rchild;
//rchild->parent = temp2;
break;
}
temp2 = temp2->right;
} else if(temp2->data > data) {
if(temp2->left == NULL) {
temp2->left = temp1;
//node *lchild = insert(root->left, data);
//temp2->left = lchild;
//lchild->parent = temp2;
break;
}
temp2 = temp2->left;
}
}
}
return root;
}


void search(node *root, int data) {
node *temp = new node;
temp = root;
while(temp != NULL) {
if(temp->data == data) {
cout data > data)
temp = temp->left;
else
temp = temp->right;
}
cout >n;
search(root, n);
cout >c;
if(c == 'y' || c == 'Y')
goto up;

}

How Many Marks Out Of 30 Can I Get?
Thank You.

Answer 1

Explanation:

Linked list is one of the most important data structures. We often face situations, where the data is dynamic in nature and number of data can’t be predicted or the number of data keeps changing during program execution. Linked lists are very useful in this type of situations.

The implementation of a linked list in C++ is done using pointers. You can go through the pointers chapter if you don’t have a strong grip over it. You can also practice a good number of questions from practice section.

A linked list is made up of many nodes which are connected in nature. Every node is mainly divided into two parts, one part holds the data and the other part is connected to a different node. It is similar to the picture given below.

linked list

Here, each node contains a data member (the upper part of the picture) and link to another node(lower part of the picture).

Notice that the last node doesn’t point to any other node and just stores NULL.

In C++, we achieve this functionality by using structures and pointers. Each structure represents a node having some data and also a pointer to another structure of the same kind. This pointer holds the address of the next node and creates the link between two nodes. So, the structure is something like:

struct node

{

int data;

struct node *next;

};

The first data member of the structure (named node) is an integer to hold an integer and the second data member is the pointer to a node (same structure). This means that the second data member holds the address of the next node and in this way, every node is connected as represented in the picture above.

The picture representing the above structure is given below.

node in linked list

And the picture representing the linked list is:

linked list in C

So, if we have access to the first node then we can access any node of the linked list. For example, if ‘a’ is a node then a->next is the node next to the ‘a’ (the pointer storing the address of the next node is named ‘next’)