C: swap function (linked list)

[sedaw]

need to write function swap(*list,char X , char Y) that swap beteein items in liked list ;

supose list: A ->B->C->D->NULL

swap(list,A,B)

result:


list : B->A->C->D->NULL


changing value of items is forbidden .


TNX . ..........

[Tassos Souris]

Make a function that takes pointers to the pointers that point to these two nodes... then swap those pointers..

[sedaw]

but it`s singly listed .

it`s alright ?

[JosAH]

@sedaw
Forbidden by who? I guess this is homework again; you show us what you have tried and explain to us where you got stuck and then we might try to help you out. We are not going to give you a copyable and pastable spoonfed solution.

kind regards,

Jos

[sedaw]

hello Jos !

that`s not homework i just learning C by myself , i want to sort list but dont know how to swap beteen nodes in list .

i tryin do it without change the values cause i want to learn linked lists , the option of change values is simple and not useful for learning .

TNX , wish you all the best.

[Banfa]

You can easily write a swap function in terms of an insert function and a remove function (that does not delete the removed node just returns it.

[donbock]

@sedaw
Your swap prototype hints that the list items are single characters. In general, a linked list node can contain a lot of information (ie, fields). Typical practice is to characterize one field as the key field. You can then specify a swap function that searches for two nodes whose key fields match the function arguments, and then swap the position of those nodes in the list. You need to consider how you want to handle the corner cases:

• More than one node matches the key value.
• No node matches the key value.
• The caller specifies the same key value twice (swap a node with itself).
• The *list argument is NULL.

[sedaw]

ok.... my solution :

void sort_list(Node*item)
{
    Node *ptr1, *ptr2, *current, *temp;
    while(item!=NULL)
    {
        current=item;
        while(current!=NULL)
        {
            if(current->value < item->value)
            {
                ptr1=item->next;
                ptr2=current->next;
                temp=item;
                item=current;
                item->next=ptr1;
                current=temp;
                current->next=ptr2;
            }
            current=current->next;
        }
        item=item->next;
    }
}
 

the program not workin alright although theres no compilation error .



TNX ..........

[sridhard2406]

Try to put the printf statment and check the flow.

In 9th line ur comparing same pointer value.

[Banfa]

That is not a swap algorithm that is a sort algorithm (or would be if it worked). Since many sorts need to swap you should write a swap algorithm.

What you have written comes no where near to a swap, for instance these lines

temp=item;
item=current;
...
current=temp;

May look like a swap but they operate on local variables and therefore have absolutely no effect on your list.

You need to change the list members taht are pointing to "current" and "item".

However the code does change the items that "current" and "item" point to because you change the data that they point to not the pointers themselves. So current-.next is swapped with item->next. This has the effect of partitioning you list as follows: Assume this list

A -> B -> C -> D -> E -> F

Assume current points to B and item points to D, you don't change the nodes pointing to current and item but you do swap where current and item point to so after you operation you have 2 chains

A -> B -> E -> F
D -> C -> D -> C -> D -> C -> D -> ...

The D/C chain is infinite and is also lost (assuming you have a head pointer to A).

1. Start by writing a successful swap function to swap 2 nodes in a list.
2. Then write your sort algorithm.

[Tassos Souris]

And again consider using pointers to the pointers that point to each node :)

[sedaw]

line 11-18 the swap code.

the pointers of items saved as ptr1 and ptr2 for backup

after changing the content of item by current

ptr1=item->next;
ptr2=current->next;

this is whats goin on:

E->D->C->B->A->NULL


supose swap E,C

save ptr1 = Node{E}->next = D->C->B->A->NULL


after change the content E &C :

Node{E}->value = C
Node{E}->next = B->A->NULL

now cangin the pointer :
Node{E}->next = ptr1


the new list C->D->C->B->A->NULL


same proces to Node{C} while data of Node{E} saved as temp .

Node{C}=temp;
Node{C}->next=ptr2 ;

[Banfa]

If you have a list of N nodes and you want to swap the positions of 2 arbitrary nodes P and Q in the list then you have to change the following nodes

node[P-1]
node[P]
node[Q-1]
node[Q]

That is you need to change the nodes before the 2 nodes you want swap because they need to point somewhere different after the swap.

Since your code on changes the pointers in 2 actual nodes it can not properly swap 2 nodes.

[sedaw]

is there any option to perform it on unidirectional list ?