473,692 Members | 2,271 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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
It's a little more complicated then that! You need to switch 4 links altogether. link to a, link from a, link to b, link from b.

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.

Bito, give us more info as to how you're storing your linked list, or what std library class you're using.
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

Sign in to post your reply or Sign up for a free account.

Similar topics

8
3945
by: surrealtrauma | last post by:
if i have circular linked list like: 14->12->10->8->6->4->2->0->// how can i revises it as 0->2->4->6->8->10->12->14->// is there any other method besides swap? Thank you
19
13567
by: RAJASEKHAR KONDABALA | last post by:
Hi, Does anybody know what the fastest way is to "search for a value in a singly-linked list from its tail" as oposed to its head? I am talking about a non-circular singly-linked list, i.e., head and tail are not connected. Of course, recursive function aproach to traverse the list is one way. But, depending upon the list size, it could overrun the stack pretty fast.
7
2608
by: Kieran Simkin | last post by:
Hi all, I'm having some trouble with a linked list function and was wondering if anyone could shed any light on it. Basically I have a singly-linked list which stores pid numbers of a process's children - when a child is fork()ed its pid is added to the linked list. I then have a SIGCHLD handler which is supposed to remove the pid from the list when a child exits. The problem I'm having is that very very occasionally and seemingly...
12
15092
by: Eugen J. Sobchenko | last post by:
Hi! I'm writing function which swaps two arbitrary elements of double-linked list. References to the next element of list must be unique or NULL (even during swap procedure), the same condition should be kept for references to previous element of list. Here is my solution below: struct node {
7
1970
by: Shwetabh | last post by:
Hi, can some one tell me: -> how to remove a loop from a singly linked list with a loop. -> how to count the number of nodes in a looped singly link list. Thanks
2
1486
by: Paminu | last post by:
I have a Linked-List and would like to create pointers to elements in this list. e.g I would like two pointers that point to each of their elements in the Linked-List. But there should always be exactly 5 nodes between these pointers. Does this make any sense or are there some more efficient way to access certain elements in a Linked-List?
3
4256
by: lrsweene | last post by:
How to swap elements in a singly linked list?
23
4366
by: Himanshu Chauhan | last post by:
Hi! I was wondering, In the first parse of a singly linked list of unknown length, is it possible to know when we are at middle of the linked list? Regards --Himanshu
4
4309
by: saki | last post by:
How do we reverse a singly linked list without using extra memory.Extra pointers can however be used
7
5735
by: davidson1 | last post by:
Hello friends, I want ur help regarding singly linked list in C,I tried in net,But it is confusing and difficult.I want singly linked list in a simple way of Understanding.Please Help Me I want single list to create,delete,Display Can u give me Program and Explanation,to create,display,Delete in a Simple and Easy Way.Really it will be Helpful for Me. I have given some partial code,I want Program to create,display,Delete a Singly...
0
8547
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9090
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8969
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
8810
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
6462
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5822
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4329
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
2983
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2242
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.