Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Linked list - swapping nodes

Posted on 2006-11-27
14
Medium Priority
?
567 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
The top UI technologies you need to be aware of

An important part of the job as a front-end developer is to stay up to date and in contact with new tools, trends and workflows. That’s why you cannot miss this upcoming webinar to explore the latest trends in UI technologies!

 
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

The top UI technologies you need to be aware of

An important part of the job as a front-end developer is to stay up to date and in contact with new tools, trends and workflows. That’s why you cannot miss this upcoming webinar to explore the latest trends in UI technologies!

Question has a verified solution.

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

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:
The viewer will learn how to implement Singleton Design Pattern in Java.
Suggested Courses

721 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