Sorted insert using Linked List

Question

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;
  }
}

NPE · Accepted Answer · 2012-12-10 23:18:49Z

2

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

Fundamentally, there are two cases:

The element being inserted becomes the new head. In this case, you need to update l.
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.

answered Dec 10, 2012 at 23:18

NPE

503k114 gold badges970 silver badges1k bronze badges

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

1 Comment

Voo Over a year ago

Or go with the clever implementation and use a dummy head which greatly simplifies the code.

Collectives™ on Stack Overflow

Sorted insert using Linked List

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related