Ask coding questions

← Back to all posts
[Double-linked lists] There's problems in my insert() method, I cant figure out why.
TuanTran17 (0)

When insert() at tail(), the contents of the list is incorrect. In other words, the order of the list is in correct.
You can run the code to see where the problem is. main.cpp has all the test to determine my double-linked lists is efficient.

My codes are in dlist.hpp / main.cpp is the tester

Answered by Highwayman (1483) [earned 5 cycles]
View Answer
Comments
hotnewtop
Highwayman (1483)

the conditional code beginning on line 62 inserts the node after the tail instead of before.

 # else if(cur-> next == nullptr)   [[value = 1, previous = _head/_tail]]
 # null <- 0 -> null
 # (null <- 0 -> n) (null <- n -> null)
 # (null <- 0 -> n) (0 <- n -> null)
 # (null <- 0 <-> n -> null)
 # (null <- 0 <-> 1 -> null)
 
 # else   [[value = 2, previous = _tail]]
 # (null <- 0 <-> 1 -> null) (null <- n -> null)
 # (null <- 0 -> n) (null <- n -> null) (0 <- 1 -> null)
 # (null <- 0 -> n) (0 <- n -> null) (0 <- 1 -> null)
 # (null <- 0 -> n) (0 <- n -> 1) (0 <- 1 -> null)
 # (null <- 0 -> n) (0 <- n -> 1) (n <- 1 -> null)
 # (null <- 0 <-> n <-> 1 -> null)
TuanTran17 (0)

@Highwayman can you elaborate more on it? I don't think I get it yet.

Highwayman (1483)

Sure. I accidentally pointed out the wrong thing anyways kind of.

Basically, in the last two cases of your insert method, the actual effects are changed slightly. This makes it clear that one of these ways is doing your insert incorrectly. In order to fix this, you have to change the behavior of one of these conditional blocks to match the other.

let's look at your code.

    // Insert a new value, after an existing one. If previous == nullptr, then
    // the element is added *before* the head (or, if the list is empty, 
    // becomes the new head).
    // Must run in O(1) time.
    void insert(node *previous, int value){
      node* n = new node{value, nullptr, nullptr};
      node* curr = _head;
      if(empty()){
        _head = n;
        _tail = n;  
      }
      else if(previous == nullptr){
        n->next = _head;
      }
      else if(curr == nullptr){
        return;
      }
      else if(curr->next == nullptr){
        _tail->next = n;
        n->prev = _tail;
        _tail = n;
      }
      else{
        node* nex = curr->next;
        curr->next = n;
        n->prev = curr;
        n->next = nex;
        nex->prev = n;
      }  
    }

Ok, so looking at the comment, we see that the correct behavior of this function is to link in a new node after the passed node (previous).

// Insert a new value, after an existing one.

But we have one of your cases not linking the node in after, but before the given node, specifically the else code block:

else{
  node* nex = curr->next; // (null <- 0 <-> 1 -> null) (null <- n -> null)
  curr->next = n; // (null <- 0 -> n) (null <- n -> null) (0 <- 1 -> null)
  n->prev = curr; // (null <- 0 -> n) (0 <- n -> null) (0 <- 1 -> null)
  n->next = nex; // (null <- 0 -> n) (0 <- n -> 1) (0 <- 1 -> null)
  nex->prev = n; // (null <- 0 -> n) (0 <- n -> 1) (n <- 1 -> null)
  // (null <- 0 <-> n <-> 1 -> null)
}  

This is your incorrect behavior. I hope that's more helpful :)

@TuanTran17

TuanTran17 (0)

@Highwayman I see what you mean, ill work on it.

Highwayman (1483)

um. I know this is kind of unrelated, but

      node(int value, node* next, node* prev) :
          value(value), next(next), prev(prev)
        { }

seems kinda dangerous...