C++ - adding a node to a circular linked list with sorting

Question

I have to create a circular linked list with a function, which adds a node on a particular position (the list should be sorted in ascending order by the value of a variable info). The function is called add_node. I thought that the best would be to create two pointers - to head and to the next node and then use while loop to compare next elements with a new node, and if it gets on a proper place - put it between those two. Unfortunately, the function works only when I add elements with smaller values than the biggest in list. How should this function look like to arrange the nodes correctly?

Code:

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

class Circular
    {
        struct node
        {
            int info;
            struct node *next;
        }*head;

    public:
        void create_node(int value);
        void add_node(int value);
        void display_list();
        Circular()
        {
            head = nullptr;
        }
    };

void Circular::create_node(int value)
{
    node *newnode;
    newnode = new node;
    newnode->info = value;
    if (head == nullptr)
    {
        head = newnode;
        newnode->next = head;
    }
    else
    {
        newnode->next = head->next;
        head->next = newnode;
        head = newnode;
    }
}

void Circular::add_node(int value)
{
    if (head == nullptr)
    {
        cout<<"List has not been created yet"<<endl;
        return;
    }

    node *newnode, *ptr2, *ptr1;
    newnode = new node;
    newnode->info = value;
    newnode->next=nullptr;

    ptr1=head;
    ptr2=head->next;
    while(newnode->info > ptr2->info)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;

        if(ptr2 == head) break;
    }
    ptr1->next = newnode;
    newnode->next = ptr2;

}
void Circular::display_list()
{
    node *s;
    if (head == nullptr)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    s = head->next;
    cout<<"Circular Link List: "<<endl;
    while (s != head)
    {
        cout<<s->info<<"->";
        s = s->next;
    }
    cout<<s->info<<endl<<endl;

}

int main()
{
    int choice, element;
    Circular cl;
    while (1)
    {
        cout<<"1.Create node"<<endl;
        cout<<"2.Add node"<<endl;
        cout<<"3.Display"<<endl;
        cout<<"9.Quit"<<endl;
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Enter the element: ";
            cin>>element;
            cl.create_node(element);
            cout<<endl;
            break;
        case 2:
            cout<<"Enter the element: ";
            cin>>element;
            cl.add_node(element);
            cout<<endl;
            break;
        case 3:
            cl.display_list();
            break;
        case 9:
            exit(1);
            break;
        default:
            cout<<"Wrong choice"<<endl;
        }
    }
    return 0;
}

Look carefully at add_node. head never changes. This is wrong. Your invariant is that head points to the largest element. You need to take this into account when inserting. When an element larger than the current maximum is inserted, you must adjust head. (You also need to fix the break condition, as the largest element needs to be inserted after the current head). Alternatively, make head point to the smallest element (and adjust it when an element smaller than the current minimum is inserted). — n. m. could be an AI
– n. m. could be an AI, Commented Nov 26, 2016 at 21:03
Pencil and paper are your friends here. Draw the list. Draw a node. Step by step draw in the changes to the linking required to put the node in place. Translate drawings to code. Off topic, cout<<"List has not been created yet"<<endl; offends my sensibilities.I would expect adding a node to an empty list to set that added node as the head. — user4581301
– user4581301, Commented Nov 26, 2016 at 21:03

Berek · Accepted Answer · 2016-11-26 22:37:52Z

0

I've come up with this:

void Circular::add_node(int value)
{
    node *newnode, *ptr2, *ptr1, *temp;
    newnode = new node;
    newnode->info = value;
    newnode->next=nullptr;

    if (head == nullptr)
    {
        head = newnode;
        newnode->next = head;
    }

    ptr1=head;
    ptr2=head->next;
    while(newnode->info > ptr2->info)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;

        if(ptr2 == head) break;
    }
    if( ptr2->info < newnode->info )
    {
        temp=new node;
        temp->info= ptr2->info;
        temp->next= ptr2->next;
        ptr2->next=newnode;
        newnode->next=temp->next;
        head=newnode;

        delete temp;
    }
    else
    {
        ptr1->next = newnode;
        newnode->next = ptr2;
    }

}

It seems that it works. However, I wonder is there a better way to do it?

answered Nov 26, 2016 at 22:37

Berek

11 bronze badge

Sign up to request clarification or add additional context in comments.

2 Comments

rcgldr Over a year ago

The code doesn't seem to handle the case of (newnode->info) < (head->info), where newnode will become the new head, and the last node's next pointer will need to be updated to point to the new head node (newnode). There's no need for a temp node in the case ptr2 == head when scanning for where to add a node.

Berek Over a year ago

Thanks for your comments, I'll try to improve the code.

rcgldr · Accepted Answer · 2016-11-27 19:21:18Z

0

If a node is inserted before head, then then the last node's next pointer is not updated to point to the new head node, and the code currently doesn't have an easy way to find the last node in the list.

The usual way to handle this is also have tail pointer (pointer to the last node). Since this is a circular list, you only need to maintain a tail pointer for the class, since head can be created at anytime using head = tail->next;

Optional: add_node can be updated to handle an empty list, eliminating the need for create_node.

edited Nov 27, 2016 at 19:21

answered Nov 27, 2016 at 0:12

rcgldr

29.4k3 gold badges41 silver badges70 bronze badges

Collectives™ on Stack Overflow

C++ - adding a node to a circular linked list with sorting

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related