Doubly Linked List inserting in order

Question

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_++;

`while (temp->data > node->data)` will segfault if `temp` is null. Are you checking for null? — Drew Dormann, Aug 04 '22 at 18:01
@DrewDormann but my first condition is !head at the top isnt this do the job ? — Kuba Kluzniak, Aug 04 '22 at 18:04
After `temp = temp->next;`, what will happen next if `temp` becomes null? [Have you run this code in your debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Drew Dormann, Aug 04 '22 at 18:17
***but my first condition is !head at the top isnt this do the job?*** No it does not do the job in the case that temp becomes null because `temp->data > node->data` is true for every node in the list. — drescherjm, Aug 04 '22 at 18:19
i updated my question with your suggestion but still getting error — Kuba Kluzniak, Aug 04 '22 at 18:29
Your update still tries to evaluate `temp->data` if `temp` is null. — Drew Dormann, Aug 04 '22 at 18:33
Write a function to insert at a particular location (given by iterator or `Node*`). Test that. Write another function to find the correct insert location (like `std::lower_bound`). Test that too. Finally write a third function that calls one and then the other. Merging them all together has given you a function that's repetitive and over-complicated. — Useless, Aug 04 '22 at 18:34

Martin York · Accepted Answer · 2022-08-04T22:33:20.063

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 *
        **********                            **********

                             node
                               V
                          **********
                          *   next *
                          *   prev *
                          **********

After your code is run:

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

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

I would do:

Node* next = prev->next;

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

Thanks for that visualization i guess i need to put these puzzles correct in my mind . I need to add prev for node tho. — Kuba Kluzniak, Aug 04 '22 at 20:06

Doubly Linked List inserting in order

1 Answers1