Sorted insert into Linked List

Question

i have been working with this iterative function since Sunday without any success, I want to create iterative function for sorted insert but after hour of node drawings, I think i would need some help with the function:

struct declaration:

  typedef struct E_Type * List;

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

the function:

bool insert(List & l, int data) {
    while (l != 0) {
        for (List p = l; p; p = p->next) {
            if (p->data == data)
                return false;
        }

        if (l->data > data) {
            List new_list = new E_Type;
            new_list->data = data;
            new_list->next = l;
            l = new_list;
            return true;
        } else if (l->data < data) {

            List new_list = new E_Type;
            new_list->data = data;
            l->next = new_list;
            l = new_list;
            return true;
        }
    }

    if (l == 0) {
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
        return true;
    }
}

btw: is this function even possible... all tutorials, infos etc about this insertion are with recursive call for next-data

Answer 1

//find the closest Node that is not > data and return it
List* find(List* l, int data) {
    // l != NULL
    List* current = l;
    List* previous = NULL;

    while(current != NULL && current->data > data) {
        previous = current;
        current = current->next;
    }

    return previous;
}

List* insert(List* l, int data) {
    //l != NULL
    List* current = new List();
    current->data = data;

    if(l->data > data) {
        List* insert_position = find(l, data);
        current->next = insert_position->next;
        insert_position->next = current;
    } else {
        current->next = l;
        return current;
    }
    return l;
}

---

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

You don't really need the typedef or struct keywords.

The above example should be close to what your looking for. There are a few issue with what you had as pointed out.

Answer 2

I can see how you have gotten stuck. Your insert function tries to do multiple tasks (check for duplicates, find where to insert a new element and do the actual insertion) and the steps needed for each task have gotten muddled up.

My best advice is to take a step back and write three functions:

1. Make function that checks if an element already exists (lets call it bool find_element(List l, int data)).
2. Make a function that inserts a new element at the front of an existing list and returns the new list (List insert_front(List l, int data)). This function can make use of the fact that each element of a List can be regarded as the head of a list as well.
3. Make a function that determines where to insert a new element (List locate_insertion_point(List l, int data)).

4. Write your insert function in terms of the three new functions.

   bool insert(List& l, int data)
   {
       if (find_element(l, data))
           return false;
   
       List insert = locate_insertion_point(l, data);
       if (insert == NULL)
       { /* Can't insert after any point. Insert at the front */
           List new_list = new E_Type;
           new_list->data = data;
           new_list->next = l;
           l = new_list;
       }
       else
       { /* insert after insert */
           List next = insert->next;
           insert->next = insert_front(next, data);
       }
       return true;
   }
   

Answer 3

The struct looks fine. I've tried to keep insert's structure as close as possible to yours. I hope the comments can help you see what you did wrong.

bool insert( List & l, int data ) {
    // We have to look sequentially at all members in the *ordered* list
    while ( l != 0 ) {
         // We already have this data, we exit
         if ( l->data == data ) return false;
         // If this element's data is bigger we shift it by one spot
         // so we can insert the new one
         else if ( l->data > data ) {
              List new_element = new E_Type;
              // Save current element in the new one ( that will shift )
              new_element->data = l->data;
              new_element->next = l->next;
              // "Insert" our new element
              l->data = data;
              l->next = new_element;
              return true;
         }
         // If we didn't return before, we skip to the next element
         // but only if it's not the end
         if ( l->next )
             l = l->next;
         else
             break;
    }
    if ( l ) {
        // If we are here it means that all elements are lower than the new data.
        // l currently holds the last element of the list, so we only need to add
        // a new element to the list
        List new_element = new E_Type;
        new_element->data = data;
        new_element->next = 0;
        l->next = new_element;
        return true;
   }
   else {
        // If we are here it means that there was no list to begin with.
        // Thus, we have to create a first element.
        l = new E_Type;
        l->data = data;
        l->next = 0;
        return true;
   }
}

Answer 4

There's a lot of mistakes:

l->next = new_list;

This line erases previous value of pointer l->next.

There's no code that looks for proper element to insert new element before of after.

Your while has no sense since your l pointer doesn't change from iteration to iteration.

You better just write in the piece of paper elementary steps your function should do and only after that code them in C++.

(Or just use working sample from neighbor answer ;-) )