I need to write a function that insert valuse in order for doubly linked list e.g

I have an int list that contains: [3, 4, 6, 9, 10] and the input is 7, then the list should be updated to contain: [3, 4, 6, 7, 9, 10]

I tried to write but i get segmentation fault

LinkedList is already sorted , I only need to put the value in the right place.

template <typename T>
void LinkedList<T>::insertOrdered(const T& newData) {
  Node *node = new Node(newData);
  if(!head_){
    head_ = node;
    tail_=node;  
  }else{
    if(node->data < head_->data){
      head_->prev = node;
      node->next = head_;
      head_=node;
    }
    else if(node->data > tail_->data){
      tail_->next = node;
      node->prev = tail_;
      tail_ = node;
    }
    else{
      Node *temp = head_;
      Node *prev = nullptr;
      
      while (temp->data > node->data || temp != NULL) {
        prev = temp;
        temp = temp->next;
      }

      prev->next = node;
      temp->prev = node;
      node->next = temp;
     
    }
  }
  size_  ;
}

Thanks evryone for help i found a bug and this is working code for me :)

  Node *node = new Node(newData);

  if(!head_){
    head_ = node;
    tail_=node;  
  }else{
    if(node->data < head_->data){
      head_->prev = node;
      node->next = head_;
      head_=node;
    }
    else if(node->data > tail_->data){
      tail_->next = node;
      node->prev = tail_;
      tail_ = node;
    }
    else{
      Node *temp = head_;
      Node *prev = nullptr;
           
      while (temp!=NULL) {
        prev = temp;
        temp = temp->next;
        if(temp->data > node->data){
          break;
        }
      }
        prev->next = node;
        node->prev = prev;
        temp->prev = node;
        node->next = temp;
    }
  }
  size_  ;

CodePudding user response：

There seems to be something missing here:

  prev->next = node;
  temp->prev = node;
  node->next = temp;

If we look at the chain before and after:

Before your code is run:

           prev 
             V             
        **********                            **********
        *   next *--------------------------->*   next *----->
    <---*   prev *<---------------------------*   prev *
        **********                            **********

                             temp
                               V
                          **********
                          *   next *
                          *   prev *
                          **********

After your code is run:

           prev 
             V             
        **********                            **********
        *   next *----*                 * --->*   next *----->
    <---*   prev *<*--------------------------*   prev *
        ********** |  |                 |     **********
                   |  |                 |
                   |  |      temp       |
                   |  |        V        |
                   |  |   **********    |
                   |  --->*   next *----|
                   |------*   prev *
                          **********

Seems like one of the links has not been set correctly.

CodePudding user response：

while (temp->data > node->data || temp != NULL) {

You need to switch the NULL check here. You are first accessing the data at temp, then checking to make sure temp isn't NULL. If temp is NULL you will still segfault because you do a dereference before a check. Try

while (temp != NULL && temp->data > node->data) {