Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Linked list - swapping nodes

Posted on 2006-11-27
14
Medium Priority
?
580 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
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 6

Accepted Solution

by:
SeanDurkin earned 500 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

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

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

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
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 …
Suggested Courses

782 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