Swap nodes in a singly-linked list
I am trying to swap two nodes. For example if the nodes are a and b I am passing the pointers
(a-1)->next and (b-1)->next which are basically nodes a and b.
void swap(struct stack **a,struct stack **b)
{
struct stack *temp1 = *a, *temp2 = *b, *temp3 = *b;
*a = *b;
(*b)->next = (temp1)->next;
temp2 = temp1;
(temp2)->next = temp3->next;
}
What am I doing wrong? When I am trying to print the nodes after calling the function it's an infinite loop. Please help.
Answer
Why Infinite loop?
Infinite loop is because of self loop in your list after calling swap() function. In swap() code following statement is buggy.
(*b)->next = (temp1)->next;
Why?: Because after the assignment statement in swap() function temp1's next starts pointing to b node. And node[b]'s next point to itself in a loop. And the self loop is reason for infinite loop, somewhere in your code where you traverse linked list.
Below I drawn to show how swap() works step-by-step. May be this help you to understand your error:
You didn't mention but I am assuming linked list having following relation between a and b: (read red comments)
(step-1):
+----+----+----+ +---+----+----+
| one |----->| two |
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| *a | *b
| |
temp1 temp2, temp3 "after assignment to temp variables"
(step-2): ^
|
*a = *b | *a "<--- next step"
(step-3): The buggy statement
(*b)->next = (temp1)->next; "Change link: (temp1)->next; is `two` node"
" *b is `two`, So Self loop"
+----+----+----+ +---+----+----+ <---|
| one | | two |-----|
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp1 temp2, temp3 " after assignment to temp"
See (temp1)->next; is actually b and you are assigning (*b)->next = (*b) by doing (*b)->next = (temp1)->next; hence adding a self loop.
(step-4):
I think with the diagram you can easily understand what last two lines of your swap() code are doing:
temp2 = temp1;
(temp2)->next = temp3->next;
Following is my diagram for this two lines:
temp2 = temp1;
+----+----+----+ +---+----+----+ <---|
| one | | two |-----| "<--- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
(step-5): Even last line of your function swap() left loop as below:
(temp2)->next = temp3->next; " last line of your code"
+----+----+----+ +---+----+----+ <---|
| one |----->| two |-----| "<-- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
So loop still there at two node so infinite loop.
How to swap two nodes in single linked list?
One way is swap node's data instead of swapping node's position it self in linked list (as I commented to your question). But you wants to swap node's position in list.
Well this good! if node data size is larger, that time its better to swap node's position rather then swap node's data(swapping data will be bad choice)
Because you having single linked list, to swap any two arbitrary nodes in list you need there previous node addresses too. (this is the point you don't consider in your swapping logic)
WHY need previous pointers?:
Suppose after some successful insert(push) operations, your list becomes as follows:
0 <--------TOP - "head"
9 <--p
2
6 <--q
5
A horizontal diagram- Suppose you want to swap say two nodes (q) and (p):
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (q) (p)
(head)
As I said, to swap we need previous pointers. You need to think about following
(In theory, I am writing for specific nodes (p) and (q) just to keep explanation simple. but my implementation is quit general):
In list previous pointers:
node[0] points to node[9] that is (q), and
node[2] points to node[6] that is (p)
And
node[9] points to node[2]
node[6] points to node[5]
NOTICE: If you want to swap two nodes say node[ 9 ] and node[ 6 ] then you should use pointers of the nodes previous to these two nodes.
For example: two swap node[ 9 ] and [ 6 ], you also need to change next pointer of node[ 0 ] and next pointer of node[ 2 ] in above diagram.
How would be the list after swapping this two nodes?
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (p) (q)
(head)
What is now in previous nodes [o] and [2]?
After swapping, In list previous pointers
node[0] points to node[6] that is (q), and
node[2] points to node[9] that is (p)
And
node[9] points to node[5]
node[6] points to node[2]
So if you want to swap two nodes; there immediate previous node also effects and because list is single link list you need previous pointers too.
How to find previous node pointers?
Suppose you want to swap any two nodes node[p] and node[q] then you can use head pointer to find previous node.
So swap function syntax (In my implementation) is like:
void swap(struct stack **head, // head node
struct stack **a, // first candidate node to swap
struct stack **b); // first candidate node to swap
And you will call function like:
swap(&head, &p, &q);
Definition: (To understand code please read comments I added at almost each line)
void swap(struct stack **head,
struct stack **a,
struct stack **b){
// first check if a agrgument is null
if( (*head) == NULL || // Empty list
(*a) == NULL || (*b) == NULL){ // one node is null
// Nothing to swap, just return
printf("\n Nothing to swap, just return \n");
return;
}
// find previos nodes
struct stack* pre_a = get_prevnd(*head, *a);
struct stack* pre_b = get_prevnd(*head, *b);
//Now swap previous node's next
if(pre_a) pre_a->next = (*b); // a's previous become b's previous, and
if(pre_b) pre_b->next = (*a); // b's previous become a's previous
//Now swap next fiels of candidate nodes
struct stack* temp = NULL;
temp = (*a)->next;
(*a)->next = (*b)->next;
(*b)->next = temp;
//change head: if any node was a head
if((*head)==(*a))
*head = *b;
else
if((*head)==(*b))
*head = *a;
}
In swap() function you can notice that I call a helper function get_prevnd(, );. This function returns address of previous node in list. In The function get_prevnd(, );, first argument is list head and second argument is node for which you are looking for.
// find previous node function()
struct stack* get_prevnd(
struct stack* head,
struct stack* a
){
if(head == a){
// node[a] is first node
return NULL;
}
struct stack* temp = head; // temp is current node
struct stack* pre_a = NULL;
while(temp && temp!=a){ //search while not reach to end or the node
pre_a = temp; // find previous node
temp = temp->next;
}
if(temp!=a){// node[a] not present in list
fprintf(stderr, "\n error: node not found!\n");
exit(EXIT_FAILURE); // bad technique to exit()
}
return pre_a;
}
And fortunately the code is WORKING :). Below is link for online test of this code. I have tested for various kind of inputs.
CodePad: To Swap node in single linked list. Please check output.
And sorry for bad English