Have i miswired when trying to insert a new node at the middle of doubly linked list?

Question

Structure looked like:

class DList{
private:
        struct Elem {
        Elem *prev, *next;
        };
        Elem *_head, *_tail;
}

Now I have two existing node: cur and cur->next, and i wanna insert a new node ins between them. Here's what i did:

    cur->next = ins;//step-1-1 cur
    ins->prev = cur;//step-1-2 cur

    ins->next = cur->next;//step-2-1 cur->next
    cur->next->prev = ins;//step-2-2 cur->next 

The problem is in further traverse loop of my program my pointer cannot reach _tail anymore. Did i mishook something in my insertion part? (The loop works perfectly once i comment the insertion at middle codes above)

Answer 1

Key is to not lose the values which are going to be used later on. Your first line of code cur->next = ins; makes you lose the original value (cur->next); thereafter you really don't know who will be next to ins.

Use this logic to insert a new node in middle. Lets say initially,

cur - cur->next  
    |
  [ins]

Do,

ins->next = cur->next;

(cur) (ins) - (cur->next) {Assume - for next, and = for next and prev}

cur->next = ins;

(cur) - (ins) - (cur->next)

ins->prev = cur;

cur = ins - (cur->next)

ins->next->prev = ins;

cur = ins = (cur->next)

Answer 2

Yep, there's a miswiring here. Let's draw pictures!

Imagine things look like this, initially:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | ----------------------> |   next   | --> ...
         +----------+                         +----------+
 ... <-- |   prev   | <---------------------- |   prev   | <-- ...
         +----------+                         +----------+
                           +----------+
                           |   next   |
                           +----------+
                           |   prev   |
                           +----------+
                                ^
                                |
                                ins

First, you execute cur->next = ins;, which does this:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
                           +----------+
                           |   next   |
                           +----------+
                           |   prev   |
                           +----------+
                                ^
                                |
                                ins

Notice that we no longer have a pointer to the element that was originally after curr - oops! That'll be a problem later.

Now, we do ins->prev = curr;, which looks like this:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
               ^           +----------+
               |           |   next   |
               |           +----------+
               +---------- |   prev   |
                           +----------+
                                ^
                                |
                                ins

Now, we write ins->next = curr->next;. But oops! Notice that curr->next points to ins, so we just added a cycle in here:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
               ^           +----------+
               |           |   next   | --+
               |           +----------+   |
               +---------- |   prev   | <-+
                           +----------+
                                ^
                                |
                                ins

And finally, you write cur->next->prev = ins; But oops! curr->next is still prev, so we get another cycle:

             curr
              |
              v
         +----------+                         +----------+
         |   next   | -----------+            |   next   | --> ...
         +----------+            |            +----------+
 ... <-- |   prev   | <----------+----------- |   prev   | <-- ...
         +----------+            v            +----------+
                           +----------+
                       +-> |   next   | --+
                       |   +----------+   |
                       +-- |   prev   | <-+
                           +----------+
                                ^
                                |
                                ins

The issue here is that you lose track of the cell pointed at by curr->next after the first assignment, so you lose the ability to look in the right place.

What if you start off by writing something like this?

DList* next = curr->next;

and then use next instead of curr->next in some of these contexts?