Click here to Skip to main content
15,944,731 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
FULL QUESTION :
Implement a doubly linked list having all unique elements with the following operations:

I - Inserts element alternately at the head and at the end. return 0;

S pos1 pos2 - Shuffles the list by removing nodes from position pos1 to position pos2. Assume the head or first node is at position 1, pos1 and pos2 are always valid and pos1 is always less than equals to pos2. This operation removes nodes from pos1 to pos2 and form a new circular doubly linked list from them having node at pos1 as the starting node of this circular structure. This newly formed circular doubly linked list gets attached at the end of an already existing list. If nodes at pos1 and/or pos2 lie(s) in the previously formed circular doubly linked list structure then removal of these nodes should be handled as per the circular structure.

D - Displays the list. Nodes affected due to shuffle operation form a circular structure. All such nodes get displayed in reverse order with the starting node (of the circular structure) printing twice. The unaffected nodes get printed normally starting from head of the list. The sequence of operations start with all I, later followed by either S or D.

What I have tried:

C++
#include<iostream>
using namespace std;

class node
{
    public:
        int data;
        node* next;
        node* prev;
};

node* head=NULL;

void print()
{
    node* p=head;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}

node* pushtail()
{
    int data;
    cin>>data;
    node* newnode=(node)malloc(sizeof(node));
    newnode->data=data;
    newnode->next=NULL;

    if(head==NULL)
    {
        head=newnode;
        newnode->prev=NULL;
    }
    else 
    {
        node p=head;
        while(p->next!=NULL)
            p=p->next;

        p->next=newnode;
        newnode->prev=p;
    }

    return head;
}

node* pushhead()
{
    int data;
    cin>>data;
    node* newnode=(node*)malloc(sizeof(node));
    newnode->data=data;
    newnode->prev=NULL;
    newnode->next=head;
    head=newnode;

    return head;
}

int main()
{
    int n,data;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        if(i%2==0)
           pushhead();
        else if(i%2!=0)
           pushtail();
    }

    print();
}
Posted
Updated 19-Sep-22 13:46pm
v4
Comments
Rick York 19-Sep-22 2:33am    
It didn't all get posted. Some is missing. Also - remember to add the code tags around it.
Morbeus777 19-Sep-22 2:35am    
DONE
Morbeus777 19-Sep-22 3:48am    
please help me solve this
Richard MacCutchan 19-Sep-22 4:26am    
Since node is a class you should use new and a proper constructor to create them. The use of malloc/calloc in C++ code should be avoided.

1 solution

I have a recommendation. That is to make yourself one function that creates a new node item. Currently you have the code essentially duplicated in two places and that is not a good idea. Try something like this :
C++
node * createNode()
{
    cout << "enter data : ";
    int data;
    cin >> data;

    node* newnode = new node;
    newnode->data = data;
    return newnode;
}
and then pushhead becomes :
C++
node* pushhead()
{
    node* newnode = createNode();
    newnode->next = head;
    head = newnode;
    return head;
}
The node class needs a constructor :
C++
class node
{
public:
    int data;
    node* next;
    node* prev;

public:
    node()   // constructor - thanks Richard
    {
        data = 0;
        next = nullptr;
        prev = nullptr;
    }        
};
Another thing : you really don't need the head node to be a global variable. You can pass it where it's needed and if it needs to be modified then you can pass its address or a reference to it. For example, pushhead would be modified to look like this :
C++
node * pushhead( node ** phead )
{
    node* newnode = createNode();
    newnode->next = * phead;      // dereference the pointer to a pointer
    * phead = newnode;            // the newnode is now the head
    return newnode;
}
The function pushhead doesn't look right to me. With a doubly-linked list the previous node item should be set but in that function it is never set it. It is always null. It is set in pushtail but I think it should also be set in pushhead. In pushhead, the old list head's previous will be the new node. That is, in a typical doubly-linked list implementation it is. Note that you set both next and previous item pointers in pushtail but not in pushhead so I think you should do it in pushhead also.
 
Share this answer
 
v2
Comments
Richard MacCutchan 19-Sep-22 4:27am    
"calloc zeros the new memory"
Since it's a C++ class it should use 'new' and a proper constructor.
Rick York 19-Sep-22 4:35am    
good point. I hadn't even look at that.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900