I tried to insert a node before a given node by specifying the position of the node before which I want to insert the newnode. I got the data present inside that node's position and using a while loop, compared this data with each node's data till I reached the point where I was supposed to insert the node.
But when I tried displaying the elements using a while statement my program went into an infinte loop.I checked where the head node was pointing to and its to pointing to the first node of the singly list only. Could someone please help me out?
#include <iostream>
#include<stdlib.h>
using namespace std;
void display(struct node *);
struct node{
int data;
struct node *next;
};
struct node *ptr,*head=NULL;
void insertt(struct node *head){ //insert function to insert node before a node
struct node *ptr1=head;
int pos,poss,value;
cin>>poss; //getting position and value
cin>>value;
pos=poss-1;
while(pos--){ //moving to that position
ptr1=ptr1->next;
}
struct node *ptr2=ptr1;
struct node *newnode = (struct node*)malloc(sizeof(struct node)); //creating new node for insertion
newnode->next=NULL;
newnode->data=value;
struct node *preptr;
preptr=ptr1;
int c=ptr2->data; //getting value present in that particular position(node) of the list
while(ptr1->data!=c){ //inserting before node
preptr=ptr1;
ptr1=ptr1->next;
}
preptr->next=newnode;
newnode->next=ptr1;
display(head);
}
void display(struct node *head){ //displaying linked list
struct node *ptr2=head;
while(ptr2!=NULL){
cout<<ptr2->data;
ptr2=ptr2->next;
}
}
int main()
{
int n,val,i;
cin>>n; //number of nodes
for(i=0;i<n;i ){ //node creation
cin>>val;
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->data=val;
newnode->next=NULL;
if(head==NULL){
ptr=head;
head=newnode;
}
else{
ptr=head;
while(ptr->next!=NULL){
ptr=ptr->next;
}
ptr->next=newnode;
}
}
insertt(head); //insertion
return 0;
}
CodePudding user response：
- Once you find
ptr1, you setpreptrandptr2toptr1. - Then you get
c = ptr2->data, which happens to be the same asptr1->data. - And you go on and check
while (ptr1->data != c), which is always false. So that bottomwhileloop does nothing - And you get to the last lines with
preptrandptr1pointing to the same noden. - Now you make
n->next(preptr->next) point tonewnode, andnewnode->nextpoint toptr1(n): an infinite loop.
n newnode
-------- ---------
preptr ---> | c | | value |
ptr1 ---> -------- ---------
| next | ---> | |
| | <--- | next |
-------- ---------
void insertt(struct node *head) {
struct node *ptr1 = head;
int pos, poss, value;
cin >> poss;
cin >> value;
pos = poss - 1;
while (pos--) {
ptr1 = ptr1->next;
}
struct node *ptr2 = ptr1;
struct node *newnode = (struct node *) malloc(sizeof(struct node));
newnode->next = NULL;
newnode->data = value;
struct node *preptr;
preptr = ptr1; // ptr1, ptr2, and preptr point to the same node n
int c = ptr2->data; // c = ptr1->data too
while (ptr1->data != c) { // always false
preptr = ptr1;
ptr1 = ptr1->next;
}
preptr->next = newnode; // n->next = newnode
newnode->next = ptr1; // newnode-next = n
display(head);
}
CodePudding user response：
Here is a possible solution. to be honest your code was a bit messy and it was easier to just rewrite it. I am not sure what is the problem with your but you could compare with the code below and try to figure it out.
A couple of notes:
You do not need to have *ptr and *head as global variables it is better to keep them in the main.
The way you navigate over the list with the while loop to get to location is a bit unclear and you can do it with a for loop in a more readable way (in my opinion).
There is no error prevention/handling which makes me very nervous but if this is just for toying with, you should be fine
// Example program
#include <iostream>
#include<stdlib.h>
using namespace std;
struct node{
int data;
struct node *next;
};
void insertt( node *head, int pos, int val){ //insert function to insert node before a node
struct node *ptr = head;
struct node *next;
for (int i = 0; i < pos-1; i )
ptr=ptr->next;
next = ptr->next;
ptr->next = (struct node*)malloc(sizeof(struct node)); //creating new node for insertion
ptr->next->data = val;
ptr->next->next = next;
}
void rdisplay(struct node *head){ //displaying linked list
struct node *ptr=head;
if(ptr!=NULL){
if (ptr->next!=NULL)
rdisplay(ptr->next);
cout<<ptr->data <<std::endl;
}
}
void fdisplay(struct node *head){ //displaying linked list
struct node *ptr=head;
if(ptr!=NULL){
std::cout << ptr->data << std::endl;
if (ptr->next!=NULL)
fdisplay(ptr->next);
}
}
int main()
{
struct node *ptr = NULL,*head=NULL;
int n,val,i;
std::cout << "Incert number of values to have in the list:";
cin>>n; //number of nodes
for(i=0;i<n;i ){ //node creation
std::cout << "Incert value for node[" << i << "]:";
cin>>val;
struct node *newnode = (struct node*)malloc(sizeof(struct node));
newnode->data=val;
newnode->next=NULL;
if(head==NULL){
head=newnode;
}
else{
ptr=head;
while(ptr->next!=NULL){
ptr=ptr->next;
}
ptr->next=newnode;
}
}
std::cout <<std::endl;
std::cout <<std::endl;
fdisplay(head);
std::cout <<std::endl;
std::cout <<std::endl;
int pos;
std::cout << "At which position do you want to incert: ";
cin>>pos; //getting position and value
std::cout << "What value do you want to incert: ";
cin>>val;
insertt(head, pos, val); //insertion
std::cout <<std::endl;
std::cout <<std::endl;
fdisplay(head);
std::cout <<std::endl;
std::cout <<std::endl;
return 0;
}