Solved

Linked list - swapping nodes

Posted on 2006-11-27
14
552 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
SharePoint Admin?

Enable Your Employees To Focus On The Core With Intuitive Onscreen Guidance That is With You At The Moment of Need.

 
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
 

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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Suggested Courses

739 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