const keyword in CPP
June 12, 2012
Delete a linked list
June 12, 2012

Insert in a sorted linked list

Given a linked list, with all the nodes in sorted order. Write a function that inserts a new integer in the sorted manner. i.e If the list is as given below:

3 -> 6 -> 9 -> 10 -> 15

And if you want to insert 8 in this list, it should be inserted as below:

3 -> 6 -> 8 -> 9 -> 10 -> 15

Solution:

Let us assume that the LinkedList class is as given below:

    class LinkedList
    {
        public:
            LinkedList(): head(NULL){};
            LinkedList(int n) {};
            void printList();		 // Print the linked list
            void insertSorted(int n);	 // Insert in a sorted list
        private:
            Node* head;
    };

The structure of Node is as given below:

    struct Node
    {
        int data;
        Node* link;
        // Constructor
        Node(int n):data(n), link(NULL) {}
    };

Ideally this Node should be a template and class LinkedList should also be a template, but our purpose is not a good design but writing just a function to insert in the sorted list.
The definition of insertSorted function is like shown below:

    void LinkedList::insertSorted(int n)
    {
        Node *temp = NULL;
        // Inserting at the head of the list.
        if(head == NULL || head->data > n)
        {
            temp = new Node(n);
            temp->link = head;
            head = temp;
            return;
        }
        // Inserting anywhere else.
        temp = head;
        // Moving to the point where insertion need to be done.
        while( temp->link != NULL && temp->link->data < n )
        {
            temp = temp->link;
        }
        Node *t = new Node(n);
        t->link =  temp->link;
        temp->link = t;
}

Please let me know your feedback / comments.

Leave a Reply

Your email address will not be published. Required fields are marked *