Function that can swap elements in a singly linked list

[Bito]

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?

[slavik262]

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).

[jkmyoung]

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!

[slavik262]

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.

[jkmyoung]

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.

[slavik262]

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.

[weaknessforcats]

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;

[slavik262]

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.

[Bito]

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

Node * maxPtr(Node * &list,int n)
{
    int i = 0; 
    Node * mPtr = list;
    Node * iPtr = list -> next;
    while( i< n)
    {
           if(iPtr -> data > mPtr -> data)
              {
                   mPtr = iPtr;
              }
              i++;
              iPtr = iPtr ->next;
   }
   return mPtr;
}
 
Node * lastPtr(Node * &list,int n)
{
    Node * newp = list;
    Node * lastp;
    int i = 0;
    while(i < n)
      {
     if(newp -> next  == NULL)
        lastp = newp;
      }
      i++;
      newp = newp -> next;
      return lastp;
 
}
 

Am left with writing the swap function and need help with that..

[Banfa]

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.

[Bito]

so how would i be able to do that?? and can u help me with this invariance questionas well..

What is the invariance of the algorithm??

int power(int n, int p)
// Pre: p >= 0
// Post: returns n raised to the power p
{
int result = 1;
int i = 0;
while (i != p)
{
result = result * n;
i++;
}
return result;
}

am abit confused on what we are supposed to do.. Is it right to say that the invariance is n^p since we are going to multiply n by its self n times??

[weaknessforcats]

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.

How do you know this would be faster?

If you have an int, that would be the size of a pointer. Swapping trhe int and swapping the next pointer of the nodes is about the same.

Swapping floating point will be very much slower. The variables are bigger and have rounding considerations.

Swapping char will cause a conversion to int and then a conversion back to char.

[jkmyoung]

I agree with Banfa. Construct your single linked list one by one, but have your AddNode function check the values.
eg. pseudo

void addNode(newNodeValue){
int newNodeValue;
Node newNode = new Node(newNodeValue);
Node curr, next;
curr = head;
if (curr == null){ 
  head = newNode;
  return;
}
if (curr.value > newNodeValue){
   next = head;
   head = newNode;
   head.next = next;
   return;
}  
next = curr.next();
while (next != null && next.value < newNodeValue){
  curr = next;
  next = curr.next;
}
curr.next = newNode;
if(next != null){// end of list
  newNode.next = next;
}
 

[weaknessforcats]

Actually, I would improve this by writing a function with two arguments that are pointers to node that would insert the second pointer after the first pointer in the list.

What this will do is isolate all this next/prev pointer fiddling to one function. Call that function from your AddNode.

Note that ot insert at the front of the list, you add your insert-after function using the adress of the first node in the list as the second argument.

Then, write a second function to create a new node on the heap and return a pointer to that node. This function will have the value of the node as the first argument.

Your AddNode would start to look like:

void AddNode(NewValue)
{
 
Node* temp = FindEndOFList();         //write this too
Node* newNode = CreateNode(NewValue);
InsertAfter(temp, newNode);
}

By having your functions do only one thing, you can use them more often.

[jkmyoung]

In response to post 11: Sorry, do you have another definition of invariance? It sounds like what wouldn't change in the function regardless of the values of p and n.

In response to post 12: Switching links requires at most 4 link switches, as well as a lot of special case testing.

In response to post 14: Then the insertions would not be sorted. The only reason for post 13 was for sorted insertion. Could write a simplifying function called Node FindGreatestNodeLessThan(int value), which returns the last node with value smaller than the given value. eg:

void addNode(int newValue){
  Node newNode = new Node(newValue);
  Node last = FindGreatestNodeLessThan(newValue);
  if( last == null){
     newNode.next = head;
     head = newNode;
     return;
  }
  newNode.next = last.next;
  last.next = newNode;
}

But this is only useful if FindGreatestNodeLessThan can be reused somewhere. The function FindGreatestNodeLessThan would require pointer swapping anyways.

[whodgson]

Why can`t a single pointer be set to the head and a second pointer set to the tail and then the two pointers be swapped using the swap function from the algorithm header. If it works properly with a string or array or vector why would it not work with a list?

[jkmyoung]

@whodgson
It's not just a list, it's a Linked List.

[Banfa]

Arguambly a <list> is a linked list or at least most commonly is implemented as one although a quick glance at the standard doesn't seem to indicated that it is specified as being implemented that way.

whodgson the thing being discussed in this thread is a home grown (linked) list not an STL list. This is may or may not be being implemented in C++ however what is certain is that there is no suggestion that this home grown list conforms to the requirements for a standard container and therefore none of the standard algorithms can be expected to work on them.

Additionally look at the definition of swap, it swaps the values of 2 objects, in this case that would include all the pointers defined in the node effectively resulting in no change (the data would be stored in different locations but the list would ultimately have the same order.

swap does not work on pointers (or iterators) but objects and for that reason it can not be used on a linked list, or iterators into and standard container or pointers.

[whodgson]

I think I should not have butted in as I did -- quite rude really.
But thank you Banfa for your explanation. I intend to study it further.
p.s. I apparently mistakenly thought that all lists were at least singly linked.