Linked list - swapping nodes

I am trying to swap nodes in a linked list.

First of all I am trying to swap 2 nodes that are next to each other and are not start or finish nodes:

1.setPrevious(2.getPrevious());
1.setNext(2.getNext());

2.setPrevious(1.getPrevious());
2.setNext(1.getNext());                  

2.getPrevious().setNext(1);                  
1.getPrevious().setNext(2);                  

1.getNext().setPrevious(2);                  
2.getNext().setPrevious(1);

Surely this logic should work.

If you see that it does not then please suggest any changes.

Just hints otherwise it will be classed as cheating.

Cheers
john8932Asked:
Who is Participating?
 
SeanDurkinCommented:
Because you said it would be cheating if we gave the answer to your problem, I'll just explain what is wrong with your logic, and hopefully that will get you on the right track to solving your problem. Suppose we have nodes A through E, with A being the first node and E being the last. We'll switch nodes B and C, and they'll be nodes 1 and 2, respectively, in your problem:

A -> B -> C -> D -> E
  (<-   <-    <-    <-)   it's a doubly-linked list, so we have those pointers as well.

The goal is to do this, obviously:  A <--> C <--> B <--> D <--> E

I'll go through each of your steps just to explain what you're doing here:


1.setPrevious(2.getPrevious()); ==> B.setPrevious(C.getPrevious());

     - This will set B's previous pointer to D's previous (which is B). B.getPrevious() will now return B instead of A.

1.setNext(2.getNext()); ==> B.setNext(C.getNext());

     - This will set B's next to C's next (which is D). B.getNext() will now return D.

2.setPrevious(1.getPrevious()); ==> C.setPrevious(B.getPrevious());

     - This will set C's previous to B's previous (which is now B). C.getPrevious() will now return B.

2.setNext(1.getNext()); ==> C.setNext(B.getNext());

     - This will set C's next to B's next (which is D now). C.getNext() will now return D.

2.getPrevious().setNext(1); ==>C.getPrevious().setNext(B);

     - This will set C's previous's next (which means B's next) to to B. B.getNext() will return B.
     
1.getPrevious().setNext(2); ==> B.getPrevious().setNext(C);

     - This will set B's previous's next (which means B's next) to C. B.getNext() will now return C.

1.getNext().setPrevious(2); ==> B.getNext().setPrevious(C);

     - This will set B's next's previous (which means C's previous) to C. C.getPrevious() will now return C.

2.getNext().setPrevious(1); ==> C.getNext().setPrevious(B);

     - This will set C's next's previous (which means D's previous) to B. D.getPrevious() will now return B.

-----------------------------------------------

Here's what your code results in (if everything I did was correct):

D.getPrevious() = B;
C.getPrevious() = C;
B.getNext() = C;
C.getNext() = D;
B.getPrevious() = B;

A -> B
(B) <- B -> C
(C) <- C -> D
(B) <- D

As you can see, problems resulted when you set B's previous to B with "B.setPrevious(C.getPrevious())," and so the pointer back to A was missing in the final product. As you already said, I can't tell you what exactly to do, but I think you should do as ADSLMark suggested and use a temporary node to store some pointers, because it won't be possible without it. Something along the lines of:

LNode temp = B;
// not sure if you need it, but to be safe:
temp.setNext(B.getNext());
temp.setPrevious(B.getPrevious());

Then you can begin setting it so that this:

A <--> B <--> C <--> D <--> E

should be

A <--> C <--> B <--> D <--> E

It always helps me to use visuals to grasp the topic, because it makes it so much easier. Now you can just look at the two LinkedList's right next to each other and see what needs to be done in terms of B & C's next and previous's.

Best of luck,

Sean
0
 
James_h1023Commented:
Doesn't your first statement
1.setPrevious(2.getPrevious());

Set 1's previous as 1 it self because 2.getPrevious would get 1!
0
 
ADSLMarkCommented:
TB - A - B - C - TE

A.prev = C.prev => A.prev = B
A.next = C.next => A.next = TE
C.prev = A.prev => C.prev = B (see first statement)
C.next = A.next => C.next = TE (see second statement)

I told you before, you have to save one of the two nodes, otherwise you lose the pointers!

Mark

0
Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

 
hoomanvCommented:
Why do you not just swap the contents of the two Nodes ?
The Nodes themselves are wrappers around original Values
Therefore no need to correct the links between them
0
 
hoomanvCommented:
Folks you are making it harder than it looks
In order to Swap X and Y whether they are at head mid or tail, or having singly, doubly or whatever linked list
Just do this
  tmp = B.value
  B.value = C.value
  C.value = tmp
Isn't it the answer ?
0
 
SeanDurkinCommented:
From what it looks like, hoomanv, that may not be the point of the problem, if it's for a class. I think the point is to understand the logic of using pointers of nodes in a doubly-linked list, but I'm not sure.
0
 
hoomanvCommented:
At least I'm sure that the point is to not make it complicated when it could be so easy
0
 
john8932Author Commented:
I do think I need a temporary node. I am getting quite near to using it I think:

Please say what is wrong with this (when run it takes away one node completey):

            node temp = B;

            temp.setNext(B.getNext());
            temp.setPrevious(B.getPrevious());

            B.setPrevious(C);
            B.setNext(C.getNext());

            C.setPrevious(temp.getPrevious());
            C.setNext(temp.getNext());



            //C.getPrevious().setNext(B);
            //B.getPrevious().setNext(C);

            //B.getNext().setPrevious(C);
            //C.getNe

If you could just say the line numbers that are wrong and then give hints please.

Thanks
0
 
john8932Author Commented:
Damn missed a bit on the last line:

//C.getNe

Should be:

//C.getNext().setPrevious(B);

0
 
ADSLMarkCommented:
How many times do we have to tell you that you have to save one node, because you lose the prev/next of that node when you set them.
If you use a save node, then you still have the previous and next of the node.

Assume we have two nodes A and C
If we change the prev/next of A and later want to use the prev/next of A to set C, then you are using the new values for prev/next instead of the preferable old values.

A.next = C.next
A.prev = C.prev
now A.next points to C.next and A.prev points to C.prev

So if we do:
C.next = A.next
then C.next points to A.next which is C.next

Understand?
Mark
0
 
SeanDurkinCommented:
john8932,

     node temp = B;

     temp.setNext(B.getNext());
     temp.setPrevious(B.getPrevious());

     B.setPrevious(C);
     B.setNext(C.getNext());

     C.setPrevious(temp.getPrevious());
     C.setNext(temp.getNext());

I believe the logic of this is all correct except for the last line. I'll show you what you're doing here:

B.setPrevious(C);
B.setNext(C.getNext());

     C <- B -> D

C.setPrevious(temp.getPrevious());
C.setNext(temp.getNext());

     A <- C -> C

I trust you can figure out what the problem is from there. :)
0
 
SeanDurkinCommented:
Also you can't forget to do A.setNext() and D.setPrevious(), but make sure to use them in relation to C and B (or temp).

A -> C
B <- D
0
 
hoomanvCommented:
john8932 :)
I'm curious to know what you want to achieve after swapping nodes ?
The outcome would be to have two nodes sit in place of each other, isn't it ?
what difference does it make if you make the node's contents swap, instead of the links ? can you explain ?
0
 
SamsonChungCommented:
Let me get this clear,

Start, End
Nodes, A, B ,C ,D

A.next = B
A.pre = Start

B.next = C
B.pre = A

C.next = D
C.pre = B

D.next = End
D.pre = C

now, let say we want to swap B and C.

what you do is

temp1.next = B.next
temp1.pre = B.pre

temp2.next = C.next
temp2.pre = C.pre

B.next = temp2.next
B.pre = temp2.pre

C.next = temp1.next
C.pre = B.pre

that way, you have Start <->A<->C<->B<->D<->end

Simple?
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.