CODEWITHSUNDEEP
algorithmdata-structureslinked-list
Ranju
Ranju

Reputation: 76

Insert and delete in a multi level sorted linked list

2->7->8->11

|

13->16->17->21

|

22->23->27->29

|

30->32

Sorted Linked List given like above where each node has 2 pointers next and down. For each row starting nodes down points to next row start. Each row has 4 elements, except last one which can have <= 4 elements. Next rows start element is greater than previous rows end element. We need to design and code for it insert of new value at correct place and delete operation. I could not solve this problem.

Upvotes: 0

Views: 245

Answers (1)

Mohammed Meraj
Mohammed Meraj

Reputation: 116

Structure representation and Pseudo code for the add operation is as follows And we can implement the delete recursively using the add data as example

typedef struct sibling{
    int data;
    struct sibling *nxt;
} t_sibling

typedef struct children {
    struct sibling  *sibling;
    struct children *nxt;
} t_children;


add_element(t_children **head, int newdata)
{
    t_children *walk_down = *head;
    t_children *parent  = NULL;
    
    while (walk_down != NULL) {
        if(parent == NULL && Compare newdata < head of current walk_down->sibling) {
            // Code comes here when we add 1 to above mentioned list example
            newdata is added to begining to head of walk_down->sibling
            sibling_list_count++;
            if (sibling_list_count > 4) {
                taildata = delete_end from tail of walk_down->sibling
                add_element(&walk_down, taildata)
            }
            break;
        }
        else if(newdata < head of current walk_down->sibling) {
        
            if (Compare newdata > tail of parent sibling) {
                // Code comes here when we add  12 to above mentioned list
                newdata is added to begining to head of walk_down->sibling
                
                if (sibling_list_count > 4) {
                    taildata = delete_end from tail of walk_down->sibling
                    add_element(&walk_down, taildata)
                }
            }
            else {
                // Code comes here when we add 6 to above mentioned list
                newdata is added to the appropriate location of parent of sibling
                Since above step disturbs the <= 4 property we 
                taildata = delete_end from tail of parent->sibling
                add_element(&walk_down, taildata)
            }
            break;
        }
            
        parent = walk_down;
        walk_down = walk_down->nxt;
    }
}

Upvotes: 1

Related Questions