Solved

Linked list - swapping nodes

Posted on 2006-11-27
14
477 Views
Last Modified: 2008-01-09
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
0
Comment
Question by:john8932
  • 4
  • 4
  • 2
  • +3
14 Comments
 
LVL 4

Expert Comment

by:James_h1023
ID: 18021336
Doesn't your first statement
1.setPrevious(2.getPrevious());

Set 1's previous as 1 it self because 2.getPrevious would get 1!
0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18021469
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
 
LVL 14

Expert Comment

by:hoomanv
ID: 18021823
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
 
LVL 6

Accepted Solution

by:
SeanDurkin earned 125 total points
ID: 18021981
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
 
LVL 14

Expert Comment

by:hoomanv
ID: 18022069
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
 
LVL 6

Expert Comment

by:SeanDurkin
ID: 18022088
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
 
LVL 14

Expert Comment

by:hoomanv
ID: 18022235
At least I'm sure that the point is to not make it complicated when it could be so easy
0
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 

Author Comment

by:john8932
ID: 18022431
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
 

Author Comment

by:john8932
ID: 18022440
Damn missed a bit on the last line:

//C.getNe

Should be:

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

0
 
LVL 10

Expert Comment

by:ADSLMark
ID: 18022475
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
 
LVL 6

Expert Comment

by:SeanDurkin
ID: 18022544
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
 
LVL 6

Expert Comment

by:SeanDurkin
ID: 18022622
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
 
LVL 14

Expert Comment

by:hoomanv
ID: 18022630
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
 
LVL 6

Expert Comment

by:SamsonChung
ID: 18023548
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

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

Suggested Solutions

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
The viewer will learn how to implement Singleton Design Pattern in Java.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now