CODEWITHSUNDEEP
clinked-list
jason dancks
jason dancks

Reputation: 1142

c: linked list: how to write a node swapping function?

here's my function:

void switchnodes(NODE **A)
{
    if((*A)->next)
    {
        NODE *first = pop(A);
        NODE *second = pop(A);
        push(A,first);
        push(A,second);
    }
}

push and pop:

void push(NODE **top,NODE *nnew)
{
    nnew->next=*top;
    *top=nnew;
}
NODE * pop(NODE **top)
{
    NODE *remove = *top;
    *top=(*top)->next;
    remove->next=0;
    return remove;
}

my confusion:

NODE:

typedef struct node {
    int value;
    struct node *next;
} NODE;

NODE * top my linked list holding values 1...10 NODE * holder is another pointer pointing to the 5th and 4th node of the linked list, respectively

switchnodes(&holder); holder pointing to the 5th node. The 6th node gets lost switchnodes(&(holder->next));holder pointing the 4th node. 5th and 6th nodes successfully swapped.

why does that happen?

and how do I write this function so I don't have to pass pointer->next? I can't do that in every instance, like if its the top node I need to swap.

Upvotes: 0

Views: 227

Answers (2)

dinomoth
dinomoth

Reputation: 86

You have to update first's "next" at switchnodes function. Here is a working function:

void switchnodes(NODE **A)
{
    if((*A)->next)
    {
        NODE *first = pop(A);
        NODE *second = pop(A);  
        push(A,first);
        first->next = second->next; //the missing line
        push(A,second);
    }
}

Upvotes: 1

M Oehm
M Oehm

Reputation: 29126

That's the way your list works: You can only swap nodes via next pointers; holder is a pointer outside the list. It may get updated, but the list won't know.

Say holder points to the 4th node. You swap it, it now points to the new 4th node, the former 5th node. But what's important: The next pointer of the list's third node still points to the 4th node - 4th before swapping that is.

You can make your list two-way by having a haed and a tail and an additional prev pointer for each node. Then you can use that information to update the swapped nodes' neighbours, if any.

Upvotes: 1

Related Questions