CODEWITHSUNDEEP
c++linked-listiteration
EmilDo
EmilDo

Reputation: 1177

Sorted insert using Linked List

I have some difficulties to implement one iterative function for sorted insert in linked list. I have previously done that with recursion which is much easier when the insert() function is called, but here I am a bit confused with how to implement the (l->data < data) condition:

typedef struct E_Type * List;

struct E_Type
{
  int data;
  struct E_Type* next;
};

and the function:

insert(List & l, int data){
  if (l == 0 || l->data > data){
    List new_list = new E_Type;
    new_list->data = data;
    new_list->next = l;
    l = new_list;
  }
  else if (l->data < data){
    List new_list = new E_Type; 
    new_list->data = data;
    new_list->next = l; //i am shooting in the dark with this one
    l = new_list;
  }
}

Upvotes: 0

Views: 122

Answers (1)

NPE
NPE

Reputation: 500207

I won't code this up for you, but will offer some hints.

Fundamentally, there are two cases:

  1. The element being inserted becomes the new head. In this case, you need to update l.
  2. The element being inserted does not become the new head. In this case you need a loop.

If I were you, I'd work through both cases using pen and paper first.

Upvotes: 2

Related Questions