473,692 Members | 2,271 Online

# Function that can swap elements in a singly linked list

3 New Member
Some one help me write a function that can swap elements in a singly linked list?Having a problem swapping the elements without, loosing some of the data?
Mar 5 '10 #1
18 17848
slavik262
5 New Member
Assuming you can get pointers to the data of the two nodes you want to swap (call them a and b), I'd do the following:
1. In your function, create a variable to temporarily hold the value of b (if you're using an int, int temp = b).
2. Assign the value of a to the value of b (b = a).
3. Assign the value of a to the temporary variable (a = temp).
Mar 5 '10 #2
jkmyoung
2,057 Recognized Expert Top Contributor

What you need to do is find the nodes before them. Say your nodes are a, b.
Find the nodes linking to them, say beforeA, beforeB.

beforeA.next = b;
beforeB.next = a;
So now you've switched the links to them. Now, you must switch the links after the nodes.
temp = a.next;
a.next = b.next;
b.next = temp;

Also, you have to take into account: what if there is no beforeA, or beforeB? (eg one of them is the head?) See how this works out, and then try to figure out your special cases. Don't forget to check if a = b; then you don't have to do any work!
Mar 5 '10 #3
slavik262
5 New Member
What is the necessity of swapping the nodes themselves? While swapping the values isn't truly the same as swapping the nodes, the end result is the same without all the extra pointer assignments.

A check to see if a already equals b would save you a lot of time though.
Mar 5 '10 #4
jkmyoung
2,057 Recognized Expert Top Contributor
I guess it depends on the composition of the nodes; whether the data is easily copyable or depends on the context of the node.

Mar 5 '10 #5
slavik262
5 New Member
Ah, so you're saying that it might be faster to swap the pointers around if the data stored in the linked list is a complex type like a class.
Mar 5 '10 #6
weaknessforcats
9,208 Recognized Expert Moderator Expert
This is not that hard.

If you have node addresses A B C D and you want to swap B and C what you do is:

1) Traverse to B. During this traverse, save the address of the current node in TEMP before you go the the next node. When you get to B, TEMP will have the address of A.

2) TEMP->NEXT (remember TEMP is the address of A) is assigned B->NEXT. Now you have A pointing to C.

3) B->NEXT is assigned B->NEXT->NEXT (B->NEXT is C. Therefore,
B->NEXT->NEXT is really C->NEXT,which is D).

It looks like this:

TEMP->NEXT = B->NEXT;
B->NEXT = B->NEXT->NEXT;
Mar 5 '10 #7
slavik262
5 New Member
Right, but the point we were discussing before was that if you have a simple data type, it would be faster and simpler to just swap out the values of the nodes.
Mar 5 '10 #8
Bito
3 New Member
Am trying to write a program that prompts the user to enter integer data, i store it in a linked list then i sort it into ascending order. Am using the selection sort function to arrange the data and its supposed to call the swap function, i want to swap the last and largest element in the linked list. but i do not know how to write that function.these are my two functions to find the last and largest elements in the linked list
Expand|Select|Wrap|Line Numbers
1. Node * maxPtr(Node * &list,int n)
2. {
3.     int i = 0;
4.     Node * mPtr = list;
5.     Node * iPtr = list -> next;
6.     while( i< n)
7.     {
8.            if(iPtr -> data > mPtr -> data)
9.               {
10.                    mPtr = iPtr;
11.               }
12.               i++;
13.               iPtr = iPtr ->next;
14.    }
15.    return mPtr;
16. }
17.
18. Node * lastPtr(Node * &list,int n)
19. {
20.     Node * newp = list;
21.     Node * lastp;
22.     int i = 0;
23.     while(i < n)
24.       {
25.      if(newp -> next  == NULL)
26.         lastp = newp;
27.       }
28.       i++;
29.       newp = newp -> next;
30.       return lastp;
31.
32. }
33.
Am left with writing the swap function and need help with that..
Mar 6 '10 #9
Banfa
9,065 Recognized Expert Moderator Expert
In my experience if you are receiving a series of values and storing them in a list that finally has to be ordered it is often just as easy to put them in the list in the right order in the first place as to sort the list after you have all the values.
Mar 6 '10 #10