1

I am using a bubble sort to change the nodes positions. I understand there are a few situations to be aware of if node 1 is at the beginning of the list. If node 2 is at the end of the list. If node1 is at the beginning and node2 is at the end. So I believe the issue is when I am swapping nodes that are neighbors as in node1->next_ = node2; because if I do my regular swap i end up with node2->next_ = node2.

I would like to know if I am on track because I tried something similar to what I wrote and ended up infinitely loop. I think there is something I am not understanding like I am losing a pointer somewhere.

I believe this is correct except for the case of if the 2 nodes are neighbors in the linked list.

edit clarified naming of links. reverted to original. 

void swap(struct student_record_node** node1, struct student_record_node** node2)
{

  struct student_record_node *p1, *x1, *n1, *p2,*x2,*n2, *temp;

  p1 = (*node1)->prev_;
  x1 = *node1;
  n1 = (*node1)->next_;

  p2 = (*node2)->prev_;
  x2 = *node2;
  n2 = (*node2)->next_;

  /* swap next_  */

  if (p1 == NULL && n2 == NULL)
  {



  /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
    /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = NULL;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;

    /* step 5 swap node2 next to be node1 next */
    (*node1)->next_ = NULL;
    /* step 6 swap node2 prev to be node1 prev */
    (*node1)->prev_ = n2;
    /* step 7 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;


  }
  else if (p1 == NULL)
  {
   /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
     /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = NULL;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;

    /* step 5 swap node2 next to be node1 next */
    (*node1)->next_ = n2;
    /* step 6 swap node2 prev to be node1 prev */
    (*node1)->prev_ = p2;
    /* step 7 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;
    /* step 8 swap node2 next prev to be node1 next prev */
    (*node1)->next_->prev_ = x1;



  }
  else if(n2 == NULL)
  {
     /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
     /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = p1;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;
        /* step 5 node1 prev next swapped with node2 prev next */
    (*node2)->prev_->next_ = x2;


    /* step 6 swap node2 next to be node1 next */
    (*node1)->next_ = NULL;
    /* step 7 swap node2 prev to be node1 prev */
    (*node1)->prev_ = p2;
    /* step 8 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;


  }
  else
  {
       /* step one swap nodes */
    temp = *node1;
    *node1 = *node2;
    *node2 = temp; 
     /* step two swap node1 prev to be node2 prev */
    (*node2)->prev_ = p1;
    /* step three swap node1 next to be node 2 next */
    (*node2)->next_ = n1;
    /* step four swap node1 next prev to be node2 next prev */
    (*node2)->next_->prev_ = x2;
        /* step 5 node1 prev next swapped with node2 prev next */
    (*node2)->prev_->next_ = x2;


    /* step 6 swap node2 next to be node1 next */
    (*node1)->next_ = n2;
    /* step 7 swap node2 prev to be node1 prev */
    (*node1)->prev_ = p2;
    /* step 8 swap node2 prev next to be node1 prev next */
    (*node1)->prev_->next_ = x1;
    /* step 9 swap node2 next prev to be node1 next prev */
    (*node1)->next_->prev_ = x1;


  }
  /* swap surrounding */

}
Improve this question
6
  • I would start by using meaningful variable names. And by recognising that, for example, if (*node1)->prev_ is NULL then you are absolutely not allowed to access (*node1)->prev_->next_ (hint: you do). Of course, if you used a debugger, you would find exactly the line that crashes, and you wouldn't need to ask here. Commented Apr 26, 2017 at 5:43
  • Ah I forgot I made that change. I was trying to make it easier to read when I posted here. I guess it was counter intuitive. Yea I couldn't understand how to make the gdb take my program and the sample.txt file at the same time. Commented Apr 26, 2017 at 6:26
  • Yeah.. you need to tame your debugger. Without it, you are essentially unable to develop software. Commented Apr 26, 2017 at 6:37
  • If your data isn't super-heavy, it might be easier to just sort by swapping the data rather than the pointers. That's a bit like "cheating", but if it leads to simpler software with fewer bugs, that's fine. Another approach might be to gather the data into an array, sort that, then overwrite the list by iterating the array and list in parallel. That's perhaps a bit extreme, though. Commented Apr 26, 2017 at 8:27
  • Another option is to add a dummy head and tail node onto the list temporarily. That way you know all your pointers are valid. Then you just remove them at the end. A further simplification is to only manage single linkage while sorting the list, and then do one final pass that sets all the prev_ pointers. Commented Apr 26, 2017 at 9:13

2 Answers 2

Reset to default
1

There are 8 pointers to modify when you swap two nodes in a double linked list. See the 8 arrows in the diagram below.

+---+    +---+    +---+        +---+    +---+    +---+
|   |--->| A |--->|   | ...... |   |--->| B |--->|   |
|   |<---|   |<---|   | ...... |   |<---|   |<---|   |
+---+    +---+    +---+        +---+    +---+    +---+

Now, either of A or B could possibly be at the beginning or end of the list. They could also be right next to each other (a special case we will address in a bit).

The simplest thing to do here is to first store pointers to those four unlabeled nodes. This is all the information you will need:

struct node *a_prev = a->prev;
struct node *a_next = a->next;
struct node *b_prev = b->prev;
struct node *b_next = b->next;

Now, since any of those pointers can be NULL, you simply do a sanity test before acting on them:

if (a_prev) a_prev->next = b;  //(1)
if (a_next) a_next->prev = b;  //(2)
if (b_prev) b_prev->next = a;  //(3)
if (b_next) b_next->prev = a;  //(4)

And then you can update the links from the actual nodes:

a->prev = b_prev;  //(5)
a->next = b_next;  //(6)
b->prev = a_prev;  //(7)
b->next = a_next;  //(8)

Now, what about that special case? There are two versions:

a_prev   b_prev   a_next   b_next
+---+    +---+    +---+    +---+
|   |--->| A |--->| B |--->|   |
|   |<---|   |<---|   |<---|   |
+---+    +---+    +---+    +---+

b_prev   a_prev   b_next   a_next
+---+    +---+    +---+    +---+
|   |--->| B |--->| A |--->|   |
|   |<---|   |<---|   |<---|   |
+---+    +---+    +---+    +---+

Let's take the first one. What lines of code will break the structure of the list? You can see that since b_prev == a and a_next == b, the following:

if (a_prev) a_prev->next = b;  //(1) OK
if (a_next) a_next->prev = b;  //(2) ERROR b->prev = b 
if (b_prev) b_prev->next = a;  //(3) ERROR a->next = a
if (b_next) b_next->prev = a;  //(4) OK
a->prev = b_prev;  //(5) ERROR a->prev = a
a->next = b_next;  //(6) OK and fixes 3
b->prev = a_prev;  //(7) OK and fixes 2
b->next = a_next;  //(8) ERROR b->next = b

So there are two statements (5 and 8) which break. First, what should they be?

a->prev = b;
b->prev = a;

You can also see that if A and B are reversed (the second case) then the opposite problem occurs (5 and 8 will break; 6 and 7 will fix 1 and 4; 2 and 3 will be okay).

If you want compactness, you can extend these four last statements with the ternary operator. It might mess with your head a bit though:

a->prev = (b_prev == a ? b : b_prev);  //(5)
a->next = (b_next == a ? b : b_next);  //(6)
b->prev = (a_prev == b ? a : a_prev);  //(7)
b->next = (a_next == b ? a : a_next);  //(8)

To squeeze out the last of the branching, you could rearrange these four statements without the ternary operator (since half the tests are redundant). Alternatively you could rewrite the statements to use two tests (instead of the four I wrote for symmetry) and rely on the compiler for optimization.

I might not bother, but you could also expand the whole thing:

if (a_next == b)
{
    a->prev = b;       //(5)
    a->next = b_next;  //(6)
    b->prev = a_prev;  //(7)
    b->next = a;       //(8)
}
else if (b_next == a)
{
    a->prev = b_prev;  //(5)
    a->next = b;       //(6)
    b->prev = a;       //(7)
    b->next = a_next;  //(8)
}
else
{
    a->prev = b_prev;  //(5)
    a->next = b_next;  //(6)
    b->prev = a_prev;  //(7)
    b->next = a_next;  //(8)
}
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

There is an additional special case: a and b can be adjacent; (a->next == b; b->prev ==a;)
would you be able to explain the sanity test you are using? I a new to pointers/doubly linked list and haven't seen that syntax. Is it something similar to a ternary operator that I just have to look up? Thank you for the help
@wildplasser I mentioned that there are special cases (two actually) where the nodes are adjacent. In that case, half of the pointer assignments are redundant but no harm is done because these pointers are first saved on the stack.
@EthanGlory You don't need the ternary operator. I'm just doing a unary pointer test. The statement if (a_prev) is a non-zero = truth case and is specially allowed by the C standard to be equivalent to if (a_prev != NULL).
@paddy what is the other special case. I assumed windplasser answer correct. If they are neighbors that mean that the a->next == b && a ==b->prev which would mean when I save the initial pointers a_next I can't use it the same way I would if they were separated one node between them. This is the problem I think I have since if I just make a->next = b->next;. I would be essentially making a_node->next point right back to a_node or is this completely wrong?
|
0

The problem in your swap() is x4 and y4 , both has NULL value and you are trying to de-reference both pointers, which leads to segmentation fault.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.