CODEWITHSUNDEEP
clinked-listnodesswapdoubly-linked-list
Peter Povy
Peter Povy

Reputation: 3

How to swap nodes in a linked list without swapping data in C language?

I use this sorting function, but I don't know how to swap node addresses instead of values. I use doubly linked list.

Thank you

void sort(LISTnode **h) {
    LISTnode * start, * min, * temp;
    int num;
    start = *h;
    while (start->next != NULL) {
        temp = start;
        min = temp;
        temp = temp->next;

        while (temp != NULL) {
            if (temp->number < min->number)
                min = temp;
                temp = temp->next;
        }

        // This part of the code
        num = min->number;
        min->number = start->number;
        start->number = num;

        start = start->next;
    }    
}

Upvotes: 0

Views: 3399

Answers (2)

shiwang
shiwang

Reputation: 160

Alternative method..
Instead of manipulating with the pointers it is easier to swap the pointers using double pointers..

void swap(Node* &a,Node* &b){
    Node* c=a,a=b,b=c;
}

void swapNodes(Node** head_ref, int x, int y)
{
    Node**a=NULL,**b=NULL;
    Node* head=*head_ref;
    while(head!=NULL){
        if(head->data==x)   *a=head;
        else if(head->data==y)  *b=head;
    }  
    if(a&&b){
        swap(*a,*b);
        swap((*a)->next,(*b)->next);
    }
}

Upvotes: 0

Aconcagua
Aconcagua

Reputation: 25516

Swapping two nodes (Edit: non-adjacent ones! - special handling is required as the code below will set part of the involved next/prev pointers back to the own object on adjacent nodes!!!):

x->prev->next = y;
x->next->prev = y;

y->prev->next = x;
y->next->prev = x;

Now the nodes changed their positions in the list, need to adjust nodes themselves:

tmp = x->prev;
x->prev = y->prev;
y->prev = tmp;

tmp = x->next;
x->next = y->next;
y->next = tmp;

Finally: adjusting the head pointer:

if(list->head == x)
{
    list->head = y;
}
else if(list->head == y)
{
    list->head = x;
}

Done...

Well, half way only: Above applies for a doubly and circularly linked list (where you can get the tail via list->head->previous). If you don't have a circularly linked list, add appropriate null pointer checks to the very first code section (second one you do not need, assuming x and y are both not null...) and do the head adjustment for the tail, too.

Side note: Because of having to adjust head (and tail, if need be), you cannot swap safely without the parent list of the nodes...

That's quite a lot of pointer adjustment necessary, though. I'd rather consider swapping data within the nodes instead (inspite of being excluded explicitly in your question!). If you did not want to do that because of data being large, then consider storing the data separately from the nodes and let the nodes have a pointer to the data. Swapping then just is swapping two pointers, and you even don't need the parenting list object...

Upvotes: 1

Related Questions