Unexpected Node Swap for Doubly Linked List

[Xeratol]

Good Day!

I'm teaching Doubly Linked Lists and I gave my students an exercise on Node Swapping with guidelines. The prototype is as follows:

void node_swap(struct node *a, struct node *b);

The node structure is defined as:

struct node {
    int data;          // arbitrary data
    struct node *next; // next element
    struct node *prev; // previous element
};

a and b are assumed to be non-null pointers inside a doubly linked list with a global root defined as:

struct node *root;

The considerations are as follows:

1) a or b might be first/last element (prev or next is null)
2) a and b are consecutive nodes in the linked list (either a->next == b or b->next == a)
3) a and b are the same elements in the list

My answer is as follows:

void node_swap(struct node *a, struct node *b) {
    if (a == b) return; // do nothing
    
    if (a->next == b) {
        // b comes after a
        // swap the pointers
        struct node *t = a;
        a = b;
        b = t;
        // algorithm will only work if a comes after b
        // when a and b are consecutive
    }
    
    struct node *bPrev = b->prev;
    struct node *aNext = a->next;
    
    if (a->prev == b) {
        // a comes right after b
        b->next = a->next;
        a->next = b;
        if (bPrev)
            bPrev->next = a;
        else
            root = a;
        
        a->prev = b->prev;
        b->prev = a;
        if (aNext)
            aNext->prev = b;
    } else {
        if (a->prev)
            a->prev->next = b;
        else
            root = b; // 'a' was the first element
        b->prev = a->prev;
        
        if (bPrev)
            bPrev->next = a;
        else
            root = a; // 'b' was the first element
        a->prev = bPrev;
        
        if (b->next)
            b->next->prev = a;
        a->next = b->next;
        
        if (aNext)
            aNext->prev = b;
        b->next = aNext;
    }
}

So my code is quite lengthy and covers all scenarios.

Now the question is, my student gave me this:

void node_swap(struct node *a, struct node *b) {
    struct node* t;
    if(a->next) t = a->next;
    else t = 0;
    
    a->next = b->next;
    if (a->next) a->next->prev = a;
    b->next = t;
    if (b->next) b->next->prev = b;
    
    if(a->prev) t = a->prev;
    else t = 0;
    
    a->prev = b->prev;
    if (a->prev) a->prev->next = a;
    else root = a;
    b->prev = t;
    if (b->prev) b->prev->next = b;
    else root = b;
}

And it works perfectly! I mean, should it? What if a and b are consecutive such that a->next == b. The following line would make t point to b.

if(a->next) t = a->next;

and the following would make b->next point to itself.

b->next = t;

Though upon running and testing it... it works perfectly! For all cases! I ran through the debugger and found out that this line fixes everything:

b->prev->next = b; // magic statement!

Right before that line, b is disconnected from the linked list, no element in the list points to b. In fact, b->prev and b->next points to b (even though b->prev was not modified prior to the above statement). Then after that magic statement; around 4 pointers gets fixed and includes b back in to the list, swapped in the place of a.

I'm using XCode with the following compiler:
Using built-in specs.
Target: i686-apple-darwin11
Configured with: /private/var/tmp/llvmgcc42/llvmgcc42-2336.11~67/src/configure --disable-checking --enable-werror --prefix=/Applications/Xcode.app/Contents/Developer/usr/llvm-gcc-4.2 --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-prefix=llvm- --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin11 --enable-llvm=/private/var/tmp/llvmgcc42/llvmgcc42-2336.11~67/dst-llvmCore/Developer/usr/local --program-prefix=i686-apple-darwin11- --host=x86_64-apple-darwin11 --target=i686-apple-darwin11 --with-gxx-include-dir=/usr/include/c++/4.2.1
Thread model: posix
gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)

Is this a compiler optimization? I'm running in Debug Mode where optimization is set to -O0. I don't know what causes this. I'm totally stomped.

Could someone explain this phenomenon. Thanks!

[codewalker]

Works because line# 6 in the student code?
if(a->next) t = a->next; then a->next = b->next; and then b->next = t;