Search code examples
c++data-structuresdoubly-linked-listcircular-list

circular doubly linked list insertion at the end


I was going through dsa doubly circular list, and was practicing insertion of elements to it, after entering the first element my program ends abruptly.....is there a mistake in my insertafterfunction.i get a segmentation fault error .just help me through I cant find what has gone wrong..

#include<iostream>
struct Node{
    int data;
    Node* next;
    Node* prev;
};
Node* headnode;    
void insert(int data){
    Node* newnode = new Node;
    newnode->data= data;
    newnode->next=headnode;
    newnode->prev=headnode;
    headnode=newnode;
}
void insertafter(int data){
    Node* newnode=new Node;
    newnode->data=data;
    newnode->next=headnode;
    Node* existingnode = headnode;
    while(existingnode->next!=headnode){
        existingnode=existingnode->next;
    }
    existingnode->next=newnode;
    newnode->prev= existingnode;
    headnode->prev=newnode;

}


void printnode(){
    Node* newnode=headnode;
    while (newnode->next!=headnode){
        std::cout<<newnode->data<<"->";
        newnode=newnode->next;
    }
    std::cout<<"\n";
 
}    
int main(){
    headnode=NULL;
    int x,data;
    std::cin>>x;
    for(int i=0;i<x;i++)
    {
        std::cin>>data;
        if(i==0)
        {
            insert(data);
        }
        else
        {
            insertafter(data);
        }
        printnode();
    }
}

Solution

  • For example this while loop within the function insertafter

    while(existingnode->next!=headnode){
        existingnode=existingnode->next;
    }
    

    invokes undefined behavior because after calling the function insert data members prev and next of the head node are equal to nullptr.

    See the function insert

    void insert(int data){
        Node* newnode = new Node;
        newnode->data= data;
        newnode->next=headnode;   // here headnode is equal to nullptr
        newnode->prev=headnode;   // And here headnode is equal to nullptr
        headnode=newnode;
    }
    

    It seems you mean at least the following function definition

    void insert(int data){
        Node* newnode = new Node;
        newnode->data= data;
        headnode=newnode;
        newnode->next=headnode;
        newnode->prev=headnode;
    }
    

    That is after calling the function data members prev and next of the head node will point to the head node itself.

    In general the separate function insert does not make a sense because it may be called (provided that it will be written correctly) only once.

    Also the function printnode will output nothing if the list contains only the head node due to the condition in the while statement

        Node* newnode=headnode;
        while (newnode->next!=headnode){